Blog

Appearance

2026-03-03Share

编程能力考查突击 ​

1. 模拟题（Simulation） ​

核心：按题意逐步实现，注意边界和输入格式。
典型场景：日期、进制、字符串解析、简单流程控制。

题目：P1055 [NOIP2008 普及组] ISBN 号码 ​

题意：验证 ISBN-10 校验位是否正确。
输入：形如 x-xxx-xxxxx-x 的字符串
输出：Right 或修正后的 ISBN

cpp
#include <iostream>
#include <string>
using namespace std;

int main() {
    string s; cin >> s;
    int sum = 0, k = 1;
    for (char c : s) {
        if (c == '-') continue;
        if (c == 'X') sum += 10 * k;
        else sum += (c - '0') * k;
        k++;
    }
    int r = sum % 11;
    if (r == 10) {
        if (s.back() == 'X') cout << "Right";
        else {
            s[12] = 'X';
            cout << s;
        }
    } else {
        if (s[12] == '0' + r) cout << "Right";
        else {
            s[12] = '0' + r;
            cout << s;
        }
    }
    return 0;
}

2. 排序与查找（Sorting & Searching） ​

核心：std::sort、二分查找（lower_bound）、去重。

题目：LeetCode 26. 删除有序数组中的重复项 ​

要求：原地去重，返回新长度

cpp
#include <vector>
#include <algorithm>
using namespace std;

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    int j = 1;
    for (int i = 1; i < nums.size(); ++i)
        if (nums[i] != nums[i-1])
            nums[j++] = nums[i];
    return j;
}

若需完整程序，用 cin 读入数组后调用此函数。

3. 简单数学（Math） ​

核心：GCD/LCM、素数、取模、进制转换。

题目：判断一个数是否为素数（n ≤ 10⁶） ​

cpp
bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; ++i)
        if (n % i == 0) return false;
    return true;
}

题目：求最大公约数（GCD） ​

cpp
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

4. 递归 / 简单 DFS ​

核心：理解递归结构，避免栈溢出（n 小即可）。

题目：计算阶乘（n ≤ 20） ​

cpp
long long fact(int n) {
    return n <= 1 ? 1 : n * fact(n - 1);
}

题目：斐波那契数列第 n 项（n ≤ 40） ​

cpp
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2); // 实际建议用循环，但递归可接受
}

考试若 n 较大（>30），改用迭代：

cpp
int fib(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; ++i) {
        int c = a + b;
        a = b; b = c;
    }
    return b;
}

5. 数组与字符串操作 ​

核心：遍历、统计、子串、拼接。

题目：统计字符串中每个字符出现次数（仅小写字母） ​

cpp
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string s; cin >> s;
    vector<int> cnt(26, 0);
    for (char c : s) cnt[c - 'a']++;
    for (int i = 0; i < 26; ++i)
        if (cnt[i]) cout << char('a' + i) << ":" << cnt[i] << endl;
    return 0;
}

6. 贪心（Greedy） ​

核心：局部最优即全局最优，常见于区间、分配问题。

题目：活动选择问题（给定若干 [start, end)，最多选几个不重叠活动） ​

cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Act { int s, e; };
bool operator<(const Act& a, const Act& b) { return a.e < b.e; }

int main() {
    int n; cin >> n;
    vector<Act> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i].s >> a[i].e;
    sort(a.begin(), a.end());
    int ans = 0, last = -1;
    for (int i = 0; i < n; ++i) {
        if (a[i].s >= last) {
            ans++;
            last = a[i].e;
        }
    }
    cout << ans << endl;
    return 0;
}

⚠️ 通用输入输出模板（务必熟记） ​

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <cctype>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 单组数据
    int n; cin >> n;

    // 多组数据（直到 EOF）
    // while (cin >> n) { ... }

    // 读一行（含空格）
    // string s; getline(cin, s);

    // 输出
    cout << result << '\n';

    return 0;
}

以上题目覆盖 90% 以上大一机试考点。优先掌握代码模板，理解逻辑，不必深究证明。
考前重点：能快速写出无 bug 的完整程序。

祝你明日 AC 全部，顺利入选图灵班。