简介《2024年信息学奥赛CSP-J初赛真题详细分析》面向备战CSP-J初赛的中学生、少儿编程学习者及辅导教师围绕2024年初赛真题答案与考点梳理帮助读者从零散刷题转向按知识模块复盘。压缩包仅含1个docx文档约121KB篇幅集中便于打印、标注和检索。文档逐题给出答案与解析并延伸整理32位int存储范围、进制与存储单位换算、二分查找比较次数、无向图度数性质、二叉树前中后序遍历、栈的出栈序列判断、排列组合捆绑法与编译器作用等高频知识点兼顾C基本数据类型、控制结构和操作系统常识。已有2594人学习适合用于考前查漏补缺、课堂讲评和错题归因也可作为教师组织专题复习的参考材料。1. 2024 年信息学奥赛 CSP-J 初赛真题别急着从第一题往下做2024 年信息学奥赛 CSP-J 初赛真题与解析这份资源最大价值是它把入门组第一轮的考点摊成一张清晰的清单15 道单选考记忆与推导3 组阅读程序考代码跟踪2 组完善程序考结构还原42 个空位背后对应的是 int 边界、进制换算、组合计数、栈与二叉树、素数判定、递归与动态规划这几块硬骨头。它适合三类人刚学完 C 语法准备第一次参赛的学生、带孩子刷题但自己讲不清原理的教练、以及想快速摸清入门组难度水位再决定要不要投入的家长。整套材料最大的用处是当“诊断表”把不会的题按知识点归类再回头补对应的代码能力。2. 选择题的六类解法从 int 边界到组合分类的固定套路单选 15 题看着杂实际归成六类存储与编码、进制混算、组合计数、数据结构性质、语言细节、编译原理常识。每一类都有固定解法背答案没用记住“从哪一步开始推”才有用。2.1 int 的存储范围与存储单位换算32 位 int 占 4 个字节用补码表示范围是 $-2^{31}$ 到 $2^{31}-1$也就是 -2147483648 到 2147483647。这道题真正容易出问题的不是范围本身而是负端比正端多一个数——负端能取到 -2147483648正端取不到 2147483648。选项里一旦出现“两端对称”的写法基本可以排除。存储换算那道题考的是链条1MB 1024KB1KB 1024B1B 8bit所以 1MB 1024×1024×8 8388608 bit。很多人卡在“1Kb 是 1024 字节”这句表述上把 Kb 和 KB 混了注意题面里小写 b 常指 bit、大写 B 指 byte但这里题干已经明确说了 1Kb 位 1024 字节按题干走。单位换算关系折算成 bit1 B8 bit81 KB1024 B81921 MB1024 KB83886081 GB1024 MB8589934592写段代码把边界打出来比背十遍都牢#include climits #include iostream using namespace std; int main() { cout sizeof(int) sizeof(int) 字节 endl; cout INT_MIN INT_MIN endl; // -2147483648 cout INT_MAX INT_MAX endl; // 2147483647 // 注意INT_MIN 不能写成 -2147483648 直接赋给 int 常量做运算 // 该字面量在 C 里是 long long 类型比较时容易出意外 long long mb 1024LL * 1024 * 8; cout 1MB mb bit endl; // 8388608 return 0; }这段代码做了两件事用sizeof确认当前平台 int 宽度用climits拿到真实边界值。参数上唯一要留意的是INT_MIN的写法——直接写字面量-2147483648在部分编译器里会被当成long long处理做位运算或取绝对值时会翻车标准做法是先取INT_MAX再减一或者直接用宏。2.2 进制混算先全部落成十进制再动笔(148 − 1010₂) × D₁₆ − 1101₂ 这种题错误几乎都出在“边算边转”。正确流程是三步识别每个数的进制、全部转成十进制、按优先级算。148 是八进制等于 121010₂ 等于 10D₁₆ 等于 131101₂ 等于 13于是 (12−10)×13−13 26−13 13。识别进制的线索只有三个数字右下角的下标、前缀0x / 0b、以及数字里出现的最大字符。八进制里出现 8 或 9 就是错的十六进制里出现 A~F 就一定是十六进制。下面这段手写解析函数把这三条规则落成代码#include iostream #include string using namespace std; // 把任意 2~16 进制的字符串转成十进制非法字符返回 -1 long long toDec(const string s, int base) { long long v 0; for (char c : s) { int d; if (c 0 c 9) d c - 0; else if (c A c F) d c - A 10; else if (c a c f) d c - a 10; else return -1; if (d base) return -1; // 该位超出了进制上限 v v * base d; // 逐位累乘累加 } return v; } int main() { long long a toDec(14, 8); // 八进制 14 - 12 long long b toDec(1010, 2); // 二进制 - 10 long long c toDec(D, 16); // 十六进制 - 13 long long d toDec(1101, 2); // 二进制 - 13 cout (a - b) * c - d endl; // 13 return 0; }base参数就是进制数v v * base d是 Horner 形式的逐位累加比“按位乘权再求和”少一次循环内的幂运算。if (d base) return -1;这句是安全检查防止把19当八进制解析出错误结果却不自知。2.3 组合计数分类加法比容斥更稳10 人分 3 个部门4/3/3选 4 人且每部门至少 1 人。4 人分到 3 个部门、每部门至少 1 人只有一种分布211。所以按“哪个部门出 2 人”分三类再相加A 部门出 2 人C(4,2)×C(3,1)×C(3,1) 6×3×3 54B 部门出 2 人C(4,1)×C(3,2)×C(3,1) 4×3×3 36C 部门出 2 人C(4,1)×C(3,1)×C(3,2) 4×3×3 36合计 126。这里最容易犯的错是先算 C(10,4)210 再减掉不合法的减法路径要考虑“某部门 0 人”的重复计数容斥写漏一项就废。分类加法虽然慢但每一类互斥且完备几乎不会错。捆绑法那道同理3 个女生必须相邻把 3 人捆成一个整体与 5 个男生共 6 个对象全排列 6! 720内部 3! 6乘起来 4320。判断用捆绑还是插空只需要一句要求“相邻”就捆绑要求“不相邻”就插空。写个暴力枚举验证一下 126比盯着公式自信更靠谱#include iostream using namespace std; int main() { // 下标 0~3 属 A 部门4~6 属 B 部门7~9 属 C 部门 int dept[10] {0,0,0,0, 1,1,1, 2,2,2}; int ans 0; for (int mask 0; mask (1 10); mask) { if (__builtin_popcount(mask) ! 4) continue; // 只取 4 人 int c[3] {0, 0, 0}; for (int i 0; i 10; i) if (mask i 1) c[dept[i]]; // 统计各部门人数 if (c[0] 1 c[1] 1 c[2] 1) ans; } cout ans endl; // 126 return 0; }mask的每一位代表一个人是否入选__builtin_popcount数 1 的个数c[dept[i]]按部门归类。这个模板可以直接套到任何“从固定集合里选若干且满足约束”的题上规模在 20 人以内都能秒出结果用来验算比手推快得多。2.4 格雷码、二叉树与栈三道靠规律不靠计算的题格雷码那题的正确选项是 0000、0001、0011、0010、0110、0111、0101、0100。判定方法只有一条相邻两个码必须只差一位。逐对做异或结果必须是 2 的幂即二进制里只有一个 1。生成规则是 $g(i) i \oplus (i 1)$一位代码就能验证for (int i 0; i 8; i) cout (i ^ (i 1)) ; // 0 1 3 2 6 7 5 4二叉树由前序 [A,B,D,E,C,F,G] 和中序 [D,B,E,A,F,C,G] 求后序方法是递归找根前序第一个 A 是根在中序里把序列切成左 [D,B,E] 和右 [F,C,G]左子树的根是 B右子树的根是 C继续切。最终后序是 D,E,B,F,G,C,A。这套“前序定根、中序分左右”的流程写出来只有十几行#include iostream #include string using namespace std; string post; // 存放后序结果 // pre/in 为当前子树的前序与中序片段 void build(const string pre, const string in) { if (pre.empty()) return; char root pre[0]; // 前序首位即根 int pos in.find(root); // 根在中序中的位置 build(pre.substr(1, pos), in.substr(0, pos)); // 递归左子树 build(pre.substr(pos 1), in.substr(pos 1)); // 递归右子树 post.push_back(root); // 左右都处理完再输出根 } int main() { build(ABDECFG, DBEAFCG); cout post endl; // DEBFGCA return 0; }pos是中序里根的下标同时也正好等于左子树的节点个数所以pre.substr(1, pos)取左子树前序、pre.substr(pos1)取右子树前序。最后一行post.push_back(root)的位置决定了这是后序——想改成前序或中序只要挪这一行的位置。栈的出栈序列题只能靠模拟。判断标准是出栈序列里的某个元素出栈时比它后进栈的元素必须已经按逆序出完。选项 1 3 5 2 4 6 不可能因为 5 出栈后栈里 2、4 的顺序被迫颠倒。写个几十行的模拟器能一次性把这类题全部验掉。剩下的选择题是纯记忆点struct 是复合类型不是基本类型C 只有 for/while/do-while 三种循环没有 repeat-untila13 是 nNotepad 是文本编辑器不是操作系统无向图所有顶点度数之和等于边数的两倍有序表 1000 个元素二分查找最多比较 ⌈log₂1000⌉ 10 次编译器的作用是把源代码翻译成机器码。这些点没有推导空间看到就记记不住就写代码验证一次。3. 阅读程序题手推三件套素数判定、线性 DP 与快速幂递归阅读程序是初赛的分水岭题目给一段完整代码问输出或判断结论对错。这类题的核心不是读懂每一行而是找到“哪个参数会改变结果”。3.1 素数统计循环上界决定一切第一组程序的骨架是isPrime试除到 $\sqrt{n}$外层两个函数分别统计个数和求和#include iostream using namespace std; bool isPrime(int n) { if (n 1) return false; // 0 和 1 不是素数 for (int i 2; i * i n; i) { // 只需试除到 sqrt(n) if (n % i 0) return false; } return true; } // 统计 2..n 中素数个数 int countPrimes(int n) { int count 0; for (int i 2; i n; i) if (isPrime(i)) count; return count; } // 统计 2..n 中素数之和 int sumPrimes(int n) { int sum 0; for (int i 2; i n; i) if (isPrime(i)) sum i; return sum; } int main() { int x; cin x; cout countPrimes(x) sumPrimes(x) endl; return 0; }输入 10 时2~10 的素数是 2、3、5、7四个和是 17输出 “4 17”。输入 50 时素数是 2、3、5、7、11、13、17、19、23、29、31、37、41、43、47共 15 个逐个累加得 328——这正是选项里的 B。关键改动题在第 17 题把i * i n改成i n / 2问输入 20 时countPrimes(20)会不会变成 6。答案是不会仍然是 8。原因是 $n/2 \ge \sqrt{n}$对 $n \ge 4$ 恒成立上界只是被放大试除的判定结果一个都没变只是白跑了一些循环。这个点很容易凭直觉选“变”实际要靠“上界放大不改变正确性、只改变效率”这条结论顶住。第 20 题改的是另一个方向i n。这时候i会一路取到nn % n 0必然成立函数对所有大于 1 的数都返回 false于是 10 以内的素数一个都统计不到输出 “0 0”程序不能正确工作。同一道题三种改法结论分别是不变、结果错、效率低分清楚这三者的区别是这道题的全部价值。参数说明上i * i n里的乘法在n接近 int 上限时可能溢出工业写法一般是i n / i或者把i开成long long。初赛代码不会考这么细但你自己写题解时踩到一次就记住了。3.2 线性 DP把一行转移式摊成一张表第二组程序考的是“爬楼梯”型 DP转移式在题干里给的是dp[i] min(dp[i-1], dp[i-2]) cost[i-1]。纸面推演的正确姿势不是从dp[0]硬算到dp[n]而是画一张三列表下标、两个候选值、取小之后加 cost 的结果。假设 cost {1, 100, 1, 1, 1, 100, 1, 1, 100, 1}按dp[0]0, dp[1]cost[0]1起步idp[i-2]dp[i-1]cost[i-1]dp[i]20110010031100124100213523136331001037310314810341594510010410510416表一画完min每次取谁、cost 的下标为什么是i-1全都摆在明面上。这类题翻车的唯二原因是初值写错、输出下标取错程序最后cout的是dp[n]还是dp[n-1]必须回头看 main 的最后一行别凭印象。下面是一个通用的爬楼梯 DP 骨架把三个易错点都标出来了#include iostream #include vector using namespace std; int main() { vectorint cost {1, 100, 1, 1, 1, 100, 1, 1, 100, 1}; int n cost.size(); vectorint dp(n 1, 0); dp[0] 0; // 起点不付代价 dp[1] cost[0]; // 走上第一阶必须付 cost[0] for (int i 2; i n; i) { // 从 i-1 或 i-2 走过来取花费小的那条再加本阶代价 dp[i] min(dp[i - 1], dp[i - 2]) cost[i - 1]; } cout dp[n] endl; // 输出下标要和题目要求对齐 return 0; }dp数组开到n1是因为要存dp[n]dp[1] cost[0]这个初值不能想当然写 0否则第一阶免费答案整体偏小cost[i-1]而不是cost[i]是因为dp的下标比cost领先一位。这三处是同一道题在十年里反复改头换面考的东西。如果题目改转移式比如把min(dp[i-1],dp[i-2])换成别的组合手推表的列名要跟着换但“先列表再对答案”的流程不变。带一张草稿纸进考场比在脑子里空转稳得多。3.3 递归展开快速幂为什么 b 越大越慢第三组程序是快速幂的递归写法。骨架是b 0返回 1b为偶数时先算 $a^{b/2}$ 再平方b为奇数时拆成 $a \times a^{b-1}$。输入 5 4过程是 $5^4 (5^2)^2 25^2 625$返回 625。递归层数就是这道题所有判断题的答案来源$b$ 每次减半层数是 $O(\log b)$所以“b 越大运行时间越长”这句话成立只是增长得很慢。b为负数时C 的整数除法向零取整-1 / 2等于 0b不会稳定收敛到 0 的出口递归会陷进去——这一条在题里以判断题形式出现实际写代码时也确实是坑负数幂要么特判要么直接拒绝。#include iostream using namespace std; long long cnt 0; // 统计递归调用次数 long long power(long long a, long long b) { cnt; if (b 0) return 1; // 递归出口 if (b % 2 1) return a * power(a, b - 1); // 奇数拆一个 a 出来 long long t power(a, b / 2); // 偶数折半只算一次 return t * t; // 结果平方避免重复计算 } int main() { cout power(5, 4) endl; // 625 cout 调用次数 cnt endl; cout power(2, 20) endl; // 1048576 return 0; }long long t power(a, b / 2); return t * t;这两行是快速幂的全部精髓——把子问题的结果存下来复用而不是写成power(a,b/2) * power(a,b/2)后者会把 $O(\log b)$ 直接退化成 $O(b)$。参数上把返回值和中间量都开成long long是因为 $2^{20}$ 还在 int 内$2^{40}$ 就溢出了递归题里溢出不报错、只给错答案最难查。手推递归题有个笨办法但极其有效在纸上画调用树每个节点写“参数 → 返回值”画到叶子再往回填。三层以内都能画完画完答案自己就浮出来了。4. 完善程序的两条骨架完全平方数判定与汉诺塔递归参数序完善程序题给一段挖了空的代码每空四个选项。这类题不需要你从零写只需要判断“这一行在这个位置应该承担什么职责”。4.1 完全平方数上界为什么必须是 sqrt第一题判断正整数 n 是不是完全平方数骨架是从 1 枚举到 $\lfloor\sqrt{n}\rfloor$看有没有 $i^2 n$。五个空分别对应枚举起点i 1、上界(int)floor(sqrt(num))、判断条件num i*i、命中返回true、循环走完返回false。上界这一空最容易错在写成num / 2。num/2虽然也能跑出正确结果因为超过 $\sqrt{n}$ 的因子一定配对出现但循环次数从 $\sqrt{n}$ 涨到 $n/2$n 大一点就超时而且num/2在num 1时退化成 0循环一次都不进直接返回 false边界就崩了。#include iostream #include cmath using namespace std; bool isSquare(int num) { int i 1; // 从 1 开始枚举 int bound (int)floor(sqrt(num)); // 上界取 sqrt别用 num/2 for (; i bound; i) { if (num i * i) { // 判断用 而不是 return true; } } return false; // 循环走完都没命中 } int main() { int n; cin n; if (isSquare(n)) cout n is a Square number endl; else cout n is not a Square number endl; return 0; }(int)floor(sqrt(num))这一串里sqrt返回浮点数直接截断成 int 在某些平台上会因为浮点误差把 25 算成 4.9999 截成 4多加一层floor是为了显式向下取整避免“本该是 5 却变成 4”的血泪经验。判断条件必须是num i*i写成单个是把赋值当比较编译器可能只给个警告运行起来恒为真第一轮就返回 true。4.2 汉诺塔四个参数的语义必须一次记死第二题是汉诺塔函数签名dfs(int i, char src, char tmp, char tgt)的语义是“把 i 个盘子从 src 借助 tmp 移到 tgt”。三步分解把上面 i−1 个盘子从 src 移到 tmp借助 tgt →dfs(i-1, src, tgt, tmp)把最底下那个大盘从 src 移到 tgt →move(src, tgt)把 i−1 个盘子从 tmp 移到 tgt借助 src →dfs(i-1, tmp, src, tgt)出口是i 1时直接move(src, tgt)。这道题五个空里真正决定成败的是第一和第三个递归调用的参数顺序——名字记住了没用得记住“第二个参数永远是起点、第四个永远是终点、第三个永远是中转站”中间那个参数在三步里不断换位是唯一会动的位置。#include iostream using namespace std; void move(char src, char tgt) { cout 从柱子 src 挪到柱子上 tgt endl; } // 把 i 个盘子从 src 借助 tmp 移到 tgt void dfs(int i, char src, char tmp, char tgt) { if (i 1) { // 只剩一个直接搬 move(src, tgt); return; } dfs(i - 1, src, tgt, tmp); // 上面 i-1 个先挪到中转站 move(src, tgt); // 最大盘落到目标柱 dfs(i - 1, tmp, src, tgt); // 中转站那摞再挪到目标柱 } int main() { int n; cin n; dfs(n, A, B, C); return 0; }dfs(i-1, src, tgt, tmp)里第三、四个参数交换是因为此时“目标”变成了“中转”dfs(i-1, tmp, src, tgt)里第二、三个参数交换是因为此时“起点”变成了上一轮的中转站。移动总次数是 $2^n - 1$n3 时 7 步跑一遍输出数一下就知道了。参数语义记不住的时候最省事的办法是在每个递归调用上方写一行中文注释写不出来就说明还没真懂。考场上没时间写注释但平时练习写十遍手指会替你记住。4.3 把两道题扩写成可编译版本再跑一遍完善程序的坑在于“填对了但没跑过”。把两道题补全成完整程序各加三组边界测试n 1、n 2、n 0或者 num 1、num 2、num 4。完全平方数在 num 1 时bound 1i 11 1返回 true正确如果上界写成num/2bound 0循环不进返回 false错。汉诺塔在 n 1 时直接走出口输出一行n 0 时i 1不成立会一路递归到负数栈溢出。原题约束 n 是正整数所以不考这个但自己写题解时加个if (n 0) return;是习惯问题。跑通这两段代码的价值不在于押中题而在于你能拿它当模板判断完全平方数换成判断质数、汉诺塔换成全排列骨架都差不多。5. 避坑与排查五个反复翻车的现场5.1 把试除上界改成 n/2 就以为结果会变现象第 17 题选了“会变成 6”对答案发现是 F实际仍是 8。 原因上界从 $\sqrt{n}$ 放大到 $n/2$只是多跑了循环判定逻辑没变素数还是那几个。 解决记住一条判断准则——上界放大不改变正确性只改变效率只有当上界缩小到不足以覆盖因子时结果才会错。真拿不准就在草稿纸上把 n 20 的循环跑一遍比背结论可靠。5.2 把 struct 当基本类型、把 repeat-until 当 C 循环现象语言细节题连错两题明明平时写过 struct。 原因写代码时用得多但没做过“哪些是关键字、哪些是标准库、哪些是别的语言”的区分。 解决花十分钟翻一遍 C 基本类型清单int、float、double、char、bool、void再翻一遍循环语句for、while、do-while。凡是不在这两个清单里的一律归到“复合类型”或“非 C 语法”。这类题的性价比极高错一次就不该错第二次。5.3 组合计数用容斥漏掉重复计数现象算出 210 或 120选项里恰好有 120直接中招。 原因先 C(10,4) 再减“某部门 0 人”的情况三个部门两两之间的交集被减了两次。 解决凡是“每类至少一个”的题先确定人数分布这里是 211再按“谁出 2 人”分类相加。分类加法每一步互斥写完能自检——三类的系数应该对称54/36/36 就是对称的如果算出三个不一样的数多半分错了。5.4 汉诺塔递归参数抄反程序静默跑完但输出错现象代码能编译能运行输出的移动序列也对得上步数但顺序乱了。 原因dfs(i-1, src, tgt, tmp)写成dfs(i-1, src, tmp, tgt)第三个参数该放中转的地方放了目标。 解决递归题一律先写语义注释再写调用写完把注释念一遍——“把 i−1 个盘子从 src 借助 tgt 移到 tmp”念得通就对念不通就是参数放错了。另外可以加一个断言每次move之后检查大盘不能压小盘用 vector 模拟三根柱子几十行就能把错误暴露出来。5.5 浮点 sqrt 直接比较导致边界误判现象if (sqrt(num) * sqrt(num) num)在 num 25 时偶尔返回 false。 原因sqrt返回 doublesqrt(25)可能算出 4.999999999999999平方后是 24.999999999999996。 解决不要用浮点结果做相等比较。要判断完全平方数就老老实实枚举整数i到floor(sqrt(num))再比i*i num确实要开方就先round再验算一次平方。这条在初赛代码里不一定考但自己写题解时踩一次就够记一辈子。6. 把真题变成训练闭环本文还有配套的精品资源点击获取
简介《2024年信息学奥赛CSP-J初赛真题详细分析》面向备战CSP-J初赛的中学生、少儿编程学习者及辅导教师围绕2024年初赛真题答案与考点梳理帮助读者从零散刷题转向按知识模块复盘。压缩包仅含1个docx文档约121KB篇幅集中便于打印、标注和检索。文档逐题给出答案与解析并延伸整理32位int存储范围、进制与存储单位换算、二分查找比较次数、无向图度数性质、二叉树前中后序遍历、栈的出栈序列判断、排列组合捆绑法与编译器作用等高频知识点兼顾C基本数据类型、控制结构和操作系统常识。已有2594人学习适合用于考前查漏补缺、课堂讲评和错题归因也可作为教师组织专题复习的参考材料。1. 2024 年信息学奥赛 CSP-J 初赛真题别急着从第一题往下做2024 年信息学奥赛 CSP-J 初赛真题与解析这份资源最大价值是它把入门组第一轮的考点摊成一张清晰的清单15 道单选考记忆与推导3 组阅读程序考代码跟踪2 组完善程序考结构还原42 个空位背后对应的是 int 边界、进制换算、组合计数、栈与二叉树、素数判定、递归与动态规划这几块硬骨头。它适合三类人刚学完 C 语法准备第一次参赛的学生、带孩子刷题但自己讲不清原理的教练、以及想快速摸清入门组难度水位再决定要不要投入的家长。整套材料最大的用处是当“诊断表”把不会的题按知识点归类再回头补对应的代码能力。2. 选择题的六类解法从 int 边界到组合分类的固定套路单选 15 题看着杂实际归成六类存储与编码、进制混算、组合计数、数据结构性质、语言细节、编译原理常识。每一类都有固定解法背答案没用记住“从哪一步开始推”才有用。2.1 int 的存储范围与存储单位换算32 位 int 占 4 个字节用补码表示范围是 $-2^{31}$ 到 $2^{31}-1$也就是 -2147483648 到 2147483647。这道题真正容易出问题的不是范围本身而是负端比正端多一个数——负端能取到 -2147483648正端取不到 2147483648。选项里一旦出现“两端对称”的写法基本可以排除。存储换算那道题考的是链条1MB 1024KB1KB 1024B1B 8bit所以 1MB 1024×1024×8 8388608 bit。很多人卡在“1Kb 是 1024 字节”这句表述上把 Kb 和 KB 混了注意题面里小写 b 常指 bit、大写 B 指 byte但这里题干已经明确说了 1Kb 位 1024 字节按题干走。单位换算关系折算成 bit1 B8 bit81 KB1024 B81921 MB1024 KB83886081 GB1024 MB8589934592写段代码把边界打出来比背十遍都牢#include climits #include iostream using namespace std; int main() { cout sizeof(int) sizeof(int) 字节 endl; cout INT_MIN INT_MIN endl; // -2147483648 cout INT_MAX INT_MAX endl; // 2147483647 // 注意INT_MIN 不能写成 -2147483648 直接赋给 int 常量做运算 // 该字面量在 C 里是 long long 类型比较时容易出意外 long long mb 1024LL * 1024 * 8; cout 1MB mb bit endl; // 8388608 return 0; }这段代码做了两件事用sizeof确认当前平台 int 宽度用climits拿到真实边界值。参数上唯一要留意的是INT_MIN的写法——直接写字面量-2147483648在部分编译器里会被当成long long处理做位运算或取绝对值时会翻车标准做法是先取INT_MAX再减一或者直接用宏。2.2 进制混算先全部落成十进制再动笔(148 − 1010₂) × D₁₆ − 1101₂ 这种题错误几乎都出在“边算边转”。正确流程是三步识别每个数的进制、全部转成十进制、按优先级算。148 是八进制等于 121010₂ 等于 10D₁₆ 等于 131101₂ 等于 13于是 (12−10)×13−13 26−13 13。识别进制的线索只有三个数字右下角的下标、前缀0x / 0b、以及数字里出现的最大字符。八进制里出现 8 或 9 就是错的十六进制里出现 A~F 就一定是十六进制。下面这段手写解析函数把这三条规则落成代码#include iostream #include string using namespace std; // 把任意 2~16 进制的字符串转成十进制非法字符返回 -1 long long toDec(const string s, int base) { long long v 0; for (char c : s) { int d; if (c 0 c 9) d c - 0; else if (c A c F) d c - A 10; else if (c a c f) d c - a 10; else return -1; if (d base) return -1; // 该位超出了进制上限 v v * base d; // 逐位累乘累加 } return v; } int main() { long long a toDec(14, 8); // 八进制 14 - 12 long long b toDec(1010, 2); // 二进制 - 10 long long c toDec(D, 16); // 十六进制 - 13 long long d toDec(1101, 2); // 二进制 - 13 cout (a - b) * c - d endl; // 13 return 0; }base参数就是进制数v v * base d是 Horner 形式的逐位累加比“按位乘权再求和”少一次循环内的幂运算。if (d base) return -1;这句是安全检查防止把19当八进制解析出错误结果却不自知。2.3 组合计数分类加法比容斥更稳10 人分 3 个部门4/3/3选 4 人且每部门至少 1 人。4 人分到 3 个部门、每部门至少 1 人只有一种分布211。所以按“哪个部门出 2 人”分三类再相加A 部门出 2 人C(4,2)×C(3,1)×C(3,1) 6×3×3 54B 部门出 2 人C(4,1)×C(3,2)×C(3,1) 4×3×3 36C 部门出 2 人C(4,1)×C(3,1)×C(3,2) 4×3×3 36合计 126。这里最容易犯的错是先算 C(10,4)210 再减掉不合法的减法路径要考虑“某部门 0 人”的重复计数容斥写漏一项就废。分类加法虽然慢但每一类互斥且完备几乎不会错。捆绑法那道同理3 个女生必须相邻把 3 人捆成一个整体与 5 个男生共 6 个对象全排列 6! 720内部 3! 6乘起来 4320。判断用捆绑还是插空只需要一句要求“相邻”就捆绑要求“不相邻”就插空。写个暴力枚举验证一下 126比盯着公式自信更靠谱#include iostream using namespace std; int main() { // 下标 0~3 属 A 部门4~6 属 B 部门7~9 属 C 部门 int dept[10] {0,0,0,0, 1,1,1, 2,2,2}; int ans 0; for (int mask 0; mask (1 10); mask) { if (__builtin_popcount(mask) ! 4) continue; // 只取 4 人 int c[3] {0, 0, 0}; for (int i 0; i 10; i) if (mask i 1) c[dept[i]]; // 统计各部门人数 if (c[0] 1 c[1] 1 c[2] 1) ans; } cout ans endl; // 126 return 0; }mask的每一位代表一个人是否入选__builtin_popcount数 1 的个数c[dept[i]]按部门归类。这个模板可以直接套到任何“从固定集合里选若干且满足约束”的题上规模在 20 人以内都能秒出结果用来验算比手推快得多。2.4 格雷码、二叉树与栈三道靠规律不靠计算的题格雷码那题的正确选项是 0000、0001、0011、0010、0110、0111、0101、0100。判定方法只有一条相邻两个码必须只差一位。逐对做异或结果必须是 2 的幂即二进制里只有一个 1。生成规则是 $g(i) i \oplus (i 1)$一位代码就能验证for (int i 0; i 8; i) cout (i ^ (i 1)) ; // 0 1 3 2 6 7 5 4二叉树由前序 [A,B,D,E,C,F,G] 和中序 [D,B,E,A,F,C,G] 求后序方法是递归找根前序第一个 A 是根在中序里把序列切成左 [D,B,E] 和右 [F,C,G]左子树的根是 B右子树的根是 C继续切。最终后序是 D,E,B,F,G,C,A。这套“前序定根、中序分左右”的流程写出来只有十几行#include iostream #include string using namespace std; string post; // 存放后序结果 // pre/in 为当前子树的前序与中序片段 void build(const string pre, const string in) { if (pre.empty()) return; char root pre[0]; // 前序首位即根 int pos in.find(root); // 根在中序中的位置 build(pre.substr(1, pos), in.substr(0, pos)); // 递归左子树 build(pre.substr(pos 1), in.substr(pos 1)); // 递归右子树 post.push_back(root); // 左右都处理完再输出根 } int main() { build(ABDECFG, DBEAFCG); cout post endl; // DEBFGCA return 0; }pos是中序里根的下标同时也正好等于左子树的节点个数所以pre.substr(1, pos)取左子树前序、pre.substr(pos1)取右子树前序。最后一行post.push_back(root)的位置决定了这是后序——想改成前序或中序只要挪这一行的位置。栈的出栈序列题只能靠模拟。判断标准是出栈序列里的某个元素出栈时比它后进栈的元素必须已经按逆序出完。选项 1 3 5 2 4 6 不可能因为 5 出栈后栈里 2、4 的顺序被迫颠倒。写个几十行的模拟器能一次性把这类题全部验掉。剩下的选择题是纯记忆点struct 是复合类型不是基本类型C 只有 for/while/do-while 三种循环没有 repeat-untila13 是 nNotepad 是文本编辑器不是操作系统无向图所有顶点度数之和等于边数的两倍有序表 1000 个元素二分查找最多比较 ⌈log₂1000⌉ 10 次编译器的作用是把源代码翻译成机器码。这些点没有推导空间看到就记记不住就写代码验证一次。3. 阅读程序题手推三件套素数判定、线性 DP 与快速幂递归阅读程序是初赛的分水岭题目给一段完整代码问输出或判断结论对错。这类题的核心不是读懂每一行而是找到“哪个参数会改变结果”。3.1 素数统计循环上界决定一切第一组程序的骨架是isPrime试除到 $\sqrt{n}$外层两个函数分别统计个数和求和#include iostream using namespace std; bool isPrime(int n) { if (n 1) return false; // 0 和 1 不是素数 for (int i 2; i * i n; i) { // 只需试除到 sqrt(n) if (n % i 0) return false; } return true; } // 统计 2..n 中素数个数 int countPrimes(int n) { int count 0; for (int i 2; i n; i) if (isPrime(i)) count; return count; } // 统计 2..n 中素数之和 int sumPrimes(int n) { int sum 0; for (int i 2; i n; i) if (isPrime(i)) sum i; return sum; } int main() { int x; cin x; cout countPrimes(x) sumPrimes(x) endl; return 0; }输入 10 时2~10 的素数是 2、3、5、7四个和是 17输出 “4 17”。输入 50 时素数是 2、3、5、7、11、13、17、19、23、29、31、37、41、43、47共 15 个逐个累加得 328——这正是选项里的 B。关键改动题在第 17 题把i * i n改成i n / 2问输入 20 时countPrimes(20)会不会变成 6。答案是不会仍然是 8。原因是 $n/2 \ge \sqrt{n}$对 $n \ge 4$ 恒成立上界只是被放大试除的判定结果一个都没变只是白跑了一些循环。这个点很容易凭直觉选“变”实际要靠“上界放大不改变正确性、只改变效率”这条结论顶住。第 20 题改的是另一个方向i n。这时候i会一路取到nn % n 0必然成立函数对所有大于 1 的数都返回 false于是 10 以内的素数一个都统计不到输出 “0 0”程序不能正确工作。同一道题三种改法结论分别是不变、结果错、效率低分清楚这三者的区别是这道题的全部价值。参数说明上i * i n里的乘法在n接近 int 上限时可能溢出工业写法一般是i n / i或者把i开成long long。初赛代码不会考这么细但你自己写题解时踩到一次就记住了。3.2 线性 DP把一行转移式摊成一张表第二组程序考的是“爬楼梯”型 DP转移式在题干里给的是dp[i] min(dp[i-1], dp[i-2]) cost[i-1]。纸面推演的正确姿势不是从dp[0]硬算到dp[n]而是画一张三列表下标、两个候选值、取小之后加 cost 的结果。假设 cost {1, 100, 1, 1, 1, 100, 1, 1, 100, 1}按dp[0]0, dp[1]cost[0]1起步idp[i-2]dp[i-1]cost[i-1]dp[i]20110010031100124100213523136331001037310314810341594510010410510416表一画完min每次取谁、cost 的下标为什么是i-1全都摆在明面上。这类题翻车的唯二原因是初值写错、输出下标取错程序最后cout的是dp[n]还是dp[n-1]必须回头看 main 的最后一行别凭印象。下面是一个通用的爬楼梯 DP 骨架把三个易错点都标出来了#include iostream #include vector using namespace std; int main() { vectorint cost {1, 100, 1, 1, 1, 100, 1, 1, 100, 1}; int n cost.size(); vectorint dp(n 1, 0); dp[0] 0; // 起点不付代价 dp[1] cost[0]; // 走上第一阶必须付 cost[0] for (int i 2; i n; i) { // 从 i-1 或 i-2 走过来取花费小的那条再加本阶代价 dp[i] min(dp[i - 1], dp[i - 2]) cost[i - 1]; } cout dp[n] endl; // 输出下标要和题目要求对齐 return 0; }dp数组开到n1是因为要存dp[n]dp[1] cost[0]这个初值不能想当然写 0否则第一阶免费答案整体偏小cost[i-1]而不是cost[i]是因为dp的下标比cost领先一位。这三处是同一道题在十年里反复改头换面考的东西。如果题目改转移式比如把min(dp[i-1],dp[i-2])换成别的组合手推表的列名要跟着换但“先列表再对答案”的流程不变。带一张草稿纸进考场比在脑子里空转稳得多。3.3 递归展开快速幂为什么 b 越大越慢第三组程序是快速幂的递归写法。骨架是b 0返回 1b为偶数时先算 $a^{b/2}$ 再平方b为奇数时拆成 $a \times a^{b-1}$。输入 5 4过程是 $5^4 (5^2)^2 25^2 625$返回 625。递归层数就是这道题所有判断题的答案来源$b$ 每次减半层数是 $O(\log b)$所以“b 越大运行时间越长”这句话成立只是增长得很慢。b为负数时C 的整数除法向零取整-1 / 2等于 0b不会稳定收敛到 0 的出口递归会陷进去——这一条在题里以判断题形式出现实际写代码时也确实是坑负数幂要么特判要么直接拒绝。#include iostream using namespace std; long long cnt 0; // 统计递归调用次数 long long power(long long a, long long b) { cnt; if (b 0) return 1; // 递归出口 if (b % 2 1) return a * power(a, b - 1); // 奇数拆一个 a 出来 long long t power(a, b / 2); // 偶数折半只算一次 return t * t; // 结果平方避免重复计算 } int main() { cout power(5, 4) endl; // 625 cout 调用次数 cnt endl; cout power(2, 20) endl; // 1048576 return 0; }long long t power(a, b / 2); return t * t;这两行是快速幂的全部精髓——把子问题的结果存下来复用而不是写成power(a,b/2) * power(a,b/2)后者会把 $O(\log b)$ 直接退化成 $O(b)$。参数上把返回值和中间量都开成long long是因为 $2^{20}$ 还在 int 内$2^{40}$ 就溢出了递归题里溢出不报错、只给错答案最难查。手推递归题有个笨办法但极其有效在纸上画调用树每个节点写“参数 → 返回值”画到叶子再往回填。三层以内都能画完画完答案自己就浮出来了。4. 完善程序的两条骨架完全平方数判定与汉诺塔递归参数序完善程序题给一段挖了空的代码每空四个选项。这类题不需要你从零写只需要判断“这一行在这个位置应该承担什么职责”。4.1 完全平方数上界为什么必须是 sqrt第一题判断正整数 n 是不是完全平方数骨架是从 1 枚举到 $\lfloor\sqrt{n}\rfloor$看有没有 $i^2 n$。五个空分别对应枚举起点i 1、上界(int)floor(sqrt(num))、判断条件num i*i、命中返回true、循环走完返回false。上界这一空最容易错在写成num / 2。num/2虽然也能跑出正确结果因为超过 $\sqrt{n}$ 的因子一定配对出现但循环次数从 $\sqrt{n}$ 涨到 $n/2$n 大一点就超时而且num/2在num 1时退化成 0循环一次都不进直接返回 false边界就崩了。#include iostream #include cmath using namespace std; bool isSquare(int num) { int i 1; // 从 1 开始枚举 int bound (int)floor(sqrt(num)); // 上界取 sqrt别用 num/2 for (; i bound; i) { if (num i * i) { // 判断用 而不是 return true; } } return false; // 循环走完都没命中 } int main() { int n; cin n; if (isSquare(n)) cout n is a Square number endl; else cout n is not a Square number endl; return 0; }(int)floor(sqrt(num))这一串里sqrt返回浮点数直接截断成 int 在某些平台上会因为浮点误差把 25 算成 4.9999 截成 4多加一层floor是为了显式向下取整避免“本该是 5 却变成 4”的血泪经验。判断条件必须是num i*i写成单个是把赋值当比较编译器可能只给个警告运行起来恒为真第一轮就返回 true。4.2 汉诺塔四个参数的语义必须一次记死第二题是汉诺塔函数签名dfs(int i, char src, char tmp, char tgt)的语义是“把 i 个盘子从 src 借助 tmp 移到 tgt”。三步分解把上面 i−1 个盘子从 src 移到 tmp借助 tgt →dfs(i-1, src, tgt, tmp)把最底下那个大盘从 src 移到 tgt →move(src, tgt)把 i−1 个盘子从 tmp 移到 tgt借助 src →dfs(i-1, tmp, src, tgt)出口是i 1时直接move(src, tgt)。这道题五个空里真正决定成败的是第一和第三个递归调用的参数顺序——名字记住了没用得记住“第二个参数永远是起点、第四个永远是终点、第三个永远是中转站”中间那个参数在三步里不断换位是唯一会动的位置。#include iostream using namespace std; void move(char src, char tgt) { cout 从柱子 src 挪到柱子上 tgt endl; } // 把 i 个盘子从 src 借助 tmp 移到 tgt void dfs(int i, char src, char tmp, char tgt) { if (i 1) { // 只剩一个直接搬 move(src, tgt); return; } dfs(i - 1, src, tgt, tmp); // 上面 i-1 个先挪到中转站 move(src, tgt); // 最大盘落到目标柱 dfs(i - 1, tmp, src, tgt); // 中转站那摞再挪到目标柱 } int main() { int n; cin n; dfs(n, A, B, C); return 0; }dfs(i-1, src, tgt, tmp)里第三、四个参数交换是因为此时“目标”变成了“中转”dfs(i-1, tmp, src, tgt)里第二、三个参数交换是因为此时“起点”变成了上一轮的中转站。移动总次数是 $2^n - 1$n3 时 7 步跑一遍输出数一下就知道了。参数语义记不住的时候最省事的办法是在每个递归调用上方写一行中文注释写不出来就说明还没真懂。考场上没时间写注释但平时练习写十遍手指会替你记住。4.3 把两道题扩写成可编译版本再跑一遍完善程序的坑在于“填对了但没跑过”。把两道题补全成完整程序各加三组边界测试n 1、n 2、n 0或者 num 1、num 2、num 4。完全平方数在 num 1 时bound 1i 11 1返回 true正确如果上界写成num/2bound 0循环不进返回 false错。汉诺塔在 n 1 时直接走出口输出一行n 0 时i 1不成立会一路递归到负数栈溢出。原题约束 n 是正整数所以不考这个但自己写题解时加个if (n 0) return;是习惯问题。跑通这两段代码的价值不在于押中题而在于你能拿它当模板判断完全平方数换成判断质数、汉诺塔换成全排列骨架都差不多。5. 避坑与排查五个反复翻车的现场5.1 把试除上界改成 n/2 就以为结果会变现象第 17 题选了“会变成 6”对答案发现是 F实际仍是 8。 原因上界从 $\sqrt{n}$ 放大到 $n/2$只是多跑了循环判定逻辑没变素数还是那几个。 解决记住一条判断准则——上界放大不改变正确性只改变效率只有当上界缩小到不足以覆盖因子时结果才会错。真拿不准就在草稿纸上把 n 20 的循环跑一遍比背结论可靠。5.2 把 struct 当基本类型、把 repeat-until 当 C 循环现象语言细节题连错两题明明平时写过 struct。 原因写代码时用得多但没做过“哪些是关键字、哪些是标准库、哪些是别的语言”的区分。 解决花十分钟翻一遍 C 基本类型清单int、float、double、char、bool、void再翻一遍循环语句for、while、do-while。凡是不在这两个清单里的一律归到“复合类型”或“非 C 语法”。这类题的性价比极高错一次就不该错第二次。5.3 组合计数用容斥漏掉重复计数现象算出 210 或 120选项里恰好有 120直接中招。 原因先 C(10,4) 再减“某部门 0 人”的情况三个部门两两之间的交集被减了两次。 解决凡是“每类至少一个”的题先确定人数分布这里是 211再按“谁出 2 人”分类相加。分类加法每一步互斥写完能自检——三类的系数应该对称54/36/36 就是对称的如果算出三个不一样的数多半分错了。5.4 汉诺塔递归参数抄反程序静默跑完但输出错现象代码能编译能运行输出的移动序列也对得上步数但顺序乱了。 原因dfs(i-1, src, tgt, tmp)写成dfs(i-1, src, tmp, tgt)第三个参数该放中转的地方放了目标。 解决递归题一律先写语义注释再写调用写完把注释念一遍——“把 i−1 个盘子从 src 借助 tgt 移到 tmp”念得通就对念不通就是参数放错了。另外可以加一个断言每次move之后检查大盘不能压小盘用 vector 模拟三根柱子几十行就能把错误暴露出来。5.5 浮点 sqrt 直接比较导致边界误判现象if (sqrt(num) * sqrt(num) num)在 num 25 时偶尔返回 false。 原因sqrt返回 doublesqrt(25)可能算出 4.999999999999999平方后是 24.999999999999996。 解决不要用浮点结果做相等比较。要判断完全平方数就老老实实枚举整数i到floor(sqrt(num))再比i*i num确实要开方就先round再验算一次平方。这条在初赛代码里不一定考但自己写题解时踩一次就够记一辈子。6. 把真题变成训练闭环本文还有配套的精品资源点击获取
