CSP 初赛答题技巧

CSP 初赛要来了！想要参加 CSP 的复赛，就要先过初赛，否则就会连进入复赛写代码的机会都没有！很多省份的初赛分数线较低，这是因为初赛参赛人数少，而复赛名额多，所以基本不淘汰人。但是也有不少省份的初赛就具备较高的淘汰率，全国平均初赛淘汰率约为 75%。对于实力徘徊在分数线边缘的同学一定要对初赛引起足够的重视。

初赛的题型以单项选择题、判断题、阅读程序和程序填空（完善程序）为主，难点在阅读程序和程序填空，如果完全能够理解程序，一般就可以获得接近满分的成绩，但是由于读不懂题目的情况也时有发生，所以我们在这里主要讲解做题技巧。做题技巧通常是在做不出来题目的时候才使用的，可以让你提高选择题的正确率。（如果你一道题都读不懂，全场只用答题技巧，那么也很难考出较高的分数）

本文的例题全部取自 2022 至 2025 年 CSP-J 入门级第一轮的真题，是近几年考场上真实出现过的题目，建议每道例题都先捂住答案自己做一遍，再对照解析检查自己的实力。

一、代值法

2025 年入门级完善程序第 1 题（字符串解码）

本题是 2025 年入门级第一轮完善程序第 1 题。建议捂住答案先自己做一下，再看看解析检测自己的实力。

（字符串解码）"行程长度编码"（Run-Length Encoding）是一种无损压缩算法，常用于压缩重复字符较多的数据，以减少存储空间。假设原始字符串不包含数字字符。压缩规则如下：i) 如果原始字符串中一个字符连续出现 NN 次（N≥2N \geq 2），在压缩字符串中它被表示为"字符 + 数字 NN"。例如，编码 A12 代表 1212 个连续的字符 A。ii) 如果原始字符串中一个字符只出现 11 次，在压缩字符串中它就表示为该字符本身。例如，编码 B 代表 11 个字符 B。

以下程序实现读取压缩字符串并输出其原始的、解压后的形式。试补全程序。

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

int main() {
    string z;
    cin >> z;
    string s = "";

    for (int i = 0; i < z.length(); ) {
        char ch = z[i];

        if (① && isdigit(z[i + 1])) {
            i++;
            int count = 0;
            while (i < z.length() && isdigit(z[i])) {
                count = ②;
                i++;
            }
            for (int j = 0; j < ③; ++j) {
                s += ch;
            }
        } else {
            s += ④;
            ⑤;
        }
    }

    cout << s << endl;
    return 0;
}

  1. ①处应填

    • A. i < z.length()
    • B. i - 1 >= 0
    • C. i + 1 < z.length()
    • D. isdigit(z[i])

  2. ②处应填

    • A. count + (z[i] - '0')
    • B. count * 10 + (z[i] - '0')
    • C. z[i] - '0'
    • D. count + 1

  3. ③处应填

    • A. count - 1
    • B. count
    • C. 10
    • D. z[i] - '0'

  4. ④处应填

    • A. z[i+1]
    • B. ch
    • C. z.back()
    • D. (char)z[i] + 1

  5. ⑤处应填

    • A. i--
    • B. i = i + 2
    • C. i++
    • D. // 不执行任何操作

题目解析

程序要做什么很清楚：读入压缩串，遇到"字符 + 数字"就输出数字个该字符，遇到单个字符就原样输出。既然我们读懂了题意，那么给定输入，手算正确输出毫无难度——代值法就是把"手算的输出"当成一杆秤，把 ABCD 四个选项分别代入程序去称一称，与手算结果一致的选项就是答案。

先准备一把"秤"：取输入 A12。根据压缩规则，A12 代表 12 个连续的 A，所以正确输出是 12 个 A。① 处先随便选 C（待会儿再回头验证），进入压缩分支后 i = 1，从 z[1] = '1' 开始读数。

第 2 空：把四个选项分别代入"读出 12"这一步：

  • A 选项：count = 0 + 1 = 1，再读 z[2] = '2'，count = 1 + 2 = 3，输出 3 个 A，✗；
  • B 选项：count = 0 * 10 + 1 = 1，再 count = 1 * 10 + 2 = 12，输出 12 个 A，✓；
  • C 选项：每次都把 count 重置为当前数字，最后 count = 2，✗；
  • D 选项：count = 0 + 1 = 1，再 count = 1 + 1 = 2，✗。

应选 B。可见把数字串拼成整数必须用"×10\times 10 + 当前位"。

第 3 空：继续用这把秤。count 算出 12 之后，循环要输出 12 次字符 A，直接选 B（count - 1 少一次；10 恒为 10 次；z[i] - '0' 此时 i 已经走出数字串，算出的是负数，一次都不会输出）。

第 4、5 空：换一个输入 BC（两个单字符，正确输出是 BC）。i = 0 时 ch = 'B'，B 后面不是数字，走 else 分支：

  • ④ 的 A 选项把 z[1] = 'C' 加进 s，输出的第一个字符就错了；C 选项 z.back() 也是 'C'，同样错；D 选项把字符加一，错。只有 B 选项把当前字符 ch 加进去，✓，选 B。
  • ⑤ 的四个选项里，i-- 和"什么都不做"都会让 i 卡在原地导致死循环，i = i + 2 会跳过第二个字符、输出只剩一个 B，只有 i++ 能把 i 移到下一个字符，✓，选 C。

第 1 空：先用秤称一称。取输入 A12：B 选项 i - 1 >= 0 在 i = 0 时为假，直接走 else 分支，把数字 '1' 当成了普通字符，输出错乱，✗；D 选项 isdigit(z[i]) 对 'A' 为假，同样走错分支，✗。但 A、C 两个选项代入后都能得到正确结果，代值法排不掉了——这时就要回到代码本身看差别：第 1 空之后紧接着要访问 z[i + 1]，所以它的作用是防止越界。A 选项 i < z.length() 在循环里永远为真，等于没写，起不到任何保护作用；C 选项在 i 是最后一个字符时（i + 1 == z.length()）恰好拦住对 z[i + 1] 的访问。应选 C。

2024 年入门级阅读程序第 2 题（爬楼梯）

上一题的代值对象是"填空的选项"，而阅读程序题的小题经常直接问"给定输入，输出是什么"，这类题是代值法的另一片主战场。看 2024 年入门级第一轮阅读程序第 2 题的完整题面：

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

int compute(vector<int>& cost) {
    int n = cost.size();
    vector<int> dp(n+1, 0);
    dp[1] = cost[0];
    for (int i = 2; i <= n; i++) {
        dp[i] = min(dp[i-1], dp[i-2]) + cost[i-1];
    }
    return min(dp[n], dp[n-1]);
}

int main() {
    int n;
    cin >> n;
    vector<int> cost(n);
    for (int i = 0; i < n; i++) {
        cin >> cost[i];
    }
    cout << compute(cost) << endl;
    return 0;
}

判断题

  1. 当输入的 cost 数组为 {10,15,20}\{10, 15, 20\} 时，程序的输出为 1515。（ ）
  2. 如果将 dp[i-1] 改为 dp[i-3]，程序可能会产生编译错误。（ ）
  3. （2 分）程序总是输出 cost 数组中最小的元素。（ ）

单选题

  1. 当输入的 cost 数组为 {1,100,1,1,1,100,1,1,100,1}\{1, 100, 1, 1, 1, 100, 1, 1, 100, 1\} 时，程序的输出为（ ）。

    • A. 6
    • B. 7
    • C. 8
    • D. 9

  2. （4 分）如果输入的 cost 数组为 {10,15,30,5,5,10,20}\{10, 15, 30, 5, 5, 10, 20\}，程序的输出为（ ）。

    • A. 25
    • B. 30
    • C. 35
    • D. 40

  3. 若将代码中的 min(dp[i-1], dp[i-2]) + cost[i-1] 修改为 dp[i-1] + cost[i-2]，输入 cost 数组为 {5,10,15}\{5, 10, 15\} 时，程序的输出为（ ）。

    • A. 10
    • B. 15
    • C. 20
    • D. 25

题目解析

完全不需要读懂这个程序在解决什么问题（它其实是最小代价爬楼梯），只要把输入代进代码、老老实实地跑一遍 dp 表。先做单选题 1：

i 0 1 2 3 4 5 6 7 8 9 10
dp[i] 0 1 100 2 3 103 4 5 104 6

最后返回 min⁡(dp[10],dp[9])=6\min(dp[10], dp[9]) = 6，选择 A。用同样的手法，单选题 2（4 分）代入 cost = {10,15,30,5,5,10,20}\{10, 15, 30, 5, 5, 10, 20\} 手算出 30，单选题 3 把递推式改掉后再代入 {5,10,15}\{5, 10, 15\} 手算出 10——三道单选全都不需要读懂题意，只靠代值就能拿下 10 分；判断题 1 也是同一招，把 {10,15,20}\{10, 15, 20\} 代一遍得到 15，判断为正确，又得 1.5 分。

总结

很多人觉得自己读懂了，想当然地选择了其它答案。但是实际上我们只需要随便设置一个输入，代入程序里进行计算，将四个选项分别代进去尝试就可以通过排除法来获得答案。这就是代值法——如果我们知道题意，那么给定输入肯定可以手算输出。我们将输入给到程序中，把 ABCD 四个选项分别代入进去尝试，看看哪一个选项的答案可以和手算的正确输出保持一致，哪个选项就是正确的。如果运算量不大，建议使用代值法进行验算。

假设使用代值法的时候遇到了排除不掉的答案，例如第 1 空这样 A、C 两个选项都正确的情况，我们可以尝试进行更多的代值，使用不同的输入进行尝试。如果换输入还是排除不掉，说明两个选项在功能上等价，此时应当回到代码，观察它们在语义上的差别（如本例中"有边界检查"与"没有边界检查"的差别），优先选择逻辑更严密、更有存在意义的那个选项。此外，代值法对阅读程序题同样好使：题干直接问输出的小题，把输入代进代码跑一遍表，答案自然出现（见上面的爬楼梯题），往往比读懂程序快得多。

代值法是所有方法中最重要的方法，在后面几种方法的讲解中，本方法将作为一个基础方法直接使用，不再赘述。

二、读题法

对于程序阅读的题目，通常会有一些提示。而提示里面就隐藏着做题的方法，首先看下面这道真题。这是一道交互式问题，很多同学平时没见过这种题型，看到"你无需关心 query 函数的内部实现"就慌了神，读不懂题就全蒙。事实上本题题干给了非常详尽的提示，甚至手把手演示了一遍"消除"的过程，只要认真读提示，5 道题可以全部做对。

2025 年入门级完善程序第 2 题（精明与糊涂）

（精明与糊涂）有 NN 个人，分为两类： i) 精明人：永远能正确判断其他人是精明还是糊涂； ii) 糊涂人：判断不可靠，会给出随机的判断。

已知精明人严格占据多数，即如果精明人有 kk 个，则满足 k>N/2k > N/2。

你只能通过函数 query(i,j)\text{query}(i, j) 让第 ii 个人判断第 jj 个人：返回 true\text{true} 表示判断结果为"精明人"；返回 false\text{false} 表示判断结果为"糊涂人"。你的目标是，通过这些互相判断，找出至少一个百分之百确定的精明人。同时，你无需关心 query(i,j)\text{query}(i, j) 的内部实现。

以下程序利用"精明人占多数"的优势。设想一个"消除"的过程，让人们互相判断并进行抵消。经过若干轮抵消后，最终留下的候选人必然属于多数派，即精明人。

例如，假设有三人 0,1,20, 1, 2。如果 00 说 11 是糊涂人，而 11 也说 00 是糊涂人，则 00 和 11 至少有一个是糊涂人。程序将同时淘汰 00 和 11。由于三人里至少有两个精明人，我们确定 22 是精明人。

试补全程序。

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

int N;
bool query(int i, int j);

int main() {
    cin >> N;

    int candidate = 0;
    int count = ①;
    for (int i = 1; i < N; ++i) {
        if (②) {
            candidate = i;
            count = 1;
        } else {
            if (③) {
                ④;
            } else {
                count++;
            }
        }
    }
    cout << ⑤ << endl;
    return 0;
}

  1. ①处应填

    • A. 0
    • B. 1
    • C. N
    • D. -1

  2. ②处应填

    • A. count < 0
    • B. count == 1
    • C. count == 0
    • D. query(candidate, i) == false

  3. ③处应填

    • A. query(candidate, i) == false
    • B. query(i, candidate) == true
    • C. query(candidate, i) == false && query(i, candidate) == false
    • D. query(candidate, i) == false || query(i, candidate) == false

  4. ④处应填

    • A. count--
    • B. break
    • C. count++
    • D. candidate = i

  5. ⑤处应填

    • A. N - 1
    • B. count
    • C. candidate
    • D. 0

题目解析

既然给了提示就一定要看，这是最基本的做题思路。把题干提示里的关键词圈出来："消除"、"互相判断并进行抵消"、"最终留下的候选人必然属于多数派，即精明人"。把这三个词逐一映射到代码上，五道题全部能填：

  • 提示说"最终留下的候选人"，所以代码最后输出的是候选人，⑤ 选 C（candidate）。B 选项 count 是票数不是人，排除。

  • 程序从 0 号开始，把 0 号定为第一个候选人，此时他独占一票，所以 ① 选 B（count = 1）。

  • "抵消"到什么时候要换候选人？当然是票数抵消光了（count == 0）的时候，② 选 C。count < 0 在程序中根本不会出现；count == 1 只是恰好还剩一票，不代表该换人。

  • 什么时候发生"抵消"？看提示里的例子："如果 0 说 1 是糊涂人，而 1 也说 0 是糊涂人，则 0 和 1 至少有一个是糊涂人"。把它推广一步：其实只要任意一方说对方是糊涂人，这两个人里就至少有一个糊涂人——如果发言的人是精明人，那被说的那个人就是糊涂人；如果发言的人是糊涂人，那发言的人本身就是糊涂人。把这样一对人同时淘汰（抵消一票），精明人的多数地位不会受损。这段推理可以列成一张真值表：

说"对方是糊涂人"的人 他是精明人 他是糊涂人
结论 被说的那个人必是糊涂人 他自己就是糊涂人

两种情况都保证这一对里至少有一个糊涂人，抵消掉这一对不会让精明人失去多数。所以 ③ 用"或"连接两个方向的判断，选 D；④ 抵消就是 count--，选 A。

  • 为什么不选 A（只听候选人单方面的判断）？如果候选人是糊涂人，他的判断是随机的，可能把糊涂人认作精明人而误加票，票数被污染，最后留下的就未必是多数派了。只有双向都问，精明的那一方才会如实指控对方，抵消才可靠。
  • 为什么不选 C（两个方向都指控才淘汰）？"任一方指控"已经保证两人中至少有一个糊涂人。典型情形是精明人指控糊涂人：只有一方在指控，按 C 就不淘汰、反而 count++，等于把糊涂人拉进了阵营，票数被污染，最终留下的人就不可信了。
  • 双方都认为对方是精明人（两个 query 都是 true）时走 count++ 分支：没有指控，就没有理由淘汰，i 计入候选人的阵营。这同样来自提示描述的"抵消"过程的另一半。

五道题全部来自对提示的逐句翻译，根本不需要懂 query 函数怎么实现。

2022 年入门级完善程序第 2 题（洪水填充）

如果说"精明与糊涂"的提示还需要动一点脑子，"洪水填充"这道 2022 年入门级完善程序第 2 题就是读题法的极致形态：五个空与题干描述几乎是一一对应的逐句直译。

（洪水填充）现有用字符标记像素颜色的 8×88\times 8 图像。颜色填充的操作描述如下：给定起始像素的位置待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同），替换为给定的颜色。

试补全程序。

#include<bits/stdc++.h>
using namespace std;

const int ROWS = 8;
const int COLS = 8;

struct Point {
    int r, c;
    Point(int r, int c): r(r), c(c) {}
};

bool is_valid(char image[ROWS][COLS], Point pt,
              int prev_color, int new_color) {
    int r = pt.r;
    int c = pt.c;
    return (0 <= r && r < ROWS && 0 <= c && c < COLS &&
            ① && image[r][c] != new_color);
}

void flood_fill(char image[ROWS][COLS], Point cur, int new_color) {
    queue<Point> queue;
    queue.push(cur);

    int prev_color = image[cur.r][cur.c];
    ②;

    while (!queue.empty()) {
        Point pt = queue.front();
        queue.pop();

        Point points[4] = {③, Point(pt.r - 1, pt.c),
                           Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};
        for (auto p : points) {
            if (is_valid(image, p, prev_color, new_color)) {
                ④;
                ⑤;
            }
        }
    }
}

int main() {
    Point cur(4, 4);
    char new_color = 'y';

    flood_fill(image, cur, new_color);
    for (int r = 0; r < ROWS; r++) {
        for (int c = 0; c < COLS; c++) {
            cout << image[r][c] << ' ';
        }
        cout << endl;
    }
    return 0;
}

  1. ①处应填

    • A. image[r][c] == prev_color
    • B. image[r][c] != prev_color
    • C. image[r][c] == new_color
    • D. image[r][c] != new_color

  2. ②处应填

    • A. image[cur.r+1][cur.c] = new_color
    • B. image[cur.r][cur.c] = new_color
    • C. image[cur.r][cur.c+1] = new_color
    • D. image[cur.r][cur.c] = prev_color

  3. ③处应填

    • A. Point(pt.r, pt.c)
    • B. Point(pt.r, pt.c+1)
    • C. Point(pt.r+1, pt.c)
    • D. Point(pt.r+1, pt.c+1)

  4. ④处应填

    • A. prev_color = image[p.r][p.c]
    • B. new_color = image[p.r][p.c]
    • C. image[p.r][p.c] = prev_color
    • D. image[p.r][p.c] = new_color

  5. ⑤处应填

    • A. queue.push(p)
    • B. queue.push(pt)
    • C. queue.push(cur)
    • D. queue.push(Point(ROWS, COLS))

题目解析

题干里的每一个短语都能在代码里找到对应的空：

  • "终点和路径上所有像素的颜色都与起始像素颜色相同" → 一个像素能不能被填色，先要看它的颜色是否还是起始颜色 prev_color，① 选 A（image[r][c] == prev_color）。B 与定义相反；C 要求像素已经是新颜色才合法，没填过的像素反而过不了检查，显然错；D 与同一行末尾的 image[r][c] != new_color 重复。
  • "将起始像素……替换为给定的颜色" → 进入搜索前先把起点染色，② 选 B。A、C 染的是起点的邻居；D 把起点染回旧颜色，都不符合"替换为给定颜色"。
  • "经过……上、下、左、右四个方向移动" → ③ 在枚举四个邻居：已有上 Point(pt.r-1, pt.c)、右 Point(pt.r, pt.c+1)、左 Point(pt.r, pt.c-1)，缺下，选 C（Point(pt.r+1, pt.c)）。
  • "替换为给定的颜色" → 合法的邻居像素 p 染成 new_color，④ 选 D。
  • 填完色还要从 p 继续向外扩散，把 p 压入队列，⑤ 选 A。B 把刚弹出的队首又塞回队列、C 把起点反复入队，都是同一个毛病——真正要继续扩散的像素 p 没有入队，填充传不出去，图像填不完；D 把越界的 (8,8) 入队，检查必然失败，更离谱。

另外注意，本题原题代码的注释里还附上了填充后的完整输出图像（本文代码从略）——考场上填完五个空，拿它验算一遍即可，这又是出题人白送的提示。

总结

"精明与糊涂"靠的是把提示里的"消除、抵消、最终留下的候选人"翻译成代码；"洪水填充"则更直接——题干定义的每个短语都对应一个空，逐句直译就能拿满 15 分。这就是读题法：完善程序题的题干提示不是装饰，出题人把"程序在做什么、关键不变量是什么"都写在里面了，把提示翻译成代码就是填空。下次做完善程序题，先读三遍题干再读代码。

三、找规律法

2025 年入门级阅读程序第 2 题（单选 26，3 分）

阅读程序题的特点是没有题目描述，也就是说拿到程序的时候我们根本不知道它在解决一道什么样的问题，这已经具备一定的难度了。下面看 2025 年入门级第一轮阅读程序第 2 题的完整题面与代码：

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
int n, k;
int a[200007];
int ans[200007];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    std::sort(a + 1, a + n + 1);
    n = std::unique(a + 1, a + n + 1) - a - 1;
    for (int i = 1, j = 0; i <= n; ++i) {
        for (; j < i && a[i] - a[j + 1] > k; ++j);
        ans[i] = ans[j] + 1;
    }
    printf("%d\n", ans[n]);
    return 0;
}

判断题

  1. 当输入为 3 1 3 2 1 时，输出结果为 22。（ ）
  2. 假设输入的 nn 为正整数，输出的答案一定小于等于 nn，大于等于 11。（ ）
  3. 将第 14 行的 n = std::unique(a + 1, a + n + 1) - a - 1; 删去后，有可能出现与原本代码不同的输出结果。（ ）

单选题

  1. 假设输入的 aa 数组和 kk 均为正整数，执行第 18 行代码时，一定满足的条件不包括（ ）。

    • A. j<ij < i
    • B. a[i]−a[j]>ka[i] - a[j] > k
    • C. j<nj < n
    • D. a[j]<a[i]a[j] < a[i]

26.（本题，3 分）当输入的 n=100n=100、k=2k=2、a={1,2,…,100}a = \{1, 2, \dots, 100\} 时，输出为（ ）。

- A. 34
- B. 100
- C. 50
- D. 33

  1. 假设输入的 aa 数组和 kk 均为正整数，但 aa 数组不一定有序，则若误删去第 13 行的 std::sort(a + 1, a + n + 1);，程序有可能出现的问题有（ ）。

    • A. 输出的答案比原本答案更大
    • B. 输出的答案比原本答案更小
    • C. 出现死循环行为
    • D. 以上均可能发生

题目解析

读懂这个程序当然最好（它在做一个贪心分组），但就算一时读不懂，n=100n = 100 的输入也根本无法手算。然而选择题是不需要过程分的：我们先代值小规模的 nn，看输出，然后找规律。

k=2k = 2 且 aa 数组固定为 {1,2,…,n}\{1, 2, \dots, n\} 时，把 nn 从 1 代到 9，逐行模拟代码（运算量很小，几分钟就能算完），得到下表：

输入的 n 1 2 3 4 5 6 7 8 9
输出的结果 1 2 3
相邻输出的差值 0 1 0 1 0

输出序列是 1,1,1,2,2,2,3,3,3,…1, 1, 1, 2, 2, 2, 3, 3, 3, \dots，每 3 个数一组、组号加一，也就是输出 =⌈n/3⌉= \lceil n/3 \rceil。那么 n=100n = 100 时输出为 ⌈100/3⌉=34\lceil 100/3 \rceil = 34，选择 A。

总结

只给 9 个数字可能找出很多种规律，但是本题是选择题，只有 4 个选项，假设你找到了错误的规律，那么很有可能是没有对应的选项的，你可以重新再尝试其它规律。比如猜"每 2 个数一组"会得到 50（C），猜"每 3 个数一组"但外推时错用下取整会得到 33（D）——选项里都备好了坑，把 n=7n = 7 代进代码一验（输出为 3），就知道只有周期 3 是对的。

2022 年入门级阅读程序第 2 题（单选 5、6，3 分 + 4 分）

这是 2022 年入门级第一轮阅读程序第 2 题，全场公认的难题之一。f 函数是一个"猜楼层丢鸡蛋"式的递归，光看代码很难判断它在解决什么问题，想要读懂它需要花很大代价。先看完整题面，本大题我们只讲单选 5、6 两个小题：

#include <algorithm>
#include <iostream>
#include <limits>

using namespace std;

const int MAXN = 105;
const int MAXK = 105;

int h[MAXN][MAXK];

int f(int n, int m)
{
    if (m == 1) return n;
    if (n == 0) return 0;

    int ret = numeric_limits<int>::max();
    for (int i = 1; i <= n; i++)
        ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
    return ret;
}

int g(int n, int m)
{
    for (int i = 1;i <= n; i++)
        h[i][1]= i;
    for (int j = 1;j<= m; j++)
        h[0][j]= 0;

    for (int i= 1; i <= n; i++){
        for (int j= 2; j <= m; j++){
            h[i][j] = numeric_limits<int>::max();
            for (int k = 1;k <= i;k++)
            h[i][j]= min(
                h[i][j],
                max(h[i - k][j],h[k - 1][j - 1]) +1);
        }
    }

    return h[n][m];
}

int main()
{
    int n,m;
    cin >> n>> m;
    cout << f(n, m) << endl << g(n, m)<< endl;
    return 0;
}

判断题

  1. 当输入为 7 3 时，第 19 行用来取最小值的 min 函数执行了 449449 次。（ ）
  2. 输出的两行整数总是相同的。（ ）
  3. 当 mm 为 11 时，输出的第一行总为 nn。（ ）

单选题

  1. 算法 g(n,m)g(n,m) 最为准确的时间复杂度分析结果为（ ）。

    • A. O(n3/2m)O(n^{3/2}m)
    • B. O(nm)O(nm)
    • C. O(n2m)O(n^{2}m)
    • D. O(nm2)O(nm^{2})

5.（3 分）当输入为 20 2 时，输出的第一行为（ ）。

  • A. 4
  • B. 5
  • C. 6
  • D. 20

6.（4 分）当输入 100 100 时，输出的第一行为（ ）。

  • A. 6
  • B. 7
  • C. 8
  • D. 9

题目解析

20 个、100 个楼层，双层循环的递归显然无法手算到底。但 nn 很小时是可以手算的，我们就先算小规模输入，然后找规律。

先看 f(n,2)f(n, 2)。n=1n = 1 时 i 只能取 1，f(1,2)=max⁡(f(0,2),f(0,1))+1=1f(1,2) = \max(f(0,2), f(0,1)) + 1 = 1；n=2n = 2 时两种方案：i=1i=1 得 max⁡(f(1,2),f(0,1))+1=2\max(f(1,2), f(0,1)) + 1 = 2，i=2i=2 得 max⁡(f(0,2),f(1,1))+1=2\max(f(0,2), f(1,1)) + 1 = 2，取最小为 2；n=3n = 3 时三种方案：i=1i=1 得 max⁡(f(2,2),f(0,1))+1=3\max(f(2,2), f(0,1)) + 1 = 3，i=2i=2 得 max⁡(f(1,2),f(1,1))+1=2\max(f(1,2), f(1,1)) + 1 = 2，i=3i=3 得 max⁡(f(0,2),f(2,1))+1=3\max(f(0,2), f(2,1)) + 1 = 3，取最小为 2。依此类推，慢慢能算出：

输入的 n 1 2 3 4 5 6 7 ...
f(n,2)f(n, 2) 的值 1 2 3 4 ...

规律：1 出现 1 次，2 出现 2 次，3 出现 3 次，4 出现 4 次……第 kk 组的长度为 kk。也就是 f(n,2)f(n, 2) 是使 1+2+⋯+k≥n1 + 2 + \cdots + k \geq n 成立的最小 kk。f(20,2)f(20, 2)：1+2+3+4+5=15<201+2+3+4+5 = 15 < 20，再加 6 得到 21≥2021 \geq 20，所以 f(20,2)=6f(20,2) = 6，选择 C。

再看 f(n,100)f(n, 100)：mm 从 2 变成 100，规律会不会变？同样从小代起（需要顺带算出 f(i,99)f(i, 99) 的中间值，计算量稍大，耐心代到 n=8n = 8 也就够了）：f(1,100)=1f(1,100) = 1，f(2,100)=2f(2,100) = 2，f(3,100)=2f(3,100) = 2，f(4,100)=3f(4,100) = 3，f(5,100)=3f(5,100) = 3，f(6,100)=3f(6,100) = 3，f(7,100)=3f(7,100) = 3，f(8,100)=4f(8,100) = 4。画出表：

输入的 n 1 2 3 4 5 6 7 8
f(n,100)f(n, 100) 的值 1 2 3 4

规律：1 出现 1 次，2 出现 2 次，3 出现 4 次，4 出现 8 次……第 kk 组的长度为 2k−12^{k-1}。也就是说 f(n,100)f(n, 100) 是使 2k−1≥n2^k - 1 \geq n 成立的最小 kk。f(100,100)f(100, 100)：26−1=63<100≤127=27−12^6 - 1 = 63 < 100 \leq 127 = 2^7 - 1，所以答案是 7，选择 B。当然，这里只有 4 组数据点，"第 kk 组长度为 2k−12^{k-1}"还只是个猜测——正是因为有选项兜底（外推的 7 恰好是选项之一），这 4 分才敢落袋；如果外推的结果不在选项里，就要回头换一种规律。

两道 3 分、4 分的大题，只靠代值小数据 + 找规律就稳稳拿下，不必读懂"鸡蛋掉落"的来龙去脉。

总结

这两个例子展示了找规律法的两种形态：周期规律（2025 年题）与分组长度递增规律（2022 年题）。它的流程永远是三步：① 把输入换成小规模数据，老老实实代值手算；② 把输出排成表格，找差值或分组规律；③ 外推到题目要的大规模输入。如果外推出的数不在选项里，说明规律找错了，换一种再试——选项就是现成的验算器。

结语

再次提醒，答题技巧仅作为面向难题时实在不会做的备用方案，通过初赛的本质还是要提升自己的程序能力，如果只一味想着蒙选择题，即使通过了初赛也无法在复赛拿到好的成绩。

分类: 分享 · 更新时间 2026-9-9 14:57:51