2019年的CSP-S初赛是我第一次以“CSP”而不是“NOIP”的名义走进考场。说实话当时心里多少有点没底——毕竟是新名字的第一年谁也不知道命题风格会不会大改。等我翻到选择题第一页看到前5题的时候反而松了口气进制转换、位运算、栈、完全二叉树、KMP的next数组都是平时练过无数遍的考点。不过让我意外的是身边不少同学恰恰在这5道“送分题”上翻了车尤其是第5题KMP的next数组几乎成了当年考后讨论热度最高的话题。所以这篇复盘文章我想把2019年CSP-S初赛选择题第1到第5题完整还原出来逐题讲清楚答案是怎么来的、陷阱埋在哪再聊聊从这5道题暴露出的备考盲区。如果你正在准备CSP-S初赛或者只是好奇信奥赛第一轮到底考什么这篇应该能帮你少走一点弯路。先从这5道题在整张试卷里的定位说起。1. 2019年CSP-S初赛的第一枪前5题在整张卷子里有多重要1.1 CSP元年的初赛结构2019年是CSP第一次开考很多人还习惯性地把它叫“信奥赛”。第一轮认证是笔试满分100分题型包含单项选择题、阅读程序写结果、完善程序等。其中选择题一共15道每题2分合计30分。可别小看这30分初赛过线往往就是差两三分的事每年都有大量考生因为一两道选择题失误直接无缘复赛。选择题排序本身也暗含命题组的“心理设计”。第1题到第5题位于试卷最前面难度整体偏低考的全是基础概念和基本功。它们的作用有两个一是让复习到位的考生快速进入状态建立信心二是让基本功不牢的考生一开始就露馅。前5题一旦卡住或做错后面做大题时心里会一直悬着。1.2 前5题的命题逻辑从考点分布看2019年CSP-S前5题几乎就是一套“计算机基础能力”的缩影进制转换、位运算、栈、二叉树、字符串匹配。这个顺序和往年NOIP初赛的命题习惯一脉相承。前5题用的都是最经典的数据结构、最基础的编码知识但命题人会通过改数字、换问法、调选项来增加区分度。用当时我和同学的感受来说这5道题看起来都认识做起来却不一定全对。这就是典型的“基础题拉开差距”不是题目偏而是很多人对基础知识的掌握停留在“好像会”的层面经不起具体计算和细节追问。1.3 怎么用这篇文章才对我不建议你直接往下看答案。先拿出一张纸把后面第2章里的5道题抄成一份简易卷子给自己掐个表10分钟内做完。之后再对答案、看解析。题目数量不多但这个过程能让你真实体会到考场上“会不会”和“熟不熟”的差别。2. 真题还原选择题1-5逐题精讲与易错陷阱提示初赛题目历来靠考生回忆还原下面这5道题按当年多数考生记忆版本整理个别文字表述可能与原卷有出入但考点、选项思路和答案逻辑是一致的不影响做题和复盘。先把整体情况放在一张表里方便后续对照题号核心考点答案易错指数1十进制转二进制、数1个数B★2异或运算与变量交换B★★3栈的后进先出规则A★★★4完全二叉树节点数与叶子数B★★5KMP算法next数组A★★★★★2.1 第1题2019的二进制到底有几个1题目回忆版十进制数2019转换为二进制数后其二进制表示中1的个数是 A. 7 B. 8 C. 9 D. 10答案B逐层解析这道题放在第1题的位置摆明了是送分但送分也讲究方法。最稳妥的方法是短除法2019 ÷ 2 1009 余 11009 ÷ 2 504 余 1504 ÷ 2 252 余 0252 ÷ 2 126 余 0126 ÷ 2 63 余 063 ÷ 2 31 余 131 ÷ 2 15 余 115 ÷ 2 7 余 17 ÷ 2 3 余 13 ÷ 2 1 余 11 ÷ 2 0 余 1把所有余数从下往上写11111100011这就是2019的二进制表示。数一数总共8个1选B。我更推荐第二种方法拆2的幂。2019 1024 512 256 128 64 32 2 1也就是2的10次方、9次方、8次方、7次方、6次方、5次方、1次方、0次方之和一共8项每一项对应二进制中的一个1。这个方法比短除法快得多也不容易数漏。这道题真正的坑在于“数1个数”时漏数最高位的1。很多人短除到最后一层商变成1就不再继续除最后把最高位的1忘了。2019二进制是11位不是10位。所以这类题做完之后建议反向验证2的10次方等于1024比2019小2的11次方等于2048比2019大因此二进制位数一定是11位。2.2 第2题异或交换3行代码把a和b调换题目回忆版若有变量 int a 3, b 5依次执行以下语句a ^ b; b ^ a; a ^ b;则变量a、b的值分别是 A. a 3, b 5 B. a 5, b 3 C. a 0, b 0 D. a 6, b 6答案B逐层解析异或运算^的规则是“按位比较相同为0不同为1”。3的二进制是0115的二进制是101。第一步a ^ ba 3 ^ 5。011 ^ 101 ----- 110此时a变成6110。第二步b ^ ab 5 ^ 6。101 ^ 110 ----- 011此时b变成3011。第三步a ^ ba 6 ^ 3。110 ^ 011 ----- 101此时a变成5101。最终a 5b 3选B。整个过程本质上是在利用异或的两个重要性质a ^ a 0以及 a ^ 0 a。第一次异或把a和b的信息合并存在a里后面两次异或分别把原信息拆出来还给b和a。这个技巧在竞赛题里经常出现但实际业务代码中很少这么写因为可读性差。初赛考它更想考察你对位运算性质的理解而不是让你在复赛里用这招做变量交换。另外注意C里^不适用于浮点数这个技巧只在整数类型下成立。2.3 第3题栈的出栈顺序3凭什么第一个出来题目回忆版元素1、2、3、4、5依次入栈入栈过程中可以随时出栈。若第一个出栈的元素是3则第二个出栈的元素不可能是 A. 1 B. 2 C. 4 D. 5答案A逐层解析栈是“后进先出”的结构所有判断出栈序列的题目都要盯住一件事当前栈顶是谁。要让3第一个出栈入栈和出栈的过程必须是这样1入栈2入栈3入栈然后3出栈。此时栈里的情况从栈底到栈顶依次是1、2。也就是说1被压在最底下2在它上面。第二个出栈的元素只可能有三种情况直接让2出栈第二个出栈元素就是2。继续入栈4然后让4出栈第二个出栈元素就是4。继续入栈4、入栈5然后让5出栈第二个出栈元素就是5。但1上面始终压着2。在2没有出栈之前1不可能出栈。因此第二个出栈元素不可能是1选A。这类题考的是“过程模拟能力”很多同学做错不是因为不懂栈的概念而是没在草稿纸上把入栈出栈过程一步步写出来。遇到栈的模拟题不管题目问的是什么先画出栈底到栈顶的状态一切都会清楚很多。2.4 第4题2019个节点的完全二叉树叶子数考的是公式题目回忆版一棵完全二叉树共有2019个节点则它的叶子节点数是 A. 1009 B. 1010 C. 1011 D. 1008答案B逐层解析完全二叉树的特点是除了最后一层以外其他各层都填满且最后一层的节点都集中在左侧连续位置。对于这种树节点总数n和叶子节点数n0之间存在一个非常实用的关系式n0 ceil(n / 2)也就是叶子节点数等于总节点数除以2后向上取整。n 2019时n0 ceil(2019 / 2) 1010选B。如果不想直接背公式可以用二叉树的度数关系推导。对任意二叉树度为2的节点数n2与叶子节点数n0满足n0 n2 1。完全二叉树里度为1的节点数n1最多只有1个。总节点数公式为n n0 n1 n2 2 × n0 n1 - 12019是奇数。把n1 0代入得到n0 (2019 1) / 2 1010把n1 1代入得到n0 2019 / 2 1009.5不是整数。所以这个完全二叉树中n1只能为0叶子节点数确定为1010。这道题坑在于很多人把“完全二叉树”和“满二叉树”搞混。满二叉树每一层都完全填满2019个节点不可能构成满二叉树。公式一旦用错答案就会跑到1008或1011这类选项里。复习时要特别注意概念边界。2.5 第5题KMP的next数组“abaabc”的手算全流程题目回忆版设模式串P “abaabc”下标从1开始。规定next[1] 0则P的next数组为 A. 0 1 1 2 2 3 B. 0 1 2 2 3 3 C. 1 1 1 2 2 3 D. 0 1 1 2 3 3答案A逐层解析KMP算法里next数组的定义在不同的教材里有不同版本。这道题在题干中明确了下标从1开始并且规定next[1] 0所以你必须按这个约定来计算不能用你自己习惯的另一套定义。我们一位一位推。P a b a a b c位置分别是1、2、3、4、5、6。next[1] 0这是题干规定没有悬念。next[2]看P[1..1] “a”。最长相等真前后缀长度为0因为单个字符没有真前缀和真后缀。所以next[2] 1。next[3]看P[1..2] “ab”。前缀有a后缀有b不相等最长相等真前后缀长度为0所以next[3] 1。next[4]看P[1..3] “aba”。前缀集合是a、ab后缀集合是a、ba最长相等的是a长度为1。next[4] 2。next[5]看P[1..4] “abaa”。前缀有a、ab、aba后缀有a、aa、baa最长相等的还是开头的a。注意ab和aa并不相等所以长度仍是1。next[5] 2。next[6]看P[1..5] “abaab”。前缀有a、ab、aba、abaa后缀有b、ab、aab、baab最长相等的是ab长度为2。因此next[6] 3。整个next数组是0 1 1 2 2 3选A。这道题是当年选择题里正确率较低的一道。失分原因主要是两个一是next数组的教材定义不统一有的版本下标从0开始有的版本next[1] 1二是手算时没有把“最长相等真前后缀”看清楚比如第5位就很容易把next[5]错算成3。实际上“abaa”里前缀ab和后缀aa并不相等认真写一遍就好。3. 考点拆解5道题背后真正要练的4类能力前5题看起来是5个孤立的知识点但本质上拼的是4类底层能力。如果把这几类能力练到位不仅初赛选择题稳对复赛的代码阅读和算法设计也有帮助。3.1 进制与位运算少背公式多理解硬件视角进制转换不是“算术题”而是计算机底层的直接映射。计算机里没有十进制只有高低电平对应的0和1。1的个数、位长度、与或非异或左移右移全都围绕二进制展开。做位运算题目时有个很实用的习惯把每个数都先写成二进制再按位对齐计算。比如第2题的3和5写成011和101之后异或的结果一眼就能看出来。不需要靠记忆“3^5等于6”而是靠按位算。异或运算可以理解成“翻牌”两个1相遇就抵消一个1一个0相遇就留下1。三个性质要刻在脑子里交换律、结合律、自反性。自反性x ^ x 0是KMP之外的很多算法比如状态压缩、xor哈希的基础学一次受用很久。3.2 栈的思维出栈序列题的本质是“盯住栈顶”第3题看着像数据结构题做对的方法却很简单用笔模拟。栈的所有操作都只发生在栈顶所以任何元素想出栈它必须是当前栈顶。这个条件不满足即使它在栈里也出不去。考试时遇到这类题先在草稿纸上写“栈底——栈顶”一行然后按入栈出栈动作逐步更新。把栈画出来比在脑子里空想快得多也更不容易出错。栈还有几个常考方向括号匹配、表达式求值、递归过程、DFS。初赛里栈相关的选择题本质上都不会脱离“后进先出”这四个字。与其背一堆题型套路不如多练几次“手工模拟栈”的过程。3.3 完全二叉树公式要靠推导不能只靠背第4题给我们的提醒很直接树的概念题公式要会推而不是死记。叶子数等于ceil(n/2)这个结论看起来很简洁但它只能用在完全二叉树里。如果题目换成普通二叉树、满二叉树、二叉搜索树结论完全不同。推公式最稳妥的路径就是我一再强调的利用度数关系。n0 n2 1是任意二叉树的普适结论再结合完全二叉树中度为1的节点数最多为1这个特性任何n值都能当场推出来。类似的公式还有深度为k的满二叉树共有2^k - 1个节点n个节点的完全二叉树高度为floor(log2 n) 1。这些都不用死背考前自己动手各推一遍印象绝对比看十遍笔记深。3.4 KMP的next数组本质是“自己匹配自己”第5题是前5题里最有区分度的一道。很多人一到KMP就头痛其实next数组的求法和暴力字符串匹配脱不了关系。求next的过程就是让模式串自己和自己匹配在位置j失配时前面已经匹配的部分P[1..j-1]它的最长相等真前后缀长度决定了j该回到哪里。理解这个逻辑之后不管题目用哪一套next定义你都能通过“先求最长相等真前后缀再按题目规则转换”来求解。初赛只要求手算就不会考太长的模式串这类题的分析过程就是写表格把每一位的前缀、后缀、共同部分列出来答案自然出现。如果涉及代码层面的KMP可以参考如下求next数组的写法下标从0开始next[i]表示P[0..i]的最长相等前后缀长度void getNext(const string p, vectorint next) { int m p.size(); next.resize(m); for (int i 1, j 0; i m; i) { while (j 0 p[i] ! p[j]) j next[j - 1]; if (p[i] p[j]) j; next[i] j; } }注意代码里的定义和前面考试题里next[1] 0的约定不一样。做题和写代码时第一件事永远是看清next数组的定义不要默认所有题目都用同一套规则。4. 备考与临场把前5题的分数稳稳装进口袋4.1 给每道题打“考点标签”平时刷题不要只满足于“这题我选对了”。我习惯在做完一道题后顺手在旁边写一个考点标签。比如“进制-拆幂法”“栈-出栈序列模拟”“树-完全二叉树叶子数”“字符串-KMP定义辨析”。标签越具体越好。积累一段时间后把标签按出现频率排序就能一眼看出自己的薄弱点。我当年发现“位运算优先级”这个标签反复出现才意识到自己对运算顺序的掌握并不过关于是集中补了一次效果很明显。4.2 错题整理别做成“抄题本”错题本的真正作用是记录“我是怎么错的”。每道错题至少要写四行题目来源、考点、我的错误答案、错误原因。错误原因要写得诚实一点比如“把完全二叉树看成满二叉树”“next数组按成自己熟悉的定义算”而不是笼统的“不会”。每周固定翻一次错题本不需要重做所有题只重做那些还模糊的。错题本越翻越薄考试前的信心就越足。4.3 临场时间分配前10分钟决定整场心态CSP-S初赛一共120分钟前面除了15道选择还有阅读程序写结果、完善程序等大题。选择题建议控制在25到30分钟以内前5题则应该在2到3分钟内解决。如果某道题思考超过5分钟还没有头绪先圈出来跳过去做完后面的再回头。尤其不要在前面的选择题上恋战选择题没有倒扣分不会做的题可以先蒙一个写上把时间留给后面分值更集中、更容易通过上下文推理的大题。4.4 草稿纸的使用习惯绝不用心算代替演算初赛允许使用草稿纸很多人却不习惯用。我见过不少人在选择题上心算出栈序列、心算next数组结果是前5题错两三个。考场上正确做法是每道选择题都在草稿纸上留下清晰的演算过程。栈模拟画栈二叉树画节点KMP写表格进制转换写竖式。写得越清楚检查起来越方便正确率就越高。平时练习时也要这样做让“动笔”成为条件反射。5. 复盘与延伸从这几道小题看清的初赛复习盲区5.1 基础题也会以貌取人第1题表面上是“把2019转二进制”做错的人却不少。说明很多人的问题不是“不会十进制转二进制”而是“不熟练”。熟练和不熟练的区别在考场上会表现为两三分钟和十几秒的差别也会表现为“数着数着漏了一位”和“一次算对”的差别。所以别因为题目简单就轻视。越是基础的知识越要用“快且稳”的标准去练习。5.2 一个考点背后是一张网KMP的next数组看起来只是一个字符串匹配算法里的步骤但它背后是“前缀函数”这一整套思想。再往远一点字符串的hash、AC自动机、后缀数组都和“前缀与后缀之间的关系”有关。初赛只考next数组的手算复赛却可能考到它在AC自动机里的应用。第3题的栈同理。栈不仅出现在出栈序列题里它还是递归、DFS、表达式求值、括号匹配的共同基础。第4题的完全二叉树也是堆、线段树、优先队列的底层结构。基础知识的价值不在于单独做题而在于它们会被反复组合成复杂问题。5.3 把零散考点串成知识网络复习时建议做一件事拿一张白纸写下“进制、位运算、栈、二叉树、字符串匹配”这几个词然后把每个词能联想到的所有概念、公式、典型例题都写在旁边。写完之后再找它们之间的连线。比如二叉树和栈之间通过“树的遍历”连接字符串和位运算通过“二进制状态压缩”连接。当你脑子里形成这样一张网之后选择题就不再是孤立的考点测试了。最后分享一个小经验。我当年备考初赛时专门准备了一个小本子每页抄一道选择题答案写在背面首页写着“10分钟内做不完的题都算不会”。后来上了考场第5题KMP的next数组几乎没花时间就做完了因为那个本子最后几页全是next数组的题。初赛的难度从来不在“题有多难”而在“你熟不熟”。希望这篇前5题的复盘能帮你把这些基础分稳稳拿住。