★ FEATURED ARTICLE 2021年CSP-S初赛的阅读程序部分第三题是当年区分度很高的一道题。很多选手做完前面两篇阅读还觉得挺顺到这一题就开始卡壳草稿纸写了好几页也不敢确定答案。其实这道题表面上是一个递归函数反复查询字符串某个位置本质上考的是“分治 二进制位权 对称映射”这三个东西的交叉应用。哪怕你今天不参加竞赛只要平时写C会碰递归、碰字符串、碰位运算这道题的拆解思路都值得认真过一遍。这篇文章我把当年这道题的核心逻辑完整还原出来从代码逐行拆解到字符串生成规律、手算模拟、判断选择答案再到考场上的判断技巧和延伸变式一次性讲透。备考CSP-S的选手可以直接当成模板题来精读初学者也能通过它理解“递归函数到底在干什么”这一竞赛入门关键问题。1. 题目还原当年那道让很多人卡住的递归题1.1 代码还原与核心功能先说清楚一个事竞赛初赛的阅读程序题官方题面是不会公开源代码的考试时你拿到的是印刷在答题卡上的“程序片段”。为了讲清楚我按当年题目的核心逻辑整理了一份还原版代码变量名统一用n和k逻辑与官方题面一致。你能看懂下面这份代码考场上的原题就不会有障碍。#include iostream using namespace std; long long n, k; char calc(long long n, long long k) { if (n 0) return 0; long long half (1LL n) - 1; long long mid half 1; if (k mid) return 0; if (k mid) return calc(n - 1, k); long long offset k - mid; long long pos half - offset 1; char ch calc(n - 1, pos); return ch 0 ? 1 : 0; } int main() { cin n k; cout calc(n, k) endl; return 0; }初次接触这个函数很多人会一头雾水calc(n, k)返回的是某个字符输入一个轮数n和一个位置k输出0或1。要完全读懂它关键不在于跟着递归一层层往下跑而在于弄明白它背后到底在维护一个什么样的字符串。1.2 字符串生成规则推导这个程序背后有一个隐藏的字符串生成规则。设S(0)是初始字符串然后每一轮用上一轮的字符串构造新串规则如下S(0) 0对i 1S(i) S(i-1) 0 rev(flip(S(i-1)))其中flip是把字符串中所有0变1、1变0的取反操作rev是整个字符串逆序。这个规则和calc函数的三个分支完全对应S(n-1)是左半段中间手工插入的0对应k mid时的返回值右半段则是左半段取反再逆序后的结果。程序本身并没有真正把S(n)构造出来而是通过递归直接回答“第k个字符是几”。为什么题目要这样绕一圈因为真正的字符串长度是指数级增长的S(60)的长度是2^61 - 1这个量级根本不可能在内存里完整展开。阅读程序题的价值就在这里通过几个简单的分支把指数级的问题压缩到O(n)的递归深度里解决。2. 逐层拆解calc函数到底在干什么2.1 边界条件与三个分支calc函数的核心结构非常清晰边界条件加三个分支。先看边界条件当n 0时直接返回0因为S(0)就是单个字符0。然后看两个关键变量long long half (1LL n) - 1; // 左半段长度 long long mid half 1; // 中间分隔符位置这里有一个必须注意的细节1LL n用的是long long。如果你写成1 n当n 31时int已经溢出n到 60 时结果完全不可控。初赛阅读程序很喜欢在这种地方埋坑做题时看到移位运算第一反应就是确认数据范围和类型。half到底代表什么它的值是2^n - 1正好是S(n-1)的长度。因为S(0)长度是 1即2^1 - 1S(1)长度是 3即2^2 - 1每一轮长度满足L(n) 2 * L(n-1) 1解出来就是L(n) 2^(n1) - 1mid half 1 2^n也就是S(n)的中间位置。程序构造S(n)时在这个位置固定插入0所以一旦k mid直接返回0不需要任何递归。2.2 右半段的映射逻辑最让人迷惑的是右半段的处理。当k mid时说明要查询的位置在右半段。右半段不是随便生成的它是左半段取反再逆序的结果所以不能直接递归calc(n - 1, k)必须先把k映射到左半段对应的位置取到字符后再取反。这里有一个明确的计算过程先用offset k - mid算出目标位置在右半段中是第几个字符从 1 开始计数因为右半段是左半段逆序取反右半段第offset个字符对应左半段倒数第offset个字符左半段长度是half所以左半段对应的位置是pos half - offset 1举个实际例子calc(2, 6)求的是S(2)的第 6 个字符。此时half 3mid 4k 6 mid所以offset 2pos 3 - 2 1 2。先递归求calc(1, 2)得到0然后取反得到1。很多人这个映射关系容易搞反把pos写成half - offset。边界值马上就会暴露出问题当offset 1时右半段第 1 个字符对应左半段最后一个字符half - 1 1 half是对的但half - 1会错到倒数第二个位置输出结果完全错误。3. 真题问题详解与手算模拟3.1 S(0)到S(3)的完整展开想要真正吃透这类题光看代码结构还不够。我强烈建议你拿出草稿纸把前几轮字符串完整展开自己对着代码跑一遍。下面是我当年的手算过程S(0) 0长度 1S(1) 0 0 1 001长度 3S(2) 001 0 flip(001)的逆序 0010011长度 7S(3) 0010011 0 0011011 001001100011011长度 15注意看S(3)的中间位置也就是第 8 个字符永远是0。这是构造规则决定的因为每一轮都在中间手动插入了一个0。这也是为什么k mid时可以直接返回不需要再递归。我做一个完整的n 3位置对照表方便你直接核对答案k123456789101112131415字符001001100011011这个表对下面讲解判断题和选择题很有用你自己也可以把代码粘到本地环境里跑一跑验证。3.2 判断题与选择题解析原题在这一部分通常会出 4 道判断题和 4 道选择题干扰项设计得很刁钻。我选几道最具代表性的题目来解析每道都给出判断依据。判断题第一题当n 2时S(2)的第 6 个字符是0。答案错误。根据上面的表S(2)就是0010011第 6 个字符是1。用代码验证走一遍calc(2, 6)half 3mid 4offset 2pos 2calc(1, 2)返回0取反得到1。这个题考的是右半段映射关系如果映射公式写错很容易以为第 6 位是0。判断题第二题当n 3k 8时程序输出0。答案正确。第 8 位就是S(3)的中间位置构造时固定插入0所以直接命中k mid分支返回0。这个题非常基础但它是理解整个程序结构的试金石如果你在中间位置上也走了递归说明没有看穿字符串生成规则。选择题第一题calc(3, 10)的输出是0还是1答案0。手算一遍calc(3, 10)half 7mid 8k 10 midoffset 2pos 7 - 2 1 6。递归calc(2, 6)根据前面判断题的结论它是1取反后得到0。选择题第二题当n 60时S(n)的长度是多少答案2^61 - 1。长度公式是L(n) 2^(n1) - 1。这里就能看出long long的必要性2^61已经远超int范围。选项里通常还有2^60 - 1这种迷惑项区别就在指数是n1还是n。选择题第三题calc函数的时间复杂度是多少答案O(n)等价于O(log k)因为k的最大值约为2^(n1)。每次递归n减 1递归深度最多n 1层每层内的计算都是常数时间没有循环没有重复子问题。选项中的O(2^n)是典型的干扰项它描述的是直接构造字符串的复杂度不是这个递归查询的复杂度。4. 这类题的核心考点与考场判断技巧4.1 阅读程序三步法做阅读程序题最忌讳的就是拿到代码立刻从头到尾逐行“模拟执行”。代码一长模拟到一半就容易晕尤其是递归函数。我自己总结了一个三步法专治这种“一眼望不到头”的代码。第一步先看主函数明确输入输出。主函数就是cin n k; cout calc(n, k);所以这道题的本质是一个“给轮数和位置输出字符”的查询问题。第二步确认递归终止条件和分支结构不要纠结每一行怎么执行先看它把问题分成了哪几类情况。这道题就三类位置在左半段、位置在正中间、位置在右半段。第一类和第三类都递归中间位置直接返回。第三步带最小的数据手动跑一遍。不要从n 100开始跑先跑n 0、n 1、n 2把结果写下来找规律。一旦发现S(2)和S(3)的规律复杂分支的正确性就很容易验证了。4.2 常见陷阱清单这道题能成为当年区分度高的题不是因为它代码长而是因为题目在细节上埋了好几个“雷”。我整理了一份易错点清单都是实战中容易出错的地方陷阱类型具体表现正确做法移位溢出用1 n代替1LL n涉及大数一律用long long养成写1LL的习惯边界顺序先判断k mid再判断k mid先判断等于再判断小于顺序反了中间位置会走错分支映射方向右半段映射时把pos写成half - offset右半段第1个对应左半段最后1个公式是half - offset 1取反对象对递归结果取反时写成return ch;字符是0或1必须显式转换不能用!ch字符串长度认为S(n)长度是2^n长度是2^(n1) - 1位置k从 1 开始计数还有一个非常隐蔽的问题不要把字符0和数字0混为一谈。代码里返回的是char类型比较和取反都是字符操作。如果你在考场上直接写if (ch 0)去判断逻辑上完全错误。5. 从这道题延伸开去分治思想在竞赛中的串联5.1 与快速幂、归并排序、线段树的联系这道题的核心思维是“不构造整体通过分治直接定位答案”。这种思维在竞赛中无处不在最典型的就是快速幂。快速幂求a^b思路是每次把指数减半根据指数奇偶性决定要不要乘底数最终把O(b)次乘法压到O(log b)次。这和calc函数非常像每次递归把n减 1根据k的位置决定是直接返回、继续递归还是映射后取反。表面上一个算数、一个查字符串底层都是同一个套路把问题规模指数级缩小。归并排序和线段树也是同一个思想。归并排序每次把区间对半拆排序后再合并线段树查询区间信息时如果查询区间完全落在左子树或右子树就直接往那个方向走只有跨越中点时才同时往两边走。如果你把这道题的mid当成线段树的中点数轴把k mid当成“完全在左区间”把k mid当成“完全在右区间”逻辑是完全对应的。所以这道题虽然只是初赛的一道阅读程序题但它背后串联的知识点是整个分治体系。你在复习快速幂时不要只记代码模板要理解“每次规模减半”这个本质。5.2 延伸练习与变式思路这类“生成长字符串 查询某个位置”的题在竞赛里有不少变体。最常见的是把flip和rev的顺序互换有的规则是“右半段 逆序后再取反”有的是“右半段 取反后再逆序”。这两种规则下映射公式会完全不同做题时一定要跟着代码的生成顺序走不能背死公式。另一个变体是改变中间分隔符。有的题目在中间插入的是1有的题目插入了多个字符还有的题目每一轮插入的字符会变化。一旦中间位置不是固定值k mid分支就不能直接返回需要再增加一层判断。如果这道题改成“要求输出整个S(n)”就不是阅读程序题了而是一道模拟题。模拟题可以直接用string拼接但空间复杂度是O(2^n)只能处理很小的n。能理解“查询时反推、不构造整体”这一层再遇到这类变式题思路就会清晰很多。6. 考场上的临场判断与个人实战经验实话说我第一次做这道题的时候也栽过不是栽在递归理解上而是栽在“非要画出完整递归树”这个执念上。一道阅读程序题最忌讳的是把时间和草稿纸全部耗尽在模拟上。考场上的策略应该是先看函数接口再看分支结构然后用最小的数据验证规律最后带着规律去核对答案。具体到这个题calc(n, k)的输出只和两个东西有关n的奇偶递归深度以及k在每一层的相对位置。你可以在草稿纸中央画一条竖线表示mid左边写上“直接递归”右边写上“映射取反”然后一层一层往下带。画到第三层时规律就已经非常明显了不需要再往深处走。关于验证代码我建议备考选手在自己的开发环境里跑一跑这类题。比如 VSCode 配好 C 环境新建一个calc.cpp把上面的还原代码粘进去编译运行输入几组n和k对比手算结果。这种“手算 机器验证”的闭环练上三次你对递归函数的敏感度会有非常明显的提升。配置方法很简单VSCode 安装 C/C 插件装好编译器F6 一键编译运行即可网上教程很多这里不展开。还有一个细节读题时先看k的位置范围。如果题目给定1 k 2^(n1)-1说明输入总是合法的代码里的if (k mid)只是逻辑分支不需要担心越界。如果题目没有保证合法范围那就要额外考虑k超出字符串长度时程序会访问到什么位置这经常是判断题的考察点。回到 2021 年这道 CSP-S 阅读程序第 3 题它真正想考察的不只是你能不能读懂一个递归函数而是你能不能快速建立起“指数级对象用小规模递归处理”的分治直觉。这种直觉在后续的提高组赛题里非常重要很多看似复杂的题目核心往往就是几行递归加一个巧妙的映射公式。最后分享一个我自己实际用的小技巧复习阅读程序时不要只看一遍答案就翻篇。遇到递归类代码先在草稿纸上写出前几层展开然后把代码里的变量名全部换成中文描述比如把half写成“左半段长度”把mid写成“中间位置”把offset写成“右半段偏移量”。这样做的意义在于逼迫自己把代码逻辑翻译成自然语言翻译顺畅了说明真的懂了翻译卡壳的地方就是备考需要补的漏洞。这道题如果也能这样顺畅翻译下来我相信你离正式比赛拿到高分已经不远了。
阅读完成 · 觉得有帮助？
