CSP-S初赛阅读程序真题详解：反转与二进制1计数

CSP-S初赛的阅读程序题一直是很多选手的“心理阴影”。尤其是2019年作为CSP认证的第一年阅读程序第一题就埋了个不大不小的坑代码看起来就是两个平平无奇的while循环但要做对全部5个小题你得同时搞定十进制数字反转、二进制1计数、边界输入三个知识点。这篇文章我直接把这题完整还原从逐行模拟到结论一步步拆开讲最后再分享一套我刷了几百道阅读程序题总结出来的通用拆解思路准备参加信奥赛或者正在备战CSP-S的同学都可以参考。1. 真题还原2019年CSP-S阅读程序第1题到底长什么样1.1 完整代码与试题结构先直接把原题代码放出来这题不涉及任何库函数技巧代码非常简洁#include cstdio using namespace std; int main() { int n; scanf(%d, n); int x 0, ans 0; while (n 0) { x x * 10 n % 10; n / 10; } while (x 0) { ans x % 2; x / 2; } printf(%d\n, ans); return 0; }这是2019年CSP-S提高组第一轮认证也就是大家常说的初赛里“阅读程序”部分的第1题。整道题一共5个小题前3个是判断题每个2分后2个是选择题每个3分合计12分。放在整张卷子里这道题算是最温和的开场因为代码很短没有任何复杂的数组、递归、指针操作。但从当年的实际得分情况看它反而是阅读程序部分区分度很高的一道——原因是它考的不是“会不会写代码”而是“能不能一眼看出这段代码在干什么”。1.2 考点定位两个循环拼接的背后这道题表面上考两个while循环实际上密集覆盖了四个基础知识点十进制数字的拆分与重组取余、整除数字倒序反转的经典实现二进制位中1的个数统计popcount边界输入0、负数、回文数、大整数的处理。这四个知识点单独拿出来任何一个学过循环的小选手都能写对。但组合在同一个程序里再套上判断题的“文字游戏”很多人就绕进去了。我见过太多选手在第一题上纠结超过十分钟原因只有一个他没有先问“这段代码干了什么”而是直接埋头开始手算模拟。后面我会详细展开这个方法论问题这里先记住一个结论——阅读程序题的答案从来不在逐行模拟里而在语义抽象里。1.3 2019年这届初赛的特殊背景2019年是CSP认证正式登场的年份。在此之前大家更熟悉的是NOIP全国青少年信息学奥林匹克联赛CSP-S提高级考试的题型和难度基本延续了NOIP时代的风格尤其是“阅读程序”这种题型保留了“给一段代码判断输出、判断结论”的老传统。不过2019年的题目在细节上明显更注重“理解”而不是“计算”。这道第1题就是一个信号如果你只会照着循环一步步算遇到大一点的数据就要花很长时间如果你能看出“反转数1”的组合题目其实相当友好。所以备考CSP-S的同学千万不要把阅读程序题当成“模拟题”来练而是要当成“读心题”来练——读出出题人设计这段代码时想考的那个知识点。这道题的考点组合在后续几年里被反复使用算是“拼接型阅读题”的经典模板。2. 逐行拆解两个循环分别干了什么“脏活”2.1 第一个循环把n的十进制数字倒过来先看第一个whilewhile (n 0) { x x * 10 n % 10; n / 10; }n % 10 取出n当前的个位数字x * 10 这个数字把个位追加到x的末尾n / 10 删掉n的个位。循环每执行一次x的位数就多一位同时n的位数就少一位直到n变成0。新手最容易在这段代码上犯的错误我总结过三个以为循环结束条件是 n 0。实际上n0时就不进循环了所以n0以及所有负数进来x会一直保持在初始值0。搞混x和n的更新顺序。注意这里是先更新x再更新nn / 10 用到的还是旧的n所以不会出错。但如果你把两行顺序反过来用新n的%10就会丢数字。忘记第一个循环结束后n已经变成0。第二个循环操作的是x不是n。这个错误听起来很低级但人脑模拟代码时真的很容易模拟到后面就忘了变量当前是谁。以n12345为例手动迭代一次| 步骤 | 循环前的n | x x*10 n%10 | 循环后的n | | 0 | 12345 | 0 | — | | 1 | 12345 | 5 | 1234 | | 2 | 1234 | 54 | 123 | | 3 | 123 | 543 | 12 | | 4 | 12 | 5432 | 1 | | 5 | 1 | 54321 | 0 |循环结束后n0x54321。这个循环的本质就是“十进制数位倒序”也就是 reverse(n)。一个很直白的理解方式x是在“从低位往高位重建”这个数字每次取到的低位都拼到x的末尾最后x就是原数倒过来的样子。2.2 第二个循环数一数x的二进制里有几个1接着看第二个whilewhile (x 0) { ans x % 2; x / 2; }x % 2 取的是x二进制表示的最低位ans x % 2 把这一位累加进答案x / 2 等价于把x的二进制位整体右移一位。循环一直执行到x变成0为止。换句话说这个循环就是手写的popcount统计一个整数二进制表示中1的个数。如果写成位运算版本大家会更眼熟while (x 0) { ans x 1; x 1; }效果完全一样。拿x13举例13的二进制是1101841模拟一遍第一次循环ans 113的二进制1101最低位是1x6第二次循环ans 06的二进制110最低位是0x3第三次循环ans 13的二进制11最低位是1x1第四次循环ans 11的二进制1最低位是1x0结束ans3。13的二进制1101里正好有3个1。这个循环还有个容易被忽视的性质它执行完后x一定会变成0。所以整段程序最终输出的ans就是“reverse(n)这个数的二进制表示里1的个数”。这个性质是解题的钥匙后面所有判断题和选择题都建立在这句话之上。2.3 合起来跑一遍n123456的完整跟踪为了展示两个循环的整体行为我把n123456的完整状态变化写出来这也是后面选择题第1问要计算的核心过程。第一个循环阶段| 迭代 | 循环前的n | n%10 | 循环后的x | 循环后的n | | 1 | 123456 | 6 | 6 | 12345 | | 2 | 12345 | 5 | 65 | 1234 | | 3 | 1234 | 4 | 654 | 123 | | 4 | 123 | 3 | 6543 | 12 | | 5 | 12 | 2 | 65432 | 1 | | 6 | 1 | 1 | 654321 | 0 |第一个循环结束后n0x654321。第二个循环阶段程序其实就是在对654321做二进制1计数。所以选择题第1问的答案本质是问“654321的二进制表示里有多少个1”。我建议你手动模拟到这里就停不要真的一步步执行第二个循环后面我会给更快的计算方法。3. 核心原理反转数与二进制1计数之间的“组合拳”3.1 这道题真正在算什么把两个循环翻译成一句话程序输出的是 reverse(n) 的 popcount二进制中1的个数。也就是说给定一个十进制整数n先把它转成“倒序数”然后再问这个倒序数的二进制里有多少个1。例如n123456reverse是654321654321的二进制里1的个数是14。明白了这个大框架你会发现后面那些判断题其实都不难了——它们考的都是这个“大框架”在极端输入下的表现而不是代码实现本身。读程序题最忌讳的就是把代码当“黑盒”去模拟而应该把它当“白盒”去理解先看结构再看意图最后才跑数据。3.2 为什么出题人要用“反转二进制”这个组合我在刷题时总结过一类规律初赛“阅读程序”特别喜欢把两个基础操作“拼接”在一起目的就是看你能不能从“逐行模拟”切换到“语义理解”。如果你只会模拟遇到大数输入比如123456、2000000000就会算得很痛苦如果你会抽象看到reverse和popcount基本就能心算出答案。具体到这道题为什么偏偏是“反转”配上“二进制1计数”我推测有三个原因反转是初赛高频考点里最经典的“循环套路”之一能考查对取余和整除的理解深度popcount是后面数论、位运算题目里反复出现的预处理操作提前在第一题打个照面很合理把两个操作叠在一起后判断题就有了设计空间——比如回文数这种情况反转后等于原数程序就变成了“对n本身求popcount”这是个很漂亮的隐藏结论。对选手来说识别出这个“组合”才是拿分的关键。识别不出来就只能硬着头皮做大量重复模拟不仅慢还容易错。3.3 手算二进制1个数的实用技巧16进制映射法第二个循环如果真的一步步模拟到x变成0对654321这种量级可能要跑20轮中途特别容易数错。我推荐一个手算技巧先把十进制转成16进制再把每个16进制位展开成4位二进制最后数1的个数。具体流程拿654321举例。第一步十进制转16进制不断除以16取余654321 ÷ 16 40895 余 140895 ÷ 16 2555 余 15十六进制是F2555 ÷ 16 159 余 11十六进制是B159 ÷ 16 9 余 15F9 ÷ 16 0 余 9从最后一次的商0开始逆序读取余数得到十六进制数 0x9FBF1。验证一下9×65536 15×4096 11×256 15×16 1 589824 61440 2816 240 1 654321完全没问题。第二步16进制每一位展开成4位二进制9 1001F 1111B 1011F 11111 0001拼接起来就是 1001 1111 1011 1111 0001也就是654321的二进制表示。第三步数1的个数10012个、11114个、10113个、11114个、00011个总计2434114。整个过程只需要三次除法和查表比直接模拟二进制除法快得多出错率也低。这个技巧在阅读程序题里非常好用尤其是遇到大整数需要手算popcount的场合。你可以把这个方法理解成“用16进制做中间人”16和2是倍数关系一位16进制数恰好等于4位二进制数所以转换过程不存在任何误差。3.4 int边界问题2000000000合理吗选择题第2问的输入是2000000000。有些选手一看这数字就慌了第一反应是“int放得下吗”int的取值范围是-2147483648到21474836472000000000在这个范围内完全合法。但这里埋着另一个更隐蔽的坑2000000000反转之后是什么很多人以为是“0000000002”也就是2也有人以为会溢出。实际上反转过程是逐位进行的这个数字是2后面跟9个0从最低位开始取前面9次循环取出来的全都是0x始终是0最后一次n变成2x0×1022n0。所以反转结果是2前导0全部被丢弃根本不涉及溢出。然后对x2做二进制1计数2的二进制是101的个数是1。所以这道选择题的答案就是1。这里最常见的错误有两种一是把2000000000硬算成2×10^9然后去反转数字字符串忽略了前导0的丢弃二是在第一个循环阶段就担心x累加成很大的数会溢出然后猜一个离谱的答案。实际上int能装下的数字反转后大概率还在int范围内除非输入本身接近int上限且反转后位数不变这题的设计并没有往溢出方向走。4. 标准答案解析判断题与选择题逐项推理4.1 判断题1输入的n必须为正整数错误这个说法为什么错因为程序并没有强制n必须大于0。如果n0第一个循环while(n0)根本不进入x保持0第二个循环while(x0)也进不去ans保持0最终输出0。程序完全正常结束不会报错也不会死循环。如果n是负数第一个循环同样进不去输出也是0。也就是说输入0或负数时程序都能运行并输出0那“必须为正整数”这个说法当然不成立。我见过有人在这里纠结“负数没意义所以输入必须为正整数”这是把“程序的语义假设”和“代码的实际行为”混为一谈了。初赛判断题抠的是代码行为不是出题人的意图这一点一定要分清楚。4.2 判断题2若输入的n为0程序输出0正确这个其实在上面已经顺便证明了n0时两个循环都不会进入ans0输出的就是0。这题算送分题但它提醒我们阅读程序题的第一件事永远是检查边界输入尤其是0、负数、个位数、最大值这些极端情况。很多阅读题的设计思路就是“主路径大家都会边界条件才能区分人”。4.3 判断题3若输入的n是回文数程序输出的值等于n的二进制表示中1的个数正确回文数就是从左往右读和从右往左读相同的数字比如12321、1234321。由于回文数反转之后还是它自己所以第一个循环结束后x就等于n本身第二个循环就是对n求popcount程序输出的ans自然就是n的二进制表示中1的个数。这题说白了就是考察“你能不能想到reverse(n)在回文数情况下等于n”。想通了答案立刻出来想不到这题会觉得模棱两可。我当时在考场上就先写了一个回文数12321模拟了一下反转还是12321二进制里1的个数是4验证无误后选了正确。这个“用小样例验证判断题”的习惯我强烈建议每个选手都养成尤其是遇到含“一定”“必须”“始终”这类绝对化表述的题。4.4 选择题1输入“123456”输出为 这是最考验手算的一道题。根据前面的分析123456反转后是654321然后对654321求二进制1的个数。用16进制映射法6543210x9FBF1展开成二进制后数1的个数是14。我也把直接模拟的路径写一下方便想验证的读者654321的二进制是10011111101111110001里面一共14个1二进制位数是20位意味着程序要跑20轮循环才把x消到0。你要是一个循环一个循环地模拟既慢又容易在中间某一步数错——这就是我反复强调“先抽象语义、再手算”的原因。考场上没有那么多时间让你做完整模拟。4.5 选择题2输入“2000000000”输出为 前面已经推过2000000000反转后是2前导0丢弃2的二进制是101的个数是1。所以答案是1。这道题真正的价值在于提醒你反转操作在处理“末尾有连续0”的数字时会导致反转结果位数比原数少很多。2000000000是10位数反转后只有1位。如果出题人把输入改成1999999999反转后是9999999991仍然是10位那整个计算量就完全不同了。所以遇到大数输入先想清楚“反转后到底变成几位的数”再决定怎么算能省下大量无用功。4.6 一张表总结全部答案题号类型设问答案判断题1判断输入的n必须为正整数错误判断题2判断若输入的n为0程序输出0正确判断题3判断若输入的n是回文数程序输出的值等于n的二进制表示中1的个数正确选择题1选择输入“123456”输出14选择题2选择输入“2000000000”输出15. 从这道题展开阅读程序题的四步拆解法5.1 第一步先抽象语义再逐行验证拿到任何一段阅读程序题我的习惯是不急着模拟具体值而是先干一件事给每个循环、每段代码“起名字”。比如本题第一个循环你可以叫它“反转”第二个循环叫它“数二进制1”两个循环合起来就是“先反转再数1”。一旦完成了这个抽象后面所有判断题和选择题都变成了“验证这个抽象对不对”。如果第一步做不出来说明你对基础套路还不熟。常见的循环套路就那么几种数位拆分、数字反转、最大公约数、进制转换、质数判断、二分、排序。把这些套路单独练一遍见到代码能自动反应出它的“名字”阅读程序题的正确率会直接上一个档次。我经常跟学生说阅读程序题练的不是“读代码”而是“读算法”。5.2 第二步边界条件优先扫一遍抽象完成之后立刻检查这几类输入下的代码行为n0两个循环都不进输出0n为负数同上n是一个一位数第一个循环只跑一次xn第二个循环对n本身数1n是回文数反转等于自身n在int最大值附近反转结果可能溢出本题没考但你要有这个意识。这道题的判断题3就是在考“回文数”这个边界判断题1和2考的是“0和负数”。边界条件不是附加题它们恰恰是初赛判断题最爱的素材。出题人不会让你舒舒服服地只算一个正常输入一定会塞一个极端输入进来看你能不能反应过来。5.3 第三步手工模拟只走关键路径如果是选择题我不会把整个程序从头跑到尾而是只模拟到“关键点”就切换计算方法。比如本题输入123456模拟完第一个循环得到x654321就够了第二个循环我直接用16进制映射法数1而不是真的一步步除以2。关键路径的定义就是决定答案的那个变量变化路径通常不会超过整个程序工作量的一半。这里我再强调一个具体经验模拟的时候一定要写变量跟踪表也就是把每一轮循环之后n、x、ans的值都列出来。很多错误都源于“脑内模拟”时少算了一轮或者用错了上一轮的值。写下来虽然慢一点但准确率高得多特别是第一遍做题的时候。等熟练了你可以在脑子里快速过但前提是你已经错够了。5.4 第四步用小样例验证“文字描述”判断题的表述经常带有“必须”“始终”“不可能”“一定”这类绝对化词汇一旦看到就条件反射地去找反例。比如“输入的n必须为正整数”我立刻想到n0。找到反例这题就是错的找不到反例再用小样例验证正确性。我特别喜欢在草稿纸上写一个小数字比如13或者25完整跑一遍程序看看输出验证完再选答案。以13为例13反转后是3131的二进制11111有5个1程序输出5。虽然13不算什么特殊数字但至少能说明“抽象语义”和“代码行为”是一致的。如果验证结果和抽象不一致那说明我理解错了得回头重看代码而不是硬撑着往下做。5.5 考场上的时间管理CSP-S初赛全卷120分钟阅读程序部分一般有3道有题建议总用时控制在30分钟以内。像本题这样的第1题正常应该在3-5分钟内完成。如果你超过10分钟还没做完大概率是卡在“逐行模拟”里了这时候应该做的是强迫自己跳出来重新抽象语义而不是硬着头皮继续算下去。一个小技巧先跳过阅读程序里的难题把后面的完善程序或者其他题型做完了再回来啃。阅读程序的判断题和选择题分值都是固定的不存在“必须按顺序做”的说法先易后难永远是最稳的策略。这道第1题本身不难真正难的是后面那些带递归、带二维数组、带状态转移的题目遇到那种题死磕十分钟不如先拿掉能拿的分。6. 竞赛心得这类“拼接型”程序的识别与延伸6.1 出题人是怎么设计这道题的我觉得这道题的出题思路很典型先选两个最基础的操作数位反转、二进制1计数把它们拼成一个程序然后在“输入边界”上做文章。判断题2和3分别是“0输入”和“回文数输入”一个是全局边界一个是局部特殊情形选择题1和2分别给了一个带多1的数据和一个带多0的数据一个重计算一个重洞察。这种出题模式的识别价值在于一旦你习惯了“抽象语义边界检测手算技巧”的流程这类拼接型阅读题基本上就是送分题。真正拉开差距的是那些带递归、带数组、带状态转移的题目但那又是另一套方法论了。不过话又说回来基础拼接题如果做不对后面的难题更没戏因为难题的代码里也嵌套着这些基础操作。6.2 我的一个踩坑经历我第一次做这道题时栽在了一个很蠢的地方把第二个循环里的 x % 2 看成 x % 10我以为是统计“反转数里奇数数字的个数”结果算出来的答案完全对不上选项。后来我才意识到这里考察的是“除以2取余”这个二进制位运算而不是“除以10取余”的十进制数位运算。区分%2和%10、/2和/10是这类代码最容易被忽略的第一道坎。另一个坑是变量覆盖循环结束后n已经变成0但如果你看代码不仔细很容易在第二个循环里误写成n % 2。实际代码操作的是xn只是被第一个循环用掉了。初赛阅读程序特别喜欢拿这种变量生命周期做文章做题时在心里给每个变量标一下“它在哪一段代码里存活”能大概率避免这类低级错误。6.3 变式一如果第二个循环换成统计二进制0的个数把“ans x % 2”换成“ans 1 - x % 2”程序就从统计1的个数变成统计0的个数了。对于654321二进制一共20位里面14个1那么0的个数就是20-146。这个变式考察的是二进制位数可以通过反复除以2得到0的个数等于总位数减去1的个数。顺着这个思路你甚至可以自己出题考别人。6.4 变式二如果反转结果可能溢出int程序会怎样这道题没有涉及反转溢出因为123456反转后是654321、2000000000反转后是2都在int范围内。但假如输入是1999999999反转后是9999999991已经超过int最大值2147483647了会发生什么在C标准里有符号整型溢出是未定义行为实际竞赛环境中通常会发生溢出回绕算出来的x可能变成负数然后第二个循环while(x0)进不去程序输出0。这类“溢出陷阱”在竞赛题里不算罕见。阅读程序题里看到反转、阶乘、累加、平方这些操作一定要多留个心眼int的范围上限是约21亿超过这个数就要考虑是否溢出。实操中判断反转是否安全可以用类似 if (x (INT_MAX - digit) / 10) 的方式预判但在初赛笔试题里你只需要知道“可能溢出”这个结论就够了。6.5 变式三从十进制扩展到任意进制如果题目把 x % 2 改成 x % 8把 x / 2 改成 x / 8程序就从“统计二进制1的个数”变成了“求八进制表示的各位数字之和”。因为 ans x % 8 累加的是八进制的每一位和“数1个数”就完全不是一回事了。同理如果把第二个循环改成 ans x % 10; x / 10那就是在求十进制数位和。这个扩展思路其实很有用你练的不是一道题而是一类“从程序反推算法”的能力。初赛阅读程序题本质上考的就是“读代码→抽象算法→套输入→得输出”这条链路练得越多链路越顺。我个人建议每做完一道阅读程序题都随手写一个变式出来考考自己坚持半年你读代码的速度和准确率会有质的提升。就拿这道题来说从“二进制数1”改成“八进制数位和”再改成“二进制数0”一题能顶三题练。