CSP-J1 七年真题横向比较 单选·阅读·完善

依据 NOI 考纲（2025 年修订版）入门级 2.1 整理　|　覆盖 2019—2025 七年：单选 105 题按七大知识群横向全解、阅读程序(1) 四大常考代码逻辑、完善程序(1) 七年算法与复杂度对比、常用库函数速查举例

七年横向 · 考纲对照总表

第1讲 单选题：七大知识群横向全解【考纲 2.1】

七年 105 道单选题的考点高度集中：数据结构、数学、常识编码、语言基础四大块合计近八成。先看全局分布，再逐群精讲。

图 1　七大知识群 × 七年分布矩阵：格内数字为题量，每列合计 15 题

一、命题权重与三年轮换规律

轮换观察：常识类与语言类呈「互补轮换」——2022 年常识仅 1 题而语言类开始发力；2025 年常识轮空、语言与数制各 3 题。复习时按「权重降序 + 当年轮空补位」的顺序安排优先级最划算。

二、知识群一：数据结构（32 题，第一板块）

考纲条目：2.1.3 数据结构（链表【3】、栈与队列【3】、二叉树【34】、图【34】、哈夫曼树【4】）。

核心知识与真题精讲：

• 出栈序列合法性（五年六考，其中序列合法性判断四年五考）：判断方法——模拟「能进则进，栈顶匹配则弹」；性质口诀**「出栈元素之后，比它小的元素必须按降序输出」**。真题：2020-11（栈 LIFO 识别）、2021-5（不合法序列）、2022-2（6 5 4 3 2 1 入栈找非法出栈）、2024-13（1~6 入栈，不可能的出栈序）、2025-15（栈队列混合模拟）。
• 完全二叉树四个必背结论：n 个结点高度为「log2 n 向下取整 + 1」——2020-12（61 个结点高度 6）；数组表示法孩子下标 2i、2i+1——2022-8（第 9 位结点的兄弟与右孩子为 8、19）；高度 h 的完全二叉树形态数 = 2^(h−1)（最后一层 1~2^(h−1) 个结点各成一种形态）——2021-8（高度 5 有 16 种）；n 个结点的完全二叉树叶子数 = 「n/2 向上取整」——2025-14（1000 个结点 500 片叶子）。
• 二叉树遍历重建：前序（或后序）定根、中序分左右。2019-14（后序+中序→前序）、2023-11（前序+中序→后序）、2024-12（前序+中序→后序）。手算流程：从前序首字符（或后序末字符）取根 → 在中序中定位 → 递归两段。
• 图的三个计数性质：n 顶点连通至少 n−1 条边（2020-8：10 顶点至少 9 条）；n 顶点 m 边连通图删成树要删 m−n+1 条（2021-6）；无向图度数和 = 2×边数（2024-11），有向图入度和 = 出度和 = 边数（2025-5）。有向连通图邻接矩阵至少 N 个非零元素（构成一个有向环，2022-9）。
• 哈夫曼树：本质是贪心策略（2021-11）；构造时每次取最小的两堆合并，WPL = 各叶子权值 × 深度之和——2025-4（权 10、12、15、20、25 的 WPL 为 186，手算合并过程：(10+12)=22 → (15+20)=35 → (22+25)=47 → (35+47)=82，WPL = 10×3+12×3+15×2+20×2+25×2 = 186）；编码长度由频率分布决定（2022-7 字母 d 的编码长 2 位）。
• 链表 vs 数组（四年四考）：链表不能随机访问（2019-6、2020-7 都考「不具有的特点」）；插入删除不需移动元素、大小可动态调整（2022-4）；双向循环链表插结点的指针顺序（2022-11：先改前驱的后继再接管两端）。

扩展：栈的非法出栈序列计数是卡特兰数的应用——n 个元素的全排列 n! 中合法出栈序列恰 C(2n,n)/(n+1) 个；2024-13 的 6 元素情形合法序列 132 个。图的度数性质可推广到握手定理推论：奇度顶点必为偶数个。

三、知识群二：数学与计数（20 题）

考纲条目：2.1.5 数学与其他（加乘原理【2】、排列组合【4】、初等数论【3】、数制转换【3】）。

七年分布：2019-7/9/10/11/12/13（6 题）、2020-10/13/14/15、2021-10/12、2022-14、2023-6/14、2024-3/14、2025-6/8/11。

核心知识：本群是《CSP-J1 组合数学与数论·七年真题全解》的完整覆盖对象，此处给横向速查——

• 排列组合模型七年全覆盖：捆绑法（2020-10 双胞胎 48、2024-14 女生相邻 4320）、隔板法（2020-14 名额分配 C(9,6)=84）、补集思想（2023-14 至少一女生 1420、2025-6 男女都有 120）、平均分组除序（2021-10 组三队 15）、多重集组成（2021-12 三位数 18）、格路计数（2025-11 棋盘 C(7,3)=35）。
• 数论三件：素数判定（2019-9，97；91=7×13 与 93=3×31 是经典陷阱）、辗转相除（2019-10，gcd(319,377)=29）、整数拆分（2019-7，8 球 5 袋=18）。
• 递推取模周期（2025-8）：f[n]=(f[n−1]+f[n−2]) mod 7 周期 16，f[2025]=6——递推取模必想循环节。
• 鸽笼原理（2019-12）：13 张牌入 4 花色至少 4 张同色。
• 算术应用（2019-11 小胖减肥）：单价比较下的预算分配，贪心即可。

扩展：近三年（2023-2025）数学题形态从「纯计数」转向「计数 + 程序验证」复合（如 2025-8 需要发现周期），建议把杨辉三角、隔板、捆绑三个模型的公式与手算流程练到 1 分钟内出答。

四、知识群三：计算机常识与信息编码（16 题）

考纲条目：2.1.1 基础知识（计算机史、奖项、软硬件常识）、2.1.2 中的编码与单位。

核心知识与真题精讲：

• 奖项与人物：图灵奖是计算机科学最高奖（2019-15、2021-2）；面向对象语言辨识（2021-1 C++/Python/Java 中找不属于者、2022-1 printf 与 OOP 无关）。
• 存储单位换算（高频）：32 位整型占 4 字节（2019-3）；bit 是最小单位（2023-13）；1MB = 1024KB = 1024×1024B = 2^23 bit（2024-5）；图像存储 = 像素数 × 每像素字节数（2020-4：2048×1024×32bit = 8MB）。
• 系统与工具：编译器把源程序翻译成机器指令（2020-2、2024-15）；操作系统辨识（2023-15 HTML 不是、2024-10 Notepad 不是）；存储单元的编号是「地址」（2020-1）。
• 数据表示：计算机内部最终以二进制存储（2021-3）；4 位格雷码序列（2024-4）——相邻两数恰一位不同，反射构造法生成。

扩展：单位换算链 1B=8bit、1KB=2^10B、1MB=2^20B、1GB=2^30B 建议与 2 的幂表（2^10≈10^3、2^16=65536、2^20≈10^6、2^32≈4.3×10^9）合并记忆，2025 单选第 1 题正是「2^32−1 最接近 4×10^9」。

五、知识群四：语言基础与递归（15 题）

考纲条目：2.1.2 C++ 程序设计（类型【1】、语句【2】、函数与递归【2,3】、string【2】、指针【4】）。

核心知识与真题精讲：

• 递归求值（2021-13、2025-3）：考场做法是「从边界反向代入」——先写最底层返回值，再逐层回代，比正向模拟稳得多；2020-6 递归求数组最小值是「函数功能识别」型。
• 类型系统与基本语句（2023-1 const 修饰不可改变量、2024-6 基本数据类型、2024-7 循环语句辨识：repeat-until 不属于 C++）。
• 指针与引用：2022-3 指针赋值 p=q 使 p 指向 y（地址语义）；2025-10 值传递与引用传递（solve 交换后 x=10、y=10）；2023-3 union 成员的正确访问 data.value。
• 字符运算：2024-8 (char)('a'+13)='n'——ASCII 连续性，'a'=97、'A'=65，相差 32。
• string 类（2025-9）：+ 可连接 string 与 char，length 与 size 等价且不计结尾符。
• 循环等价性（2019-4）：S 初值 a，循环 c 次 S=S−1 等价 S=a−c——识别「程序段 ↔ 表达式」的映射。

六、知识群五：数制与位运算（11 题）

考纲条目：2.1.2-4 位运算【2】、2.1.5-1 数制转换【3】。

核心知识：按位与（2019-2）、x&(x−1) 清最低位 1（2025-2）、小数进制（2021-7 的 0.11(2)=0.75、2022-13 的 0.1(8)=0.125）、八进制竖式加法逢八进一（2023-2）、多进制混合运算先转十进制（2023-8、2024-2、2025-13）、32 位补码范围（2024-1）与 2^32−1≈4×10^9（2025-1）。

扩展：位运算三神器（lowbit = x&−x、popcount 循环 x&=x−1、左移 1<<k）同时是阅读程序 2021/2022 两年的主考代码，单选与阅读程序在同一考点上形成呼应——这是横向复习的最高杠杆点之一。

七、知识群六：排序与算法分析（7 题）

考纲条目：2.1.4-3 基础算法（排序【3,4】、二分法【4】）、算法概念【1,2】。

核心知识与真题精讲：

• 折半查找最多比较次数：n 个元素最多「log2(n+1) 向上取整」次——2019-5（100 个元素 7 次，2^7=128>100）、2024-9（1000 个元素 10 次，2^10=1024>1000）。
• 冒泡排序两问：带提前退出的冒泡对已有序数组最少比较 n−1 次（2020-5）；交换次数 = 逆序对数（2025-12 对 [6,1,5,2,4] 交换 6 次）。
• 排序稳定性（2022-12）：冒泡/插入/归并稳定，选择/快排不稳定——「简单选择排序是稳定的」为错误说法。
• 最少比较找最大（2021-4）：N 个数两两比较淘汰，N−1 次。
• 贪心策略（2021-15 过河）：1、2 作「往返摆渡人」，4 人 15 分钟过河。

八、知识群七：表达式与逻辑（5 题）

考纲条目：2.1.2-3/4（表达式求值、逻辑运算【1】）。

核心知识：前缀/中缀/后缀转换（2021-9 a*(b+c)*d → abc+d，2022-6 a+(b−c)d → +a−bcd，2023-9 后缀转中缀）；逻辑表达式求值代入法（2020-3）；表达式等价判断（2025-7 用「(a&&b)||(!c&&a) ≡ a&&(b||!c)」真值表或取特殊值排除）。手算技巧：中缀转后缀用「运算符栈 + 括号配对」，转换后用一次栈模拟验算。

第2讲 阅读程序(1)：常考代码逻辑精讲【考纲 2.1.2】

阅读程序第一题七年全部落在「短代码、深语义」的框架里：程序不超过 40 行，但判断题专攻改一行会怎样。把七年第一题按代码模式横向串起来，会发现只有四类逻辑反复出现。

图 2　四大常考代码逻辑模式与七年第一题主题

一、七年程序一览

二、模式一：位运算三神器（2021、2022 连续两年主考）

intf(int x) { int ret = 0; for (; x; x &= x - 1) ret++; return ret; }  // popcountintg(int x) { return x & -x; }                                        // lowbit

• popcount（二进制中 1 的个数）：x &= x - 1 每次精确消灭最低位的 1，循环次数就是 1 的个数。2021 判断题 18：对 10（1010₂）f=2 而非 3——先数 1 再谈别的。
• lowbit（最低位的 1 所代表的值）：x & -x 利用补码「取反加一」恰好保留最低位 1。2021 判断题 19：511998 = 0x7CFFE，f=16、g=2，和为 18。
• 负数也要会算：2021 选择 21，−65536 的补码 0xFFFF0000 含 16 个 1，lowbit 为 65536，答案 65552。
• 位交织（2022）：(x | x << 2) & 0x33 把 4 位数撒到偶数位，(x | x << 1) & 0x55 再撒到 1、3、5、7 位；z = x | y << 1 把 x 的位放偶位、y 的位放奇位——z 的二进制就是 x、y 的比特交错排列。追踪这类程序的诀窍是写出一组 4 位二进制的中间值表，不要空想。

三、模式二：映射表与标志变量（2020）

2020 程序用两个数组互为逆映射：encoder 先放 'C','S','P' 再按字母序补齐 23 个字母构成排列；decoder[encoder[i]-'A'] = i+'A' 构建「密文 → 明文」。三个常考套路全部出现：flag 标志变量 + break 提前退出（找未出现字母）、计数器 k 做下标追加、逆映射反查。判断题主攻两问：输入含非大写字母时 st[i]-'A' 下标越界（√）；替换密码存在不动点（如 T 解码仍是 T）（×——「一定不同」错）。选择 5/6 的「由输出反推输入」本质是查逆映射表：输出 A/B/C 分别来自输入 C/S/P。

四、模式三：循环边界与不变量（2019、2024、2025）

• 2019：i 从 1 到 n 枚举约数位置。改 i=0 → n%0 除零崩溃；改 i*i<=n → 大于根号 n 的约数（含 n 自身）漏转，结果改变。一句话：改边界 = 改语义，先把「循环不变量」（本例：i 是 n 的约数才转换 st[i−1]）说清楚再判断。
• 2024：isPrime 的 i*i <= n 若改成 i*i <= n/2，4、6、9、15 等合数因找不到满足条件的因子而误判为素数，countPrimes(20) 从 8 变 12——判定边界直接决定真假集。改成 i <= n 则结果不变只是变慢（选择 20 选 B）。
• 2025：三重循环 `ii≥1 矛盾，答案恒为 0（选择 19 选 B「变小」）。

五、模式四：浮点格式化输出（2023）

cout.flags(ios::fixed); cout.precision(4); 两行把后续浮点输出锁定为定点 4 位小数。海伦公式 sqrt(s(s−a)(s−b)(s−c)) 中 s 为半周长。判断与选择围绕「三角形不等式约束下的面积计算」：3、4、5 直角三角形面积为 6.0000；等边或特殊组合要能手算。考场心法：先看 fixed/precision 定格式，再代数值；输出位数与真实面积无关，是打印格式。

六、判断题三板斧（七年套路总结）

考场心法：阅读程序第一题的判断题，「×」多藏在三处——边界改动改变语义、输入假设不成立、编译期规则（声明顺序、类型）；「√」多是一眼可验证的确定计算。先扫程序找位运算/映射表/循环边界三个模式，再读题，速度翻倍。

第3讲 完善程序(1)：算法识别与复杂度对比【考纲 2.1.4】

完善程序第一题七年清一色是「经典算法骨架 + 关键行挖空」。识别算法 → 还原填空 → 分析复杂度三步走；本讲把 7 个补全程序全部实际运行验证，并逐一对比朴素算法。

图 3　七年算法复杂度对比（n = 10^6 时操作次数的对数刻度；灰色为朴素对照）

一、七年算法一览

二、2019 矩阵变幻：分治递归的教科书

填空答案：① t　② x, y　③ x+step, y+step　④ n, 0　⑤ 1 << n。

已补全程序（实测 n=3 输出 8×8 矩阵）：

// 2019 完善程序(1) 矩阵变幻（已补全）#include<bits/stdc++.h>using namespace std;int n;const int max_size = 1 << 10;int res[max_size][max_size];voidrecursive(int x, int y, int n, int t){    if (n == 0) { res[x][y] = t; return; }        // ① 递归出口：1x1 填当前类型    int step = 1 << (n - 1);                      // 半边长 2^(n-1)    recursive(x, y, n - 1, t);                    // ② 左上：原类型    recursive(x, y + step, n - 1, t);             //   右上：原类型    recursive(x + step, y, n - 1, t);             //   左下：原类型    recursive(x + step, y + step, n - 1, !t);     // ③ 右下：类型取反}intmain(){    scanf(”%d”, &n);    recursive(0, 0, n, 0);                        // ④ 初始：深度 n、类型 0    int size = 1 << n;                            // ⑤ 边长 2^n    for (int i = 0; i < size; ++i) {        for (int j = 0; j < size; ++j) printf(”%d”, res[i][j]);        puts(””);    }    return 0;}

复杂度与朴素对比：递归共 1+4+16+…+4^n 个结点、每个叶子写一格，输出矩阵本身就有 4^n = 2^2n 格，递归法每个格子恰好写一次，已是该规模下的最优；朴素「按变幻规则一轮轮替换」总写入量约 (4/3)·4^n，同级但多三分之一工作量且需临时矩阵。扩展（公式法）：该矩阵满足 res[x][y] = (x AND y 的二进制中 1 的个数的奇偶性)——即 parity(x & y)，可用 O(1) 逐格直接计算；已实测 n=3 时公式法与递归法输出逐格一致：

// 2019 扩展：parity(x & y) 公式法，与递归版逐格互验一致#include<bits/stdc++.h>intpopparity(int v){ int c = 0; while (v) { c ^= (v & 1); v >>= 1; } return c; }intmain(){    int n = 3, size = 1 << n;    for (int i = 0; i < size; i++) {        for (int j = 0; j < size; j++) printf(”%d”, popparity(i & j));        printf(”\n”);    }    return 0;}

三、2020 质因数分解：试除法的三个关键行

填空答案：① 2　② i * i　③ while (n % i == 0)　④ n > 1　⑤ n。

已补全程序（实测：120 → 2 2 2 3 5；质数 999999937 → 输出自身）：

// 2020 完善程序(1) 质因数分解（已补全）#include<bits/stdc++.h>using namespace std;int n, i;intmain(){    scanf(”%d”, &n);    for (i = 2; i * i <= n; i++) {          // ①② 从 2 起、试到根号 n        while (n % i == 0) {                 // ③ 同一因子反复除尽            printf(”%d ”, i);            n = n / i;        }    }    if (n > 1) printf(”%d ”, n);             // ④⑤ 剩下的大于根号 n 的质因子    printf(”\n”);    return 0;}

复杂度推导：循环变量最多到 √n，且每次除法让 n 至少减半——总量 O(√n)。朴素对比：逐个检验 2..n 是否为因子为 O(n)；n = 10^9 时 √n ≈ 31623 次与 10^9 次的差距是四万倍。为什么 i*i <= n 就够：若 n 剩余值有大于 √n 的因子，则最多剩一个（两个相乘会超过 n），由收尾分支输出。

四、2021 约瑟夫环：模拟的四个状态量

填空答案：① c < n - 1　② p　③ c++　④ p ^= 1　⑤ i = (i + 1) % n。

已补全程序（实测 n=1..8,10 依次输出 0 0 2 0 2 4 6 0 4）：

// 2021 完善程序(1) 约瑟夫环（已补全）#include<bits/stdc++.h>using namespace std;const int MAXN = 1000000;int F[MAXN];intmain(){    int n; cin >> n;    int i = 0, p = 0, c = 0;                 // i 环形下标、p 当前报数、c 已淘汰数    while (c < n - 1) {                      // ① 剩 1 人即停（i 会绕圈不能作条件）        if (F[i] == 0) {            if (p) { F[i] = 1; c++; }        // ② 报到 1 淘汰 ③ 计数            p ^= 1;                          // ④ 每次报数后 0/1 翻转        }        i = (i + 1) % n;                     // ⑤ 环形前进（跳过已淘汰只是顺带）    }    int ans = -1;    for (i = 0; i < n; i++) if (F[i] == 0) ans = i;    cout << ans << endl;    return 0;}

复杂度与优化对比：本题是「报数 0/1 交替、隔一个淘汰一个」的变体——每一轮报数恰好淘汰当前存活者的一半，共约 ⌈log₂n⌉ 轮、每轮至多扫 n 个槽位，故模拟实为O(n log n)（实测 n = 10^6 时约 2×10^7 次循环迭代）；递推公式J(1)=0、J(n) = (J(n−1)+2) mod n，O(n) 约百万次加法；更大规模可用数学法 O(1) 思想定位。模拟与递推在 n ≤ 10^6 时相差约 20 倍——不算悬殊，但递推的常数与实现风险都更小，这正是「识别算法骨架比背代码更重要」的例证。

五、2022 枚举因数：对称配对与平方数特判

填空答案：① n % i == 0　② fac[k]　③ i * i == n　④ i　⑤ n / fac[k]。

已补全程序（实测：12 → 1 2 3 4 6 12；16 → 1 2 4 8 16；9 → 1 3 9）：

// 2022 完善程序(1) 枚举因数#include<bits/stdc++.h>using namespace std;intmain(){    int n; cin >> n;    vector fac;                          // 存小于根号 n 的因子    int i;    for (i = 1; i * i < n; ++i) {        if (n % i == 0) fac.push_back(i);     // ① 整除判定    }    for (int k = 0; k < (int)fac.size(); ++k)        cout << fac[k] << ” ”;                // ② 小因子升序输出    if (i * i == n) cout << i << ” ”;        // ③④ 平方数：根号因子只输出一次    for (int k = (int)fac.size() - 1; k >= 0; --k)        cout << n / fac[k] << ” ”;            // ⑤ 大因子 = n / 小因子，降序输出    cout << endl;    return 0;}

复杂度与朴素对比：O(√n) vs 朴素 O(n)。注意两个易错点：循环用 ii < n（严格小于），退出时 i 恰为「满足 i²≥n 的最小整数」，故完全平方数时 √n = i 本身，③ 用 ii == n 特判、④ 输出 i（16 的输出中 4 只出现一次、8 与 16 由配对给出）；⑤ 的大因子按 n/fac[k] 降序配对，不需要再算一次除法判整除。

六、2023 二分找缺失元素：不变量收缩

填空答案：① nums[0]　② left = mid + 1　③ right = mid　④ left + nums[0]　⑤ nums[0] + n - 1。

已补全程序（实测：[1,2,3,5,6,7] → 缺 4；[2,3,4,5,6,7] → 连续；[3,5,6,7,8] → 缺 4）：

// 2023 完善程序(1) 寻找被移除的元素（已补全）#include<bits/stdc++.h>using namespace std;intfind_missing(vector& nums){    int left = 0, right = nums.size() - 1;    while (left < right) {        int mid = left + (right - left) / 2;        if (nums[mid] == mid + nums[0])      // ① 不变量：左半完整则值=下标+首项            left = mid + 1;                  // ② 缺口在右半        else            right = mid;                     // ③ 缺口在左半（含 mid）    }    return left + nums[0];                   // ④ 收敛点即缺失位置对应的值}intmain(){    int n; cin >> n;    vector nums(n);    for (int i = 0; i < n; i++) cin >> nums[i];    int missing_number = find_missing(nums);    if (missing_number == nums[0] + n - 1)   // ⑤ 缺的是最后一个 → 原数组连续        cout << ”Sequence is consecutive” << endl;    else        cout << ”Missing number is ” << missing_number << endl;    return 0;}

复杂度与朴素对比：二分 O(log n)（10^6 个元素仅约 20 次比较）vs 顺序扫描 O(n)。为什么能二分：数组有序且「值 − 下标」只有一次从 nums[0] 跳到 nums[0]+1 的突变——这就是判断条件 ① 的不变量；②③ 的收缩方向由不变量唯一确定，right = mid 保留 mid 因为 mid 本身可能就是缺口起点。

七、2024 判断平方数：枚举上界的边界感

填空答案：① 1　② (int)floor(sqrt(num))　③ num == i * i　④ true　⑤ false。

已补全程序（实测：1/4/9/16/25 均判定为平方数，2/8/99 判定不是）：

// 2024 完善程序(1) 判断平方数（已补全）#include<bits/stdc++.h>using namespace std;boolisSquare(int num){    int i = 1;                               // ① 从 1 开始（否则漏掉 n=1）    int bound = (int)floor(sqrt((double)num)); // ② 上界：根号 n 向下取整    for (; i <= bound; ++i) {        if (num == i * i) return true;       // ③④ 找到即返回 true    }    return false;                            // ⑤ 扫完没有则不是}intmain(){    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;}

复杂度与优化对比：枚举 O(√n) vs 朴素逐个检验 i*i 是否等于 n（同样 O(√n)——本题「朴素」指的是不设上界一直枚到 n，为 O(n)）；更优写法是一行公式 int r = (int)floor(sqrt((double)num + 0.5)); return r * r == num;——加 0.5 规避浮点误差，O(1) 次运算。填空陷阱：③ 必须 ==（= 是赋值）；② 若选 floor(sqrt(num))-1 会漏掉 9 = 3² 这类恰好整开的数。

八、2025 RLE 解码：单遍扫描的下标纪律

填空答案：① i < z.length()　② count * 10 + (z[i] - '0')　③ count　④ ch　⑤ i++。

已补全程序（实测：A12B → 12 个 A 加 B；ABC → ABC；A2B12c → AA + 12 个 B + c）：

// 2025 完善程序(1) RLE 解码（已补全）#include<bits/stdc++.h>using namespace std;intmain(){    string z; cin >> z;    string s = ””;    for (int i = 0; i < (int)z.length(); ) {   // ① 扫到串尾；i 的推进在循环体内控制        char ch = z[i];        if (isdigit(z[i + 1])) {                // 后跟数字：进入计数分支            int count = 0;            i++;            while (i < (int)z.length() && isdigit(z[i])) {                count = count * 10 + (z[i] - '0'); // ② 多位数按位累加                i++;            }            for (int j = 0; j < count; ++j) s += ch; // ③ 重复 count 次        } else {            s += ch;                            // ④ 单字符直接追加            i++;                                // ⑤ 别忘了前进，否则死循环        }    }    cout << s << endl;    return 0;}

复杂度：每个字符被消费一次、输出按展开长度计，O(串长 + 输出长度)——单遍扫描已是理论最优（至少要读一遍输入、写一遍输出）。本题考点全在下标纪律：② 的多位数解析（A12 不能解析成 1 和 2）、⑤ 与 while 分支的推进职责划分；选择题 34 的解析点「z[i+1] 越界时读到 \0、isdigit 为假」正是 C++ string 的边界特性。

全书复杂度总结：三年轮换规律

完善程序(1) 复杂度谱系（由慢到快）：

三年一轮的命题轮换：2019—2021 偏「构造与模拟」（分治矩阵、试除、约瑟夫）；2022—2024 偏「检验与查找」（因数、二分、平方数）——全是 O(√n)/O(log n) 家族；2025 回到「字符串模拟」（RLE 解码）。预测性结论：完善程序第一题的复杂度上限稳定在 O(n log n) 以内、以 O(√n) 与 O(log n) 为绝对主力，朴素 O(n) 方案在 10^6 规模下普遍不可行——识别算法骨架比背代码更重要。

第4讲 常用库函数速查：读程序先认「脸」【考纲 2.1.2】

阅读程序与完善程序的代码里，库函数从不附注释——认出它们的「脸」，就能省下一半推演时间。本讲按CSP-J（入门级）考纲 2.1.2的要求系统整理常用库函数与 STL 操作：不限于七年真题出现过的，还包括同级别选手必须认识的「备选脸」。每个函数给出作用说明 + 可运行示例（C++98，全部经编译运行验证），已考过的标注真题锚点，未考但高频的标注考点提示。

一、字符判断与转换（）

真题锚点：2025 RLE 解码用 isdigit(z[i+1]) 判断字母后是否跟重复次数，是多位数解析（填空②）的关键。

#include<bits/stdc++.h>intmain(){    printf(”%d %d %d %d\n”, isdigit('7') != 0, isalpha('a') != 0,           isalnum('a') != 0, isspace(' ') != 0);   // 1 1 1 1    printf(”%c %c %c\n”, tolower('A'), toupper('b'), tolower('7'));  // a B 7    return 0;}

注意：isXXX 系列「非 0 即真」，返回值不一定是 1，判断时写 != 0 最稳妥。

二、C 字符串与内存操作（）

#include<bits/stdc++.h>intmain(){    char s[20] = ”noip”;    strcat(s, ”2026”);    printf(”%s %d\n”, s, (int)strlen(s));                       // noip2026 8    printf(”%d %d\n”, strcmp(”abc”, ”abd”) < 0,           (int)(strstr(s, ”ip”) - s));                         // 1 2（”ip” 从下标 2 开始）    int a[5];    memset(a, 0, sizeof(a));        // 正确：全部清零    memset(a, 1, sizeof(a));        // 坑！每个元素变成 0x01010101 = 16843009，不是 1    printf(”%d\n”, a[0]);           // 16843009    return 0;}

经典坑：memset 按字节填充，int 数组只能放心填 0 或 -1（补码全 1），填其它值几乎必错。

三、string 类常用操作（）

真题锚点：2025 RLE 中 z[i+1] 越界时读到 '\0'、isdigit 为假——正是 string 末尾以 '\0' 兜底的特性，该特性直接决定了选择题 34 的判断。

#include<bits/stdc++.h>using namespace std;intmain(){    string s = ”csp2025”;    cout << s.length() << ' ' << s.substr(3, 4) << endl;  // 7 2025    s.insert(3, ”-J”);       // csp-J2025    s.erase(0, 1);           // sp-J2025    s.replace(0, 2, ”CS”);   // CS-J2025    cout << s << ' ' << s.empty() << endl;                // CS-J2025 0    cout << (s.find(”2025”) != string::npos) << endl;     // 1    return 0;}

考点提示：cin >> s 遇空格就截断，题目说「一行含空格的字符串」时必须用 getline(cin, s)——完善程序常在这个细节埋空。

四、数学函数（ /  / ）

真题锚点：2023 海伦公式 sqrt(s*(s-a)(s-b)(s-c))；2024 判断平方数用 int(sqrt((double)n)+0.5)——+0.5 正是为了抵消浮点误差（sqrt(25) 可能算出 4.9999…）。

#include<bits/stdc++.h>intmain(){    int n = 16;    int r = (int)(sqrt((double)n) + 0.5);    printf(”%d %d %d\n”, r, r * r == n, abs(-7));             // 4 1 7    printf(”%.2f %.1f %.0f\n”, pow(2, 10), fabs(-3.14),           log10(1000.0));                                    // 1024.00 3.1 3    printf(”%d\n”, INT_MAX);                                  // 2147483647    printf(”%d %d\n”, (int)ceil(4.1), (int)floor(4.9));       // 5 4    return 0;}

考点提示：① 求正整数位数可用 (int)log10(n) + 1；② 二分次数就是 ⌈log₂n⌉，对应单选「1000 个元素最多比较 10 次」；③ 最大值初始化用 INT_MAX，但 INT_MAX + 1 会溢出成负数，判断前想清楚。

五、排序与算法（）

#include <bits/stdc++.h>using namespace std;bool desc(int a, int b) { return a > b; }int main() {    int a[7] = {3, 1, 4, 1, 5, 9, 2};    sort(a, a + 7);                                    // 1 1 2 3 4 5 9    printf(”%d %d %d\n”, a[0], a[6],           binary_search(a, a + 7, 5));                // 1 9 1    printf(”%d\n”, (int)(lower_bound(a, a + 7, 4) - a));  // 4（下标）    printf(”%d %d\n”, (int)count(a, a + 7, 1),           *max_element(a, a + 7));                    // 2 9    sort(a, a + 7, desc);    printf(”%d\n”, a[0]);                              // 9    int b[6] = {1, 1, 2, 2, 3, 3};    int m = (int)(unique(b, b + 6) - b);    printf(”%d %d\n”, m, b[2]);                        // 3 3    int p[3] = {1, 2, 3};    next_permutation(p, p + 3);    printf(”%d%d%d\n”, p[0], p[1], p[2]);              // 132    int c[4];    fill(c, c + 4, 7);    printf(”%d\n”, c[3]);                              // 7    return 0;}

真题锚点：2023 二分找缺失元素的手写二分，本质上就是 lower_bound 的「不变量收缩」逻辑；单选「排序稳定性」对应 stable_sort 与 sort 的区别。

考点提示：① binary_search / lower_bound / upper_bound 必须先升序排序，降序数组上结果全错；② next_permutation 是入门组暴力枚举排列的神器（n ≤ 8 的全排列题直接秒）；③ unique 只去相邻重复，先 sort 再 unique 才是真去重。

六、STL 容器入门（ /  / ）

#include<bits/stdc++.h>using namespace std;intmain(){    vector v;    v.push_back(5); v.push_back(3); v.push_back(8);    printf(”%d %d %d\n”, (int)v.size(), v[0], v.back());  // 3 5 8    stack st;    st.push(1); st.push(2);    printf(”%d\n”, st.top()); st.pop();                    // 2    queue q;    q.push(10); q.push(20);    printf(”%d\n”, q.front()); q.pop();                    // 10    printf(”%d %d\n”, (int)st.size(), (int)q.size());      // 1 1    return 0;}

真题锚点：单选栈系列（2021-5 出栈序列、2022-2 合法出栈、2024-13 出栈判断、2025-15 栈+队列混合）考的就是 push/pop/top 与 push/pop/front 的手工模拟。

考点提示：vector 是「不定长数组」，数据范围读入后才知道多大时最顺手；注意 stack/queue 的 pop() 不返回元素，取值要先 top()/front() 再 pop()。

七、格式化输入输出（ / ）

真题锚点：2023 阅读程序用 fixed + setprecision(4) 输出 6.0000——fixed 决定「小数点后位数」的语义；没有它，setprecision 控制的是有效数字总位数，结果完全不同。

#include<bits/stdc++.h>using namespace std;intmain(){    int n = 42;    double x = 3.1415926;    printf(”%5d|%-5d|%05d\n”, n, n, n);   //    42|42   |00042    printf(”%x %o %.3f\n”, 255, 8, x);    // ff 10 3.142    cout << fixed << setprecision(2) << x << endl;  // 3.14    cout << setw(5) << setfill('*') << n << endl;   // ***42    return 0;}

八、一句话总表