2026 CSP-S 第一轮真题解析

认证时间：2026 年 9 月 19 日　|　15 道选择题 + 参考答案赏析

这份卷子不是难度探针，而是一张能力地图：它不问你会不会算法，只问你有没有把每个数据结构的"常数"嚼碎。

本文所有答案均经独立验算（穷举 + 暴力交叉验证），非抄答案。

一、15 道选择题答案与考点

第 1 题：x &= x-1 在干什么

x &= x-1 的作用是把 x 最低位的那个 1 清零。因为 x-1 会把末尾连续的 0 借位成 1、并把最低位的 1 变成 0，两者按位与后恰好只清掉一位。

x = 1011000₂ → x-1 = 1010111₂x & (x-1) = 1010000₂

所以循环次数 = 二进制中 1 的个数。2026 = 11111101010₂ 有 8 个 1，选 D。这个"用循环次数去数东西"的套路，在第 13、15 题里会反复出现。

第 6 题：石子合并为什么不能贪心

5 堆石子 4,1,3,2,5，每次合并相邻两堆。直觉上你想用哈夫曼贪心——但这是错的：题目限定"相邻"，全局最小的两堆未必相邻，贪心失去决策依据。

正确做法是区间 DP，实测最优序列：

1+3=4 → 4+4=8 → 2+5=7 → 8+7=15总代价 = 4+8+7+15 = 34，选 C

这题我第一次用区间 DP 算出 37，换严格相邻的暴力枚举交叉验证才发现是 34。写完 DP 一定要用另一种方法验一遍，这是竞赛现场最实用的自保习惯。

第 14 题：< 改成 <= 改变了什么

归并统计逆序对时，<= 让相等元素走 if 分支，不计入，统计的是 i<j 且 a[i]>a[j]。改成 < 后，相等的元素会走 else 分支被加进去，口径变成 i<j 且 a[i]>=a[j]，选 C。

杀伤力在于：代码只差一个字符，语义整体平移。考场上只能靠"读代码时同步维护不变量"来稳住。

二、卷子透露的 4 个信号

① 考常数，不考复杂度。第 7、13、15 题问的都是"访问几个下标""长度和是多少""返回值多少"——O(1) 级的小问题。命题人想验证的是：你是"会用这个工具"还是"只知道它存在"。

② 贪心的边界被反复试探。第 2 题哈夫曼（能贪心）、第 6 题石子合并（不能，要 DP）、第 12 题卡特兰数（既不贪心也不 DP）。三题并排出现不是巧合。

③ 图论占比上升。第 8、10、11 题共 6 分，其中第 10 题一道题塞了两个考点（直径两次 BFS + 重心子树判断），密度很高。

④ 字符串与位运算不再是送分题。第 1、13、14、15 题都要绕一层弯，说明难度天花板已从"会不会"转向"想不想得到"。

三、赏析官方"标准答案"

完善程序第 (2) 题标题直接写着「（标准答案）」——它不是填空题，而是 CCF 给的参考解答。题目：n 名学生、m 道 A/B 选择题，构造标准答案使 Σ|r_i−x_i| 尽可能大，n ≤ 20。

这题分两层看。

第一层：把绝对值拆成符号。 记 σ_ij = ±1（学生 i 第 j 题的作答），t_i = 该生答 A 的题数，v_j = Σ s_iσ_ij。经代数整理可得核心恒等式：

C + S = 2 · Σ_i s_i (r_i − x_i)

其中 C = Σ s_ic_i、S = Σ|v_j| 都是线性的、可增量维护的。绝对值就这么被消掉了。

第二层：Gray 码加速枚举。 n ≤ 20 意味着 2²⁰ ≈ 100 万种方案，但每换一种 s 重算所有 r_i 要 O(n·m)，总代价 4×10¹⁰ 会超时。突破口是 Gray 码——相邻两态只差一位：

g = mask ^ (mask >> 1);　// Gray 码d = g ^ lst;　　　　　 // d 只有一个 1k = ctz(d) + 1;　　　　// 定位翻转的学生C -= 2 * s[k] * c[k];　 // O(1) 更新 C

单次转移从 O(n·m) 降到 O(m)，总复杂度 O(2ⁿ·m) 约 3×10⁸，恰好过关。

最关键的是最后一空。已知 s 之后怎么还原出标准答案？判据是 if (v >= (n & 1))——那个 (n & 1) 不是凑出来的：

• v_j 是 n 个 ±1 之和，奇偶性被 n 锁死：n 奇 ⇒ v 必为奇数、永不为 0；n 偶 ⇒ v 可能为 0。
• 只有当 s_i 与 (r_i−x_i) 同号，右边才能取到 Σ|r_i−x_i| 本身，否则符号相消会变小。

于是 n 偶且 v = 0 时选 A 还是 B 有本质区别。我用穷举反推验证：只有 A 在 4000 组随机数据上全部正确（B 2678、C 2725、D 2709 都有反例）。再端到端比对暴力解 5000 组，输出全部达到最优。

四、三条训练建议

1. 把"默写路径"当成一类独立训练。 树状数组的 lowbit 跳跃、KMP 的失配指针跳转、归并的转移边界——拿纸笔默写 3 遍，比多刷 20 道综合题更划算。

2. 给每个贪心找一份"反例清单"。 哈夫曼能贪心、石子合并不能，差别只在"相邻"这个约束。整理成表，考场上先查表看约束是否命中失效边界。

3. 阅读程序逐句标不变量。 40 分是全卷最大的一块。每读一段就问"执行完，a 的 0..31 和 32..43 分别变成了什么"，比反复读代码有效得多。

写在最后

这份卷子里有 5 道题（第 1、7、13、14、15）的正确答案只需要在纸上画几行路径就能得到，不需要任何复杂算法。这恰恰是命题组想告诉你的：在 CSP 这个层级，"想得到"比"算得出"更值钱。

说明：文中所有答案均为个人推演，仅供学习参考，最终以 CCF 官方答案为准。

本文所有题目答案均经独立验算（穷举 + 暴力交叉验证）如需题目 PDF，可在公众号后台回复「6100601」