每年CSP-S初赛结束后群里讨论最多的往往不是完善程序而是阅读程序题。2024年信奥赛C提高组CSP-S初赛中阅读程序第1题又是一道非常典型的递归子集枚举题代码不长但能把递归执行流程、取模运算、时间复杂度分析这几个核心考点全都串起来。这篇文章不打算只丢一个“选B”式的参考答案而是带你从头到尾把程序拆明白把容易踩的坑一个个指出来。不管你是第一次备考CSP-S的新手还是已经刷过几年真题的老选手应该都能从里面拿到一点能直接用到考场上的东西。1. 真题回顾2024年CSP-S初赛阅读程序第1题1.1 原题核心代码还原我先根据考后选手回忆把这道题的核心代码整理出来。这道题当年的代码风格非常“标准”一上来就是全局变量、递归函数、循环初始化数组看起来很友好但稍不注意就会在细节上翻车。#include iostream using namespace std; int n, k, ans; int a[100]; void dfs(int step, int sum) { if (step n) { if (sum % k 0) ans; return; } dfs(step 1, sum a[step]); dfs(step 1, sum); } int main() { cin n k; for (int i 1; i n; i) { a[i] i * 2 - 1; } dfs(1, 0); cout ans endl; return 0; }题目给出输入6 3要求判断程序输出是多少同时还有几道关于程序功能、时间复杂度以及递归顺序影响的选择题。这类题在初赛里属于“看着简单做起来容易慌”的类型因为递归一旦展开手算路径会很多如果不掌握方法很容易算到一半就乱掉。1.2 这道题到底在考什么从考点分布来看这道题其实同时覆盖了CSP-S初赛的多个高频知识点。一是递归与分治思想。dfs函数有两个递归分支分别对应“选当前数”和“不选当前数”本质上就是枚举所有子集。这是信奥赛里最基础也最核心的模型之一CSP-J考过CSP-S也考只是换层皮而已。二是取模运算与整除判断。sum % k 0看起来很简单但很多选手在考场上一紧张会把“余数为0”和“sum等于k”搞混。题目选项里就专门设置了这类干扰项。三是时间复杂度分析。每次递归都有两路分支递归深度是n所以总状态数是2的n次方这是典型的指数级复杂度。这个知识点在选择题部分也常考放到阅读程序里就是问你“n10时程序大概跑多少次递归调用”。四是全局变量的作用域理解。ans是全局变量在递归调用里可以直接累加修改。如果把ans改成函数局部变量整个程序的功能和写法就全变了。这类“改一处代码看结果变不变”的判断题几乎是初赛阅读程序的保留题目。2. 代码逐段剖析看懂程序比背答案更重要2.1 全局变量与数组初始化代码开头定义了int n, k, ans;和int a[100];这四个变量全部是全局变量。全局变量的特点是默认初始化为0并且在程序的整个运行期间各个函数都能直接访问和修改。尤其要注意ans它在这里承担的是“统计答案”的角色。在递归程序中如果统计变量只在一个递归分支里修改别的分支看不到那结果就会出错。用全局变量则不存在这个问题所有递归调用共享同一个ans。我自己带学生的时候经常强调阅读程序题里只要看到ans又在递归函数里那八成考的就是全局变量共享。数组a的大小是100说明n不可能太大这个细节可以用来辅助判断极端输入范围。主函数里用循环生成a[i] i * 2 - 1这一步很关键。它生成的序列是 1, 3, 5, 7, 9, 11…… 也就是前n个奇数每个数对3取模的结果有规律可循。2.2 dfs函数的执行逻辑dfs函数接收两个参数step表示当前处理到第几个数sum表示已经选中的数字之和。函数的递归底是step n也就是所有数都处理完了此时如果当前子集和能被k整除ans就加1。这个“选/不选”的分支结构非常经典dfs(step 1, sum a[step])表示把第step个数放入子集dfs(step 1, sum)表示不选第step个数。由于每次递归都会让step加1最多递归到step等于n1因此不会出现死循环。整棵递归树的叶子节点正好对应原序列的所有子集数量是2的n次方个。理解了这个逻辑程序的功能就很清楚了统计所有子集中元素和能被k整除的子集个数空集也包含在内。2.3 主函数的数据入口与执行顺序主函数先读入n和k然后循环初始化数组a最后调用dfs(1, 0)并输出ans。这里有个小细节dfs的初始step是1不是0因为数组元素从下标1开始存放。如果你在模拟的时候习惯性地从0开始数就会漏掉a[1]这个数得到的答案就会差很多。输入样例是 n6, k3。程序实际生成的序列是 1, 3, 5, 7, 9, 11。这6个数按对3取模的结果可以分成三类余1的有1和7余2的有5和11余0的有3和9。利用这个规律我们不需要真的把64个子集全都列出来也能算出答案。3. 答案与手算模拟带你一步步跑完整个程序3.1 四个问题的答案速览我把原题的几个问题整理成表格方便对照题号问题正确答案第1问输入 6 3程序输出为B24第2问程序实现的功能是B统计子集和为k的倍数的子集个数第3问当 n10 时算法时间复杂度约为BO(2^n)第4问交换两行递归调用顺序输出会变吗C不变枚举的子集完全一致答案看起来简单但每一问背后都有值得展开的东西。下面我把手算过程完整写一遍。3.2 输入6 3的完整递归过程模拟先看递归树的形态。从dfs(1, 0)开始函数会一直往sum a[step]这个分支走直到 step7也就是处理完第6个数才会返回。然后回溯到上一层走sum分支。最终会访问到所有2的6次方也就是64个状态。手工模拟不需要把64个状态全部画出来那样太浪费时间。正确做法是分层观察。当step等于7时sum的取值就是某个子集的和程序判断sum % 3 0满足就ans加1。如果只是想验证答案可以用分类计数。a数组是 1, 3, 5, 7, 9, 11其中余0的数3、9共2个余1的数1、7共2个余2的数5、11共2个。一个子集的和能被3整除等价于“余1的数的个数”和“余2的数的个数”在模3意义下相等。这句话可能有点绕我举个例子如果某个子集只选了1和5和为6能被3整除。1对应余15对应余2两个数抵消了。如果选了1、7、5和是13不能被3整除因为余1的数有2个余2的数只有1个抵消后还多一个余1。由于每一类分别只有2个数所以余1和余2的选择数量只有三种匹配都不选、各选1个、各选2个。具体用组合数算余1选0个余2选0个组合数 C(2,0) × C(2,0) 1余1选1个余2选1个组合数 C(2,1) × C(2,1) 4余1选2个余2选2个组合数 C(2,2) × C(2,2) 1。这三类加起来是1加4加1等于6种。而余0的数选或不选完全不影响整除性所以有C(2,0)加C(2,1)加C(2,2)等于4种。最终答案就是6乘4等于24。3.3 为什么递归顺序不影响答案题目问交换两行dfs调用顺序会不会改变输出答案是不变。这里要理解的关键点是递归本质上只是改变了遍历子集的顺序并没有改变子集本身。dfs(step 1, sum a[step])和dfs(step 1, sum)的组合等价于“第step个数选或不选所有可能性的笛卡尔积”。可以类比一下翻扑克牌你从左边翻到右边和从右边翻到左边最后看到的牌面组合是一模一样的只是看到的先后顺序不同。程序里ans统计的是满足条件的子集个数只要枚举的集合不变结果就不会变。有不少选手在看到“交换顺序”这种题时会犹豫甚至怀疑会不会影响递归深度或造成死循环。这道题里不会。递归深度只由step从1增长到n1这个路径决定与左右分支谁先执行无关。除非你把递归出口写错否则不可能死循环。3.4 容易踩的坑全局变量、取模优先级、边界范围这类题最经典的坑有三个。第一个坑是把ans的累加位置理解错。有些选手以为ans只会在某个分支中执行或者以为递归返回时ans会被“还原”。实际上全局变量只存在一份所有递归层共享不存在“还原”的概念。如果题目把ans改成int局部变量并作为参数传递那逻辑才会完全不同。第二个坑是sum % k 0里的取模优先级。%的优先级高于所以程序实际含义是(sum % k) 0。不要读成sum % (k 0)后者是非法的。这属于C运算符优先级的基本功初赛每一届都会考。第三个坑是数组下标从1开始。初始化循环是i 1; i n; i递归入口是dfs(1, 0)。如果你习惯0-based思维很容易漏掉a[0]这个不存在的元素或者多算一个导致答案偏移。这种错误在考场上特别隐蔽因为程序本身不会报错但你手算模拟的时候对不上。4. 从这一题看CSP-S阅读程序题的通用解题套路4.1 阅读程序题的“三步走”很多选手拿到阅读程序题第一反应是“从头到尾逐行读”这个方法不能说错但效率很低。我总结了三个步骤用在这道题上非常合适。第一步是确定数据结构与全局变量。先看定义了哪些变量是数组、指针还是STL容器。这道题一眼就能看到int a[100]和全局变量n, k, ans数据结构很简单。第二步是识别核心算法模型。看到递归里有两个dfs调用就要立刻想到这是子集枚举。如果看到for循环嵌套就要考虑是不是冒泡排序变体或矩阵遍历。很多阅读程序题不是让你“理解每一行”而是让你“认出是什么模型”。第三步是带着问题去模拟。先看题目问什么再去程序里找对应的部分。比如题目问“时间复杂度”你根本不需要模拟递归过程只看递归深度和分支数就够了。题目问“输入6 3输出什么”才需要进入具体的手算模拟。4.2 考场时间分配与快速验算技巧CSP-S初赛总共21道选择加3道阅读程序加2道完善程序时间相对紧张。阅读程序三题一般建议控制在25到30分钟不能在一道题上死磕。如果某道题模拟到第三问还没有头绪可以先跳过后面的题最后再回头补。快速验算有个实用技巧把程序在草稿纸上“翻译”成更直观的枚举过程。比如这道子集枚举题你可以直接把a数组列出来然后按“余数分类”重新排列成三组。这样做的好处是看到“统计整除子集个数”这类问题时不需要一棵一棵画递归树直接用组合数学就能快速锁定答案。我在做这类题时还有一个习惯就是先判断结果数量级。比如输入6 3一共有64个子集那么答案一定在0到64之间。选项中如果有128或者256这种明显超范围的可以直接排除。这种“边界思维”在考场上能救命。4.3 常见考点与知识框架梳理从这道题延伸出去CSP-S阅读程序题的高频考点其实非常固定。我整理了一份自用的知识框架考点方向常见出题方式对应备考重点递归与回溯子集枚举、排列生成、DFS搜索递归树画法、终止条件排序算法变体冒泡排序、选择排序过程模拟交换次数、边界判断字符串处理字符数组比较、大小写转换ASCII码、下标细节位运算按位与、或、异或、移位优先级、二进制手工转换数据结构栈、队列、链表模拟先进后出、先进先出STL模板sort、vector、map使用排序规则、迭代器越界时间复杂度循环层数、递归分支数常见复杂度量级估算备考的时候不用去找偏题怪题把近五年真题刷透把每一道阅读程序的代码都亲自跑一遍比做十套模拟题都管用。5. 延伸与变式如果题目换个问法或改个参数5.1 变式一把k从3改成4如果题目把 k3 改成 k4答案会怎么变这是阅读程序题常见的“改参数”式追问本质上还是在考取模与组合计数。a数组还是 1, 3, 5, 7, 9, 11。对4取模余11、5、9共3个余23、7、11共3个余0和余3的没有。要让子集和能被4整除余1的个数和余3的个数需要匹配同时余2的个数必须为偶数。由于这里没有余3的数余1的数选了就一定会让和余4所以余1的数一个都不能选。余2的数必须有偶数个可选0个或2个。余1和余3都不选余2选0个或2个一共2种再加一个空集和一个只选3、7、11的情况。答案会明显小于24。这个变化说明同一个程序只要改变输入的k统计逻辑就需要重新分析不能背答案。5.2 变式二把n改成30或40另一个常见追问是n变大了怎么办。这个程序本质上是在枚举子集时间复杂度是O(2^n)。当n20时大约100万次调用1秒内能跑完n30时10亿次级别已经非常吃力n40时直接跑会超时。这种复杂度限制在CSP-S提高组的题目里是必须要注意的。如果题目想考更高效的做法通常会改成“用动态规划统计有多少个子集和能被k整除”或者用“折半搜索”把2^40降成2^20加2^20也就是先枚举前半部分再枚举后半部分用哈希表合并答案。虽然初赛阅读程序不会真的要求你写优化代码但理解这类复杂度演进会帮助你在“程序的时间复杂度是多少”这种问题里快速排除错误选项。5.3 刷题建议把初赛题当程序题来做我一直建议身边备考的同学不要只在纸上做阅读程序题最好把每道题都敲进编译器里跑一遍甚至主动改代码验证想法。比如这道子集枚举题你可以把k3改成k4或k5把n从6改成8再对比程序输出和你手算的答案。这样做至少有三个好处一是能立刻发现你对递归过程的理解是否准确二是能帮你积累“看到代码就能预判结果”的感觉三是能让你更熟悉编译器报错和调试工具对后续复赛也有帮助。CSP-S初赛和复赛的知识点本来就是相通的初赛里遇到的递归、排序、DP、图论基础复赛里全都会再次出现。我在实际带训练的时候发现很多选手初赛失分不是因为不会写代码而是读代码时缺少耐心。阅读程序题其实是在模拟“别人写的代码”以后你不管参加比赛还是做项目都要面临读别人代码的情况这项能力值不值得认真练答案很清楚。就我个人经验来说做阅读程序题最好的状态不是“我把每一行都背下来了”而是“我看到代码结构就知道程序在算什么”。比如看到两个递归分支马上想到了子集枚举看到三层的for循环内部带交换马上想到了冒泡排序。这种条件反射不是靠刷题量堆出来的而是靠每做完一道题之后反复追问“为什么这样写”得到的。建议你从今天这道题开始把每个你不确定的模拟过程都写下来再跑一次程序验证坚持一段时间阅读程序的正确率会有明显提升。