ARTICLE · 1023385
一文搞定CSP初赛阅读程序:算法模板、经典问题与避坑指南
阅读程序是初赛分值最大的题型——40分，占总分40%。三道大题，每题包含判断题和选择题，要求你不看电脑、纯靠纸面追踪，读懂程序逻辑、判断正误、推算输出。
今天这篇文章，把阅读程序中常见的算法模板全部梳理一遍，列出每种算法的思路步骤、经典问题和常见坑点。J组和S组分开，帮你精准定位需要练习的方向。
一、阅读程序题型概述
考试形式
• 3道大题，每题给一段完整程序（不一定有功能说明）
• 每题包含判断题（1.5分/题）和选择题（3分/题）
• 合计约16小题，共40分
核心能力要求
J组 vs S组
二、J组常见算法模板与坑点
模板1：模拟法
算法思路： 按题意逐步执行操作，用变量记录每一步状态。
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
// 模拟：把偶数位置元素往前挪
int k = 0;
for (int i = 0; i < n; i++) {
if (a[i] % 2 == 0) a[k++] = a[i];
}
for (int i = 0; i < k; i++) printf("%d ", a[i]);
return 0;
}
识别特征：
• 大量赋值语句和循环
• 没有明显算法结构，就是"照着规则走"
• 常见场景：日期计算、游戏规则模拟、数据处理
经典问题：
数组循环右移k位：
int b[105];
for (int i = 0; i < n; i++) b[(i + k) % n] = a[i];
for (int i = 0; i < n; i++) a[i] = b[i];
不用额外数组反转三段：
void rev(int l, int r) {
while (l < r) {
int t = a[l]; a[l] = a[r]; a[r] = t;
l++; r--;
}
}
// 右移k位：rev(0, n-k-1); rev(n-k, n-1); rev(0, n-1);
字符串逐字符变换（凯撒密码）：
int main() {
scanf("%s", s);
int n = strlen(s);
for (int i = 0; i < n; i++) {
if (s[i] >= 'a' && s[i] <= 'z')
s[i] = (s[i] - 'a' + 3) % 26 + 'a';
}
printf("%s\n", s);
return 0;
}
常见坑点：
• 循环边界：i < n 还是 i <= n，差一轮结果不同
• 变量覆盖：中间变量被重新赋值，旧值丢失，注意赋值顺序
• 整数除法截断：7/2=3 不是 3.5，两个 int 相除直接丢小数
• 交换陷阱：不用临时变量的交换（a^=b;b^=a;a^=b）在 a 和 b 是同一变量时归零
模板2：冒泡排序
算法思路： 相邻元素比较，逆序则交换，每轮把最大值"冒泡"到末尾。
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
return 0;
}
识别特征：
• 双重循环，外层控制轮数，内层控制比较范围
• 内层循环上限随外层递减：n - 1 - i
• 内层比较相邻元素：a[j] 和 a[j+1]
经典问题：
求总交换次数（逆序对数）：
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
cnt++; // 每次交换+1
}
优化版（加标志提前终止）：
bool flag = false;
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
flag = true;
}
if (!flag) break; // 某轮无交换，已有序
}
常见坑点：
• 比较符号：> 排升序，< 排降序；>= 会破坏稳定性（相等元素也交换）
• 轮数与比较次数：n个元素最多n-1轮，第i轮比较n-1-i次
• 优化版：加了 swapped 标志，某轮无交换则提前终止——问"最少比较几次"时要考虑已有序情况
• 轮数从0还是1开始：for(i=0;i<n-1;i++) 第0轮是第一轮
模板3：选择排序
算法思路： 每轮从未排序部分找最小值，与当前位置交换。
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n - 1; i++) {
int mi = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[mi]) mi = j;
int t = a[i]; a[i] = a[mi]; a[mi] = t;
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
return 0;
}
识别特征：
• 双重循环，内层从 i+1 开始找最小
• 记录最小值下标 mi
• 内层结束后做一次交换
经典问题：
实际交换次数（仅当 mi != i 时才交换）：
for (int i = 0; i < n - 1; i++) {
int mi = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[mi]) mi = j;
if (mi != i) { // 注意：可能mi就是i，不用交换
int t = a[i]; a[i] = a[mi]; a[mi] = t;
swaps++;
}
}
常见坑点：
• 不稳定：交换可能打乱相等元素的相对顺序
• 交换次数固定：最多n-1次交换（每轮最多1次），与冒泡不同
• mi初始值：每轮初始化为i，不要漏掉
模板4：插入排序
算法思路： 将未排序元素逐个插入到前面已排序序列的正确位置。
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 1; i < n; i++) {
int t = a[i], j = i - 1;
while (j >= 0 && a[j] > t) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = t;
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
return 0;
}
识别特征：
• 外层从第2个元素开始（i=1）
• 内层向前扫描，比当前元素大的后移
• 找到位置后插入
经典问题：
统计移动次数：
for (int i = 1; i < n; i++) {
int t = a[i], j = i - 1;
while (j >= 0 && a[j] > t) {
a[j + 1] = a[j];
j--;
moves++; // 每次后移+1
}
a[j + 1] = t;
}
常见坑点：
• 内层循环方向：从后往前扫描（j从i-1递减），不是从前往后
• 循环条件：j >= 0 && a[j] > t，条件顺序不能反（先判断j>=0防止越界）
• 最好情况：已有序时只比较n-1次，移动0次
模板5：递归（基础）
算法思路： 函数调用自身，将大问题分解为小问题，有明确的递归出口。
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
int main() {
int n;
scanf("%d", &n);
printf("%d\n", fib(n));
return 0;
}
识别特征：
• 函数体内有对自身的调用
• 有base case（if(n<=1) return n）
• 参数通常逐步减小
经典问题：
汉诺塔移动次数：
if (n == 1) return 1;
return 2 * hanoi(n - 1) + 1; // 2^n - 1
}
递归求阶乘：
if (n <= 1) return 1;
return n * fac(n - 1);
}
递归字符串反转：
if (l >= r) return;
char t = s[l]; s[l] = s[r]; s[r] = t;
rev(s, l + 1, r - 1);
}
// 调用：rev(s, 0, strlen(s) - 1);
常见坑点：
• 忘记递归出口：没有base case → 无限递归 → 栈溢出
• 参数方向：参数必须严格减小，否则也可能无限递归
• 返回值传递：注意是返回递归调用的结果还是只做副作用
• 递归深度：层数太多会栈溢出，n=1000的递归可能就爆了
• 重复计算：朴素递归斐波那契有大量重复计算，T(n)是指数级
模板6：二分查找
算法思路： 在有序序列中，每次比较中间元素，缩小一半搜索范围。
int main() {
scanf("%d%d", &n, &x);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int l = 0, r = n - 1, pos = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] == x) { pos = mid; break; }
else if (a[mid] < x) l = mid + 1;
else r = mid - 1;
}
printf("%d\n", pos);
return 0;
}
识别特征：
• while(l <= r) 或 while(l < r)
• mid = (l + r) / 2 或 mid = l + (r - l) / 2
• 根据 a[mid] 与目标的关系调整 l 或 r
经典问题：
查找第一个大于等于x的位置（lower_bound）：
while (l < r) {
int mid = (l + r) / 2;
if (a[mid] < x) l = mid + 1;
else r = mid; // 找到>=x的，继续往左找
}
// l就是答案位置
在单调函数上二分求满足条件的最小值：
// 满足某个单调性质
return /* ... */;
}
int l = 0, r = 1e9;
while (l < r) {
int mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid + 1;
}
常见坑点：
• 区间类型：l <= r（左闭右闭）时 r = mid - 1；l < r（左闭右开）时 r = mid
• mid溢出：(l + r) / 2 可能溢出，竞赛用 l + (r - l) / 2
• 死循环：l = mid 而不是 l = mid + 1 时，如果 l 和 r 相邻会死循环
• 要求有序：二分查找的前提是序列有序
模板7：字符串处理
算法思路： 逐字符遍历字符串，进行查找、替换、统计等操作。
int cnt[260];
int main() {
scanf("%s", s);
int n = strlen(s);
for (int i = 0; i < n; i++) {
if (s[i] >= 'A' && s[i] <= 'Z') s[i] += 32; // 转小写
cnt[s[i]]++;
}
for (int i = 'a'; i <= 'z'; i++)
if (cnt[i]) printf("%c %d\n", i, cnt[i]);
return 0;
}
识别特征：
• char 数组或 string 操作
• 常涉及ASCII码运算（大小写转换、数字提取）
• 可能有子串匹配
经典问题：
暴力模式匹配（非KMP）：
int n, m;
// 返回p在s中首次出现的位置，-1表示没找到
int brute() {
n = strlen(s); m = strlen(p);
for (int i = 0; i + m <= n; i++) {
int j = 0;
while (j < m && s[i + j] == p[j]) j++;
if (j == m) return i;
}
return -1;
}
字符串去重保留首次出现：
int vis[260];
int main() {
scanf("%s", s);
int n = strlen(s), k = 0;
for (int i = 0; i < n; i++) {
if (!vis[(int)s[i]]) {
vis[(int)s[i]] = 1;
s[k++] = s[i];
}
}
s[k] = '\0';
printf("%s\n", s);
return 0;
}
常见坑点：
• '\0'结尾：char 数组以 '\0' 结束，遍历时注意不要越界
• ASCII运算：大写转小写 +32，小写转大写 -32；数字字符转数值 - '0'
• 字符串长度：strlen 遍历到 '\0' 为止，与数组大小不同
• 下标从0开始：第1个字符是 s[0] 不是 s[1]
模板8：数组操作与前缀和
算法思路： 预处理前缀和数组，用差值快速求区间和。
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
sum[i] = sum[i - 1] + a[i]; // 前缀和
}
while (m--) {
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", sum[r] - sum[l - 1]); // 区间和
}
return 0;
}
识别特征：
• 先有一段循环计算 sum[i] = sum[i-1] + a[i]
• 查询时用 sum[r] - sum[l-1] 求区间和
• 也可能是差分数组（区间加减）
经典问题：
差分数组（区间加值后查询单点）：
int main() {
scanf("%d%d", &n, &m);
while (m--) {
int l, r, v;
scanf("%d%d%d", &l, &r, &v);
d[l] += v; d[r + 1] -= v; // 差分标记
}
int cur = 0;
for (int i = 1; i <= n; i++) {
cur += d[i]; // 前缀和还原
printf("%d ", cur);
}
return 0;
}
常见坑点：
• 前缀和下标：通常 sum[0] = 0，从1开始存，查询 [l,r] 用 sum[r] - sum[l-1]
• 越界：sum[l-1] 当 l=0 时越界，所以前缀和一般从1开始存
• 差分还原：差分数组的前缀和才是原数组
三、进阶算法模板与坑点
以下模板在J组基础上增加了S组专属内容。J组全部模板S组同样会考，不再重复。
模板S1：位运算
算法思路： 利用位运算实现高效的状态压缩、计数、判断等操作。
int cnt = 0;
while (x) {
cnt++;
x -= x & (-x); // 每次去掉最低位的1
}
return cnt;
}
int main() {
int n;
scanf("%d", &n);
printf("%d\n", popcount(n));
// lowbit: 取最低位的1
printf("%d\n", n & (-n));
return 0;
}
识别特征：
• 大量 &、|、^、<<、>> 操作
• 常与整数的状态表示结合
• 可能出现 lowbit 操作：x & (-x)
经典问题：
判断奇偶：
else printf("偶数\n");
异或交换两数（注意陷阱）：
a ^= b;
b ^= a;
a ^= b;
// 如果a和b是同一个变量，结果变成0！
状态压缩枚举子集：
for (int sub = s; sub; sub = (sub - 1) & s) {
// 处理子集sub
}
// 空集单独处理
常见坑点：
• 优先级陷阱：位运算优先级低于关系运算！a & b == c 被解析为 a & (b == c)，必须加括号
• lowbit公式：x & (-x) 不是 x & 1。-x 是补码表示，x & (-x) 取出最低位的1
• 左移溢出：1 << 31 在 int 下是负数（符号位），需要用 1LL << 31
• 异或自反性：a ^ a = 0，a ^ 0 = a。交换两数 a^=b;b^=a;a^=b 但a和b相同时会归零
• 移位与乘除：左移n位等价乘2^n，右移n位等价除2^n（向下取整）
模板S2：复杂递归与分治
算法思路： 将问题分解为子问题递归求解，合并子问题结果。常见于归并排序、快速幂等。
long long qpow(long long a, int n, long long p) {
if (n == 0) return 1;
if (n & 1) return a * qpow(a, n - 1, p) % p;
long long t = qpow(a, n / 2, p);
return t * t % p;
}
int main() {
long long a;
int n;
long long p;
scanf("%lld%d%lld", &a, &n, &p);
printf("%lld\n", qpow(a % p, n, p));
return 0;
}
识别特征：
• 递归调用参数为 n/2、l+r>>1 等
• 可能有记忆化数组（避免重复计算）
• 函数返回值参与后续计算
经典问题：
归并排序合并过程：
void merge(int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
merge(l, mid);
merge(mid + 1, r);
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) tmp[k++] = a[i++];
else tmp[k++] = a[j++];
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
for (i = l; i <= r; i++) a[i] = tmp[i];
}
分治求最大子段和：
int solve(int l, int r) {
if (l == r) return a[l];
int mid = (l + r) / 2;
int L = solve(l, mid);
int R = solve(mid + 1, r);
// 跨mid的最大和
int ls = a[mid], rs = a[mid + 1], s = 0;
for (int i = mid; i >= l; i--) { s += a[i]; if (s > ls) ls = s; }
s = 0;
for (int i = mid + 1; i <= r; i++) { s += a[i]; if (s > rs) rs = s; }
int mx = L; if (R > mx) mx = R; if (ls + rs > mx) mx = ls + rs;
return mx;
}
记忆化递归（避免重复计算）：
int vis[100005];
long long dfs(int n) {
if (n <= 1) return n;
if (vis[n]) return f[n]; // 算过了直接返回
vis[n] = 1;
f[n] = dfs(n - 1) + dfs(n - 2);
return f[n];
}
常见坑点：
• 递归树深度：分析复杂度要画递归树，T(n) = 2T(n/2) + O(n) → O(n log n)
• 记忆化：如果代码中有 if(vis[n]) return f[n] 类似语句，是记忆化递归，复杂度大幅降低
• 递归返回值方向：注意是 return dfs(left) + dfs(right) 还是 return max(dfs(left), dfs(right))
• 边界与终止：l == r 时返回什么，漏看边界会导致整题算错
模板S3：动态规划
算法思路： 将问题分解为子问题，用状态转移方程记录最优解，避免重复计算。
int a[1005], f[1005];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
int ans = 0;
for (int i = 1; i <= n; i++) {
f[i] = 1;
for (int j = 1; j < i; j++)
if (a[j] < a[i] && f[j] + 1 > f[i])
f[i] = f[j] + 1;
if (f[i] > ans) ans = f[i];
}
printf("%d\n", ans);
return 0;
}
识别特征：
• 双重或三重循环
• f[i] 或 f[i][j] 形式的状态数组
• 状态转移方程：f[i] = max(f[i], f[j] + ...)
经典问题：
最长公共子序列（LCS）：
int f[1005][1005];
int main() {
scanf("%s%s", a + 1, b + 1);
int n = strlen(a + 1), m = strlen(b + 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (a[i] == b[j]) f[i][j] = f[i-1][j-1] + 1;
else f[i][j] = max(f[i-1][j], f[i][j-1]);
}
printf("%d\n", f[n][m]);
return 0;
}
01背包：
int main() {
int n, W;
scanf("%d%d", &n, &W);
for (int i = 1; i <= n; i++) scanf("%d%d", &w[i], &v[i]);
for (int i = 1; i <= n; i++)
for (int j = W; j >= w[i]; j--) // 逆序！
if (f[j - w[i]] + v[i] > f[j])
f[j] = f[j - w[i]] + v[i];
printf("%d\n", f[W]);
return 0;
}
编辑距离：
int f[1005][1005];
int main() {
scanf("%s%s", a + 1, b + 1);
int n = strlen(a + 1), m = strlen(b + 1);
for (int i = 0; i <= n; i++) f[i][0] = i;
for (int j = 0; j <= m; j++) f[0][j] = j;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (a[i] == b[j]) f[i][j] = f[i-1][j-1];
else f[i][j] = min(f[i-1][j], min(f[i][j-1], f[i-1][j-1])) + 1;
}
printf("%d\n", f[n][m]);
return 0;
}
常见坑点：
• 初始化：f[0] 的值决定了整个递推的正确性，容易漏看
• 转移方向：f[i] 从 f[i-1] 还是 f[j]（j < i）转移，方向错了全盘皆错
• 循环顺序：01背包必须逆序遍历体积（防止同一物品被选多次），完全背包正序
• 状态定义：注意 f[i] 表示"前i个"还是"以第i个结尾"，含义不同结果不同
• max与min：转移方程用 max 还是 min，看求最大值还是最小值
模板S4：DFS深度优先搜索
算法思路： 沿一条路径走到底，走不通就回溯，换一条路继续。
int dy[] = {1, -1, 0, 0};
char mp[105][105];
int vis[105][105];
int n, m, cnt;
void dfs(int x, int y) {
vis[x][y] = 1;
cnt++;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (mp[nx][ny] == '#' || vis[nx][ny]) continue;
dfs(nx, ny);
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) scanf("%s", mp[i]);
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (mp[i][j] == '@' && !vis[i][j]) {
cnt = 0;
dfs(i, j);
if (cnt > ans) ans = cnt;
}
printf("%d\n", ans);
return 0;
}
识别特征：
• 递归函数，参数含坐标或节点编号
• 有 vis 访问标记数组
• 方向数组 dx[]、dy[]
经典问题：
求迷宫路径数（需回溯恢复标记）：
int dy[] = {1, -1, 0, 0};
char mp[15][15];
int vis[15][15];
int n, m, ex, ey, ans;
void dfs(int x, int y) {
if (x == ex && y == ey) { ans++; return; }
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (mp[nx][ny] == '#' || vis[nx][ny]) continue;
vis[nx][ny] = 1;
dfs(nx, ny);
vis[nx][ny] = 0; // 回溯！求路径数必须恢复
}
}
全排列生成：
int n;
void dfs(int dep) {
if (dep == n) {
for (int i = 0; i < n; i++) printf("%d ", path[i]);
printf("\n");
return;
}
for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
vis[i] = 1; path[dep] = i;
dfs(dep + 1);
vis[i] = 0; // 回溯
}
}
常见坑点：
• 回溯忘记恢复标记：如果只是统计连通块大小，不用恢复 vis；如果是求路径数/排列，必须回溯恢复
• 方向数组：四连通 dx={0,0,1,-1}、dy={1,-1,0,0}，八连通多4个对角
• 剪枝：如果代码中有 if(ans > best) return 类似语句，是剪枝优化，可能提前终止
• 参数传递：注意坐标是传值还是传引用，传引用修改会影响回溯
模板S5：BFS广度优先搜索
算法思路： 用队列逐层扩展，先访问距起点近的节点，天然求无权图最短路径。
int dy[] = {1, -1, 0, 0};
char mp[105][105];
int vis[105][105], dis[105][105];
int qx[10005], qy[10005];
int n, m;
int bfs(int sx, int sy) {
int head = 0, tail = 0;
qx[tail] = sx; qy[tail] = sy; tail++;
vis[sx][sy] = 1;
while (head < tail) {
int x = qx[head], y = qy[head]; head++;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (mp[nx][ny] == '#' || vis[nx][ny]) continue;
vis[nx][ny] = 1;
dis[nx][ny] = dis[x][y] + 1;
qx[tail] = nx; qy[tail] = ny; tail++;
}
}
return -1; // 根据题目返回结果
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) scanf("%s", mp[i]);
bfs(0, 0);
printf("%d\n", dis[n-1][m-1]);
return 0;
}
识别特征：
• 手写队列（数组+头尾指针）或 queue
• while 循环取队首，扩展邻居入队
• dis 或 step 数组记录距离
经典问题：
逐层BFS（记录层数，求最少操作次数）：
qx[tail] = sx; qy[tail] = sy; tail++;
vis[sx][sy] = 1;
int step = 0;
while (head < tail) {
int sz = tail - head; // 当前层节点数
for (int k = 0; k < sz; k++) {
int x = qx[head], y = qy[head]; head++;
if (x == ex && y == ey) { printf("%d\n", step); return 0; }
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (mp[nx][ny] == '#' || vis[nx][ny]) continue;
vis[nx][ny] = 1;
qx[tail] = nx; qy[tail] = ny; tail++;
}
}
step++;
}
常见坑点：
• 入队时标记：必须在入队时设 vis，不能在出队时设——否则同一节点会重复入队
• 队列实现：手写队列用 head、tail 指针，注意 tail 是指向最后一个元素的下一个位置
• 层数计算：记录当前层节点数，每层处理完后步数+1
• 起点是否标记：起点入队时就要设 vis[start] = 1
模板S6：指针与引用操作
算法思路： 通过指针直接操作内存地址，实现高效的数据结构操作。
int val;
Node *next;
};
// 链表逆序
Node* reverse(Node *head) {
Node *prev = NULL, *cur = head;
while (cur) {
Node *nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
int main() {
int n;
scanf("%d", &n);
Node *head = NULL;
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
Node *p = new Node;
p->val = x;
p->next = head;
head = p;
}
head = reverse(head);
for (Node *p = head; p; p = p->next)
printf("%d ", p->val);
return 0;
}
识别特征：
• 大量 * 和 & 操作
• 可能涉及链表节点的 next 指针
• new / delete 动态分配
经典问题：
链表删除指定值节点：
Node* del(Node *head, int val) {
// 哑节点简化头删逻辑
Node *dummy = new Node;
dummy->next = head;
Node *p = dummy;
while (p->next) {
if (p->next->val == val) {
Node *t = p->next;
p->next = t->next;
delete t;
} else {
p = p->next;
}
}
head = dummy->next;
delete dummy;
return head;
}
指针交换值（传引用）：
void swap_val(int &a, int &b) {
int t = a; a = b; b = t;
}
int main() {
int x = 3, y = 5;
swap_val(x, y);
// x=5, y=3
}
常见坑点：
• 画内存图：指针题必须在草稿纸上画出节点关系图，追踪指针指向的变化
• NULL空指针：p->next 前必须确认 p 不为NULL
• 指针与数组：a[i] 等价于 *(a+i)，指针运算按元素大小偏移
• 引用不可重绑：引用一旦初始化就不可改变绑定对象，看起来像赋值实际是修改被引用对象
四、通用坑点总结（J/S组通用）
以下坑点在阅读程序中反复出现，不论什么算法都可能踩到。
1. 整数溢出
• int 最大约 2.1 × 10^9，两个 int 相乘可能溢出
• 阅读程序中看到 a * b 且 a、b 可能很大时，要考虑中间结果溢出
• long long 最大约 9.2 × 10^18
2. 循环边界差一
• for(i=0; i<n; i++) 循环 n 次
• for(i=0; i<=n; i++) 循环 n+1 次
• for(i=1; i<n; i++) 循环 n-1 次
• 这是最常见的丢分点，务必逐个确认
3. 逻辑短路
• a && b：a为假时b不执行
• a || b：a为真时b不执行
• 如果b有副作用（修改变量），短路会导致结果不同
4. ++i 与 i++
• a[i++]：先用i的值做下标，然后i加1
• a[++i]：先把i加1，然后用新i做下标
• 在循环条件和数组访问中影响巨大
5. 数组下标从0开始
• a[n] 的有效范围是 a[0] 到 a[n-1]
• 访问 a[n] 是越界
• 很多阅读程序故意在边界上做文章
6. 全局变量与局部变量
• 全局变量默认初始化为0
• 局部变量不初始化，值不确定
• 函数内如果定义了与全局同名的局部变量，局部变量"遮蔽"全局变量
7. do-while 至少执行一次
• do { ... } while(条件)
• 即使条件一开始就为假，循环体也执行一次
• 与 while 不同，while 可能一次都不执行
8. break 和 continue
• break 跳出当前循环
• continue 跳过本次循环剩余部分，直接进入下一轮
• 嵌套循环中 break 只跳出最内层
五、阅读程序做题方法论
第一步：快速通读，识别算法
拿到程序先从头到尾扫一遍，不纠结细节，回答三个问题：
1. 程序有几个函数？主函数结构是什么？
2. 有没有递归？有没有排序？有没有位运算？
3. 输入是什么？输出是什么？
根据上面梳理的模板特征，快速判断这段代码在实现什么算法。
第二步：标注变量含义
在草稿纸上写下每个变量的业务含义，不要只看变量名：
• i 是循环计数器？还是左指针？
• tmp 是临时变量？还是当前最小值？
• cnt 在统计什么？
第三步：用样例手动模拟
用题目给的样例输入，在草稿纸上逐行执行程序：
• 画表格记录每轮关键变量的值
• 循环嵌套要分层记录
• 递归要画递归树
第四步：验证选项
对每个选项，用以下策略快速判断：
• 代入特殊值：n=0、n=1等极端值
• 找反例：判断题中说"恒成立"，只需一个反例即可排除
• 排除法：先排除明显错误的选项
第五步：检查高频坑点
做完后回头检查是否踩了以下坑：
• 循环边界有没有看错？
• 整数除法有没有截断？
• 逻辑短路有没有影响？
• 递归出口有没有漏看？
• 变量有没有被意外覆盖？
六、考前练习建议
J组学生
1. 重点练习：模拟法、冒泡/选择/插入排序、基础递归、字符串处理
2. 每天做2道阅读程序，重点练"画表格追踪变量"
3. 把通用坑点打印出来，做题时逐条对照
S组学生
1. 在J组基础上增加：位运算、复杂递归、DP、DFS/BFS、指针操作
2. 每天做3道阅读程序，其中至少1道是S组难度
3. 重点练位运算的二进制展开和递归树的画法
4. 判断题特别注意"恒成立"类陷阱，构造反例是核心技能
最后提醒：阅读程序的核心就是"动笔"。所有变量变化、循环轮数、递归展开都要写在草稿纸上。不要试图用脑子记住所有状态——纸面Debug的能力，就是初赛最大的竞争力。祝你在阅读程序部分拿到35分以上！