简介这份PDF聚焦2020年CSP-J1入门级与CSP-S1提高组初赛面向备战信息学奥赛第一轮的选手、竞赛教练及需要复盘真题的教师帮助读者对照答案梳理失分点并理解命题思路。压缩包内仅含1个PDF文件体积约63KB内容围绕两套试题的答案、解析与总结展开并附有相关真题、各省分数线统计与参赛经验等参考线索便于按需延伸查阅。已有4584人学习说明其在初赛备考群体中具有一定参考价值。读者可借此核对2020年两级别初赛答案分析选择题、程序阅读与完善程序等题型的常见陷阱结合解析归纳数据结构、算法与语法知识点并借助分数线信息判断自身水平、安排后续训练。整体适合作为赛前查漏补缺、把握难度和赛后复盘的材料同时可了解当年试题难度与命题风格。1. 从一段二十行的循环说起CSP-J 初赛和 CSP-S 初赛到底在考什么CSP-S 初赛最容易踩坑的地方往往不是最后两道完善程序而是阅读程序里那段只有二十行、看起来没什么威胁的双重循环。2020 年那份答案解析被反复传阅真正有价值的不只是答案本身而是它把“这道题为什么这么想”展开给你看。第一轮满分 100 分单选 30、阅读程序 40、完善程序 30120 分钟全在答题卡上完成不写一行能跑的代码。这场考试考的不是你会不会写程序而是你能不能在纸上把别人的程序读懂、算准、补全。适合已经学完 C 基础语法、准备第一次上考场的人更适合考了两三次还在 60 分上下浮动、想知道自己到底丢在哪一块的人。2. 分值地图与单选考点30 分里有 22 分是能背出来的2.1 三种题型的分值与时间分配先把分值分配搞清楚后面所有策略都从这里推导。CSP-J1 和 CSP-S1 的卷面结构一致只是难度不同同年两卷的知识点范围高度重叠所以一份答案解析往往能同时覆盖两个组别。题型题量分值建议用时目标分单项选择15 题30 分25 分钟22 分阅读程序3 篇40 分45 分钟24 分完善程序2 篇 10 空30 分40 分钟18 分填涂与回查——10 分钟—阅读程序的 40 分里判断题一般每题 2 分、选择题每题 3 分具体配比逐年微调进考场先看卷面说明不要凭记忆套。很多人在单选上花 40 分钟结果阅读程序只剩 30 分钟第三篇直接靠猜这是最典型的失分场景。单选 15 题的考点分布大致稳定计算机基础 3 到 4 题进制、编码、存储单位、网络常识C 语法 3 到 4 题运算符优先级、类型转换、指针与引用、数组与字符串数据结构 3 题栈队列、树、图、哈希算法与复杂度 3 题排序、递归、复杂度量级数学 2 到 3 题排列组合、概率、逻辑推理。前四类靠背和练就能拿数学类看临场。提示单选控制在 25 分钟内做完遇到卡壳超过 90 秒的直接标记跳过先把能拿的分收进袋子。2.2 进制、位运算与原反补码三步定答案这三块是单选里最容易“会但算错”的题。进制转换用固定动作不要心算。十进制整数转二进制除 2 取余倒序排列。小数部分乘 2 取整正序排列。二进制转十六进制从右往左四位一组不够左边补零每组换成一个十六进制字符。二进制转八进制三位一组同理。原码、反码、补码只记一条链正数三码相同负数的反码是符号位不变、其余位取反补码是反码加 1。n 位补码的表示范围是 -2^(n-1) 到 2^(n-1)-18 位就是 -128 到 127这个范围每年都有人写成 -127。位运算记四个常用套路考试基本跑不出这个圈x (x - 1)消掉最低位的 1用来统计二进制中 1 的个数循环几次就有几个 1。x -x取出最低位的 1也叫 lowbit树状数组的基石。x ^ x 0异或用来找唯一出现奇数次的数全部异或一遍剩下的就是答案。左移 k 位等于乘 2^k右移 k 位等于整除 2^k 并向下取整负数右移要小心。“三步”指第一步确定位宽8 位、16 位还是 32 位第二步判断正负看最高位第三步按链走负数先减 1 再取反得原码或先取反再加 1 得补码。位宽搞错后面全错。2.3 数据结构与排序两张表解决大半道题数据结构的单选题几乎都是“性质判断”把下面这张表记住比现场推快得多。结构关键性质常考问法栈后进先出出栈序列是否合法、括号匹配、表达式求值队列先进先出广度优先遍历顺序、滑动窗口链表插入删除 O(1)查找 O(n)头插尾插的结果、删除结点要改几个指针二叉树第 i 层最多 2^(i-1) 个结点遍历序列还原树、叶子与度为 2 结点的关系完全二叉树编号 i 的左孩子 2i右孩子 2i1叶子数、树高、最后一个非叶结点图所有顶点度数之和等于边数的两倍邻接矩阵空间、连通分量个数哈希装填因子等于元素数除以表长冲突处理方式、平均查找长度二叉树有一条必考结论任何非空二叉树中叶子结点数 n0 等于度为 2 的结点数 n2 加 1即 n0 n2 1。推导过程不用背用“边数 结点数 - 1”两分钟能推出来但考场上直接用结论更稳。排序算法重点是稳定性和复杂度这张表建议抄在错题本第一页。算法平均最坏空间稳定性冒泡O(n²)O(n²)O(1)稳定插入O(n²)O(n²)O(1)稳定选择O(n²)O(n²)O(1)不稳定归并O(n log n)O(n log n)O(n)稳定快速O(n log n)O(n²)O(log n)不稳定堆O(n log n)O(n log n)O(1)不稳定计数O(n k)O(n k)O(k)稳定基数O(d(n k))同左O(n k)稳定稳定性记一句话只有“相邻交换”和“分治合并”才稳跳跃式交换选择、快排、堆排都不稳。2.4 组合计数与概率加乘原理的边界这类题错的人最多因为公式都认识就是不知道用哪个。判断标准只有一条做完一件事是“分类”还是“分步”。分类用加法每类互不重叠分步用乘法每步缺一不可。常用公式排列 A(n, m) n! / (n - m)!从 n 个不同元素里取 m 个排队。组合 C(n, m) n! / (m!(n - m)!)只取不排。插板法n 个相同物品分给 m 个人每人至少一个方案数 C(n - 1, m - 1)。错排 D(n) (n - 1)(D(n - 1) D(n - 2))D(1) 0D(2) 1。鸽巢原理n 1 个物品放进 n 个抽屉必有一个抽屉至少两个。古典概型就是“符合条件的情况数除以总情况数”两个数都用组合算别中途换算成百分数最后一步再换。考场上最容易错的是“至少”两个字正面算不清楚就反过来用总数减一个都没有的情况。2.5 真题演练五道单选题的完整推演下面五道题按 2020 年卷面结构改写覆盖上面四类考点每道给出思路而不是只给答案。第一题二进制 1011010 转成十六进制是多少。从右往左四位一组得到 0101 和 1010前一组补零后是 5后一组是 A结果是 5A。这类题的唯一风险是分组方向搞反从右往左不能从左往右。第二题8 位补码 1111 0110 对应的真值是多少。最高位是 1负数。补码减 1 得反码 1111 0101符号位不变、其余取反得原码 1000 1010真值 -10。也可以用“取反加 1”的等价算法两种算法结果必须一致不一致就是位宽搞错了。第三题入栈顺序为 1、2、3、4下列哪个出栈序列不可能出现。判断方法对每个候选序列模拟一遍只要出现“某个数出栈时比它小的数还没出栈且被压在它下面”这个序列就不合法。比如 4、1、2、3 不可能因为 4 先出栈说明 1、2、3 都在栈里出栈顺序必须是 3、2、1。第四题一棵二叉树有 10 个度为 2 的结点叶子结点有多少个。直接套 n0 n2 1答案是 11。这道题不用画图画图反而浪费时间。第五题从 6 个不同元素中取 3 个要求至少包含某一个指定元素有多少种取法。正面算是 C(5, 2) 10反过来算是 C(6, 3) - C(5, 3) 20 - 10 10。两种算法互相验证是考场上最省时间的检查方式。3. 阅读程序题三段式拆解与三类高频模型3.1 三段式定输入、走变量、卡边界阅读程序给的是 15 到 30 行代码后面跟 6 个小题判断题问“输入为某值时输出是否为某值”“把某行改成另一种写法结果是否改变”选择题问“时间复杂度”“输出结果”“循环执行次数”。固定动作分三段。第一段定输入。看cin读几个数、什么类型、有没有范围提示。输入范围决定了三件事会不会溢出int 还是 long long、循环能不能跑完指数级递归遇到 n 40 必然超时、数组够不够大。第二段走变量。找循环不变量也就是每一轮开始时恒成立的那个关系。比如“前 i 个元素已经有序”“f[i] 表示前 i 个数的方案数”。找到不变量代码就不用逐行读。第三段卡边界。n 0、n 1、全相同、全逆序、负数、最大值。判断题有相当一部分就是拿边界值来设陷阱。注意阅读程序的选择题里出现“一定”“必然”这种词先怀疑再看有没有反例。3.2 循环与数组类冒泡排序的交换次数这是阅读程序里出现频率最高的一类结构2020 年两卷都有类似的循环嵌套题。#include iostream using namespace std; int a[1005], n, cnt; int main() { cin n; for (int i 1; i n; i) cin a[i]; for (int i 1; i n - 1; i) { // 外层每轮把一个最大值送到末尾 for (int j 1; j n - i; j) { // 内层已排好的尾部不再比较 if (a[j] a[j 1]) { // 严格大于才交换 swap(a[j], a[j 1]); cnt; // cnt 累计交换次数 } } } cout cnt endl; return 0; }逻辑说明外层循环控制轮数共 n - 1 轮内层上界是 n - i因为第 i 轮结束时末尾 i 个元素已经有序再比较就是浪费。cnt记录的是交换次数而在冒泡排序中交换次数恰好等于原序列的逆序对数量这个结论是选择题的高频答案。参数说明数组开 1005 是按题目给定的 n 不超过 1000 留的余量考场上看到 n 的范围一定要回头核对数组大小越界在纸面上不报错但答案会错。判断题常见的两种改法要特别小心。第一种把a[j] a[j 1]改成a[j] a[j 1]排序结果不变但相等元素也会交换cnt变大所以“输出不变”是错的。第二种在两层循环之间加一个bool flag每轮检查有没有发生交换、没有就break这时最好情况复杂度从 O(n²) 降为 O(n)但逆序对数量的结论依然成立。时间复杂度外层 n 轮、内层平均 n/2 次总共 O(n²)与输入是否有序无关没加提前退出。空间复杂度 O(n)因为开了数组。这两问几乎每篇阅读程序都会有一道。3.3 递归类调用次数与指数爆炸#include iostream using namespace std; int f(int n) { if (n 1) return n; // 递归出口f(0)0f(1)1 return f(n - 1) f(n - 2); // 每层拆成两个子问题 } int main() { int n; cin n; cout f(n) endl; return 0; }逻辑说明这是最朴素的斐波那契递归写法f(n)的值是第 n 项但真正要考的不是值而是调用规模。f(n)展开后形成一棵二叉树结点总数约为 2^n所以时间复杂度是 O(2^n)空间复杂度是递归栈深度 O(n)。参数说明n用 int 就够因为 n 超过 45 时结果会超出 int 范围但程序本身在 n 40 左右就已经跑不完了所以题目通常不会问大数的值而是问“n 40 时能否在 1 秒内结束”——答案是不能指数级增长在 n 40 时已经是万亿次量级。判断题常见的坑把if (n 1)改成if (n 1)此时 n 1 会继续递归到 f(0) f(-1)f(-1) 又继续往下栈溢出程序行为完全改变。这种“改一个不等号”的题一定要代入边界值实际走一遍。另一类递归题是“递归求二进制中 1 的个数”或“递归求最大公约数”结构简单但问法刁钻比如“把递归改成循环时间复杂度会不会变”。答案是不会递归和循环只是写法差别量级取决于循环次数不取决于写法。3.4 位运算与字符串类逐位拆解#include iostream using namespace std; int main() { int n, ans 0; cin n; while (n) { n n (n - 1); // 每次消掉最低位的 1 ans; // 消几次就有几个 1 } cout ans endl; return 0; }逻辑说明n (n - 1)的作用是把 n 的二进制表示中最低位的 1 变成 0其余位不变。循环每执行一次消掉一个 1所以ans最终等于 n 的二进制中 1 的个数。循环次数等于 1 的个数最坏情况n 全是 1是 O(log n)因为 n 的二进制位数是 log n 级别。参数说明如果 n 是负数在补码表示下最高位是 1这个算法会把符号位也算进去答案变成 32 或 64。所以题目一定会给 n 是正整数的范围看到“正整数”三个字要留意这往往是判断题的考点。字符串类阅读程序的处理方式不同重点看三处字符数组有没有留\0的位置、strlen是在循环条件里调用还是提前算好、下标从 0 开始还是从 1 开始。strlen放在for条件里会导致 O(n²) 复杂度这是选择题的常客。3.5 判断题的答题口径错在哪才算错判断题的表述往往是“当输入为 X 时输出为 Y”判错的标准是“程序实际行为与描述不符”而不是“描述里的数字算错了”。所以做判断题的正确顺序是先按描述跑一遍程序看输出对不对如果输出对再看描述里有没有额外的限定词“一定”“仅”“最多”。最常见的三种错法把“第 3 行输出”看成“输出 3”把“最多执行 n 次”看成“恰好执行 n 次”把“结果不变”看成“过程不变”。改一个比较符号通常结果不变但过程变了改一个初值通常过程不变但结果变了这两种要分清。还有一类是“复杂度判断”判断题比如“这段程序的时间复杂度是 O(n log n)”。判断依据是循环层数与每层规模双重循环且内层规模随外层缩小如 n、n-1、n-2……是 O(n²)内层规模固定减半是 O(n log n)只有一层且规模减半是 O(log n)。这三个量级每年都有人搞混。4. 完善程序题五空填空的答题顺序与两类高频模型4.1 空位分三类边界空、递推空、初始化空完善程序题面一定有一段中文说明讲清楚这段代码要解决什么问题、用什么算法。很多人上来就看代码结果读了十分钟还不知道在干什么。正确顺序是先读中文说明再扫一遍代码骨架最后把 5 个空分类。边界空循环条件、数组下标、递归出口。判断依据是“这个循环要跑几次”“这个数组要用到第几位”。看到i n和i n要停顿一下看题目里是 0 下标还是 1 下标。递推空状态转移方程、累加式、比较式。判断依据是“这一步要用到前面哪几个状态”。01 背包是f[j] max(f[j], f[j - w[i]] v[i])最长上升子序列是f[i] max(f[i], f[j] 1)这些式子的结构是固定的。初始化空dp 数组初值、ans 初值、计数器清零。这类空最容易填也最容易错。求最小值时 ans 要初始化为一个大数求最大值时初始化为 0 或 -1求方案数时f[0] 1。答题顺序建议从最有把握的空开始不要按 1 到 5 的顺序填。填完一个空就在草稿纸上标一下避免后面改前面的。4.2 二分与双指针模型// 在升序数组 a[1..n] 中找第一个大于等于 x 的位置 int l 1, r n, ans n 1; // ans 初值设为不存在的位置 while (l r) { int mid l (r - l) / 2; // 防溢出写法 if (a[mid] x) { ans mid; // 记录当前可行解 r mid - 1; // 继续往左找更小的 } else { l mid 1; // 当前太小往右找 } }逻辑说明这是“找下界”的标准二分。ans记录当前找到的可行位置每找到一个更靠左的就更新。循环结束时ans就是第一个大于等于 x 的位置如果始终没找到ans保持 n 1。参数说明mid写成l (r - l) / 2而不是(l r) / 2是为了防止 l 和 r 都接近 int 上限时相加溢出。考场上如果题目数据范围不大两种写法结果一样但填空处给的形式往往是防溢出写法因为出题人想考这个点。完善程序里二分题的填空通常落在三个位置ans的初值、r mid - 1还是r mid、l mid 1还是l mid。判断方法看循环条件while (l r)配mid ± 1while (l r)配mid或mid 1。两种模板不能混用混用就是死循环。4.3 搜索与动态规划模型// 01 背包n 件物品容量 m求最大价值 for (int i 1; i n; i) { for (int j m; j w[i]; j--) { // 必须倒序 f[j] max(f[j], f[j - w[i]] v[i]); } }逻辑说明外层枚举物品内层枚举容量。倒序枚举容量保证每件物品只被选一次因为计算f[j]时用到的f[j - w[i]]还是上一轮没选当前物品的值。参数说明如果内层改成正序for (int j w[i]; j m; j)f[j - w[i]]可能已经在本轮被更新过等于同一件物品被选了多次那就变成了完全背包。这个“正序还是倒序”的填空几乎是每套完善程序的常客也是最容易失分的地方。搜索类完善程序通常是 DFS 或 BFS 的框架填空落在三处递归出口边界判断、状态标记vis[x] 1和回溯vis[x] 0。判断依据是“这个点能不能重复走”。如果题目说“每个点只能走一次”就必须有回溯或标记如果是有向无环图标记可以省。4.4 填完之后的自检清单五个空填完不要立刻涂卡按下面四步过一遍。第一步用最小规模手算。n 1、n 2、只有一个元素、空数组把这几种情况代进去看代码会不会越界、会不会死循环、输出是否符合预期。第二步查数组下标。题目给的数组是a[1..n]还是a[0..n-1]循环从 1 开始还是从 0 开始这两件事必须前后一致中间改一个就是全错。第三步查变量初始化。ans、cnt、f[0]有没有赋值全局变量默认是 0局部变量不初始化是随机值考场上不报错但答案错。第四步查数据类型。累加、累乘、方案数统计这三类很容易超过 int 范围题目数据范围里出现 10^9 就要考虑 long long。5. 易错点五类每年都有人栽的题5.1 错在循环边界把 n - 1 当成 n错在哪阅读程序里数循环执行次数看到for (int i 1; i n - 1; i)就填 n正确应该是 n - 1。为什么错C 的循环条件是“小于等于”还是“小于”很多人在纸上读代码时自动脑补成自己习惯的写法尤其是代码里同时出现i n和i n时眼睛会跳过符号。怎么答对每读到一个循环先在草稿纸上写一遍“i 从几到几共几次”把上界单独抄下来再开始推逻辑不要心算。5.2 错在稳定性把快排记成稳定错在哪选择题问“下列排序算法中稳定的是”把快速排序选进去。为什么错快排的交换是跳跃式的相同元素可能在交换中被跨过去前后顺序变了。很多人只记“快排很快”没记“快排不稳定”。怎么答对用一句话做判断标准交换只发生在相邻位置的是稳定排序冒泡、插入、归并交换跨越中间元素的是不稳定排序选择、快排、堆排。考场上用这一句话现推比背表格可靠。5.3 错在 01 背包正序把完全背包当 01 背包错在哪完善程序里内层循环写成for (int j w[i]; j m; j)用正序枚举容量。为什么错正序时f[j - w[i]]可能在本轮已经被更新过相当于同一件物品被重复选取01 背包成了完全背包答案变大。这个错误在纸上不明显只有手算小数据才会暴露。怎么答对记住一条口诀“01 倒序完全正序”倒序保证每一轮用的是上一层的状态。填完空之后拿 n 1、m w[1] 试一遍如果答案等于v[1]就说明只选了一次如果大于就说明重复选了。5.4 错在复杂度量级把 O(n log n) 写成 O(log n)错在哪看到二分就写 O(log n)看到排序就写 O(log n)看到两层循环就写 O(n)。为什么错复杂度看的是“基本操作执行了多少次”不是“代码有几层”。二分查找是每次范围减半执行 log n 次所以是 O(log n)归并排序每层合并 n 次、共 log n 层所以是 O(n log n)两层循环且内层每轮减半是 O(n log n) 而不是 O(n²)。怎么答对先数层数再看每层的规模。每层规模都是 n 就是 O(n²)每层规模减半就是 O(n log n)只有一层且规模减半就是 O(log n)。三个量级对应三种结构不要混。5.5 错在判断题的“一定”把可能当成必然错在哪判断题说“当输入为某值时程序一定会输出某值”实际上程序在该输入下行为未定义或依赖随机值。为什么错全局数组默认初始化为 0局部数组不会int溢出是未定义行为swap相同元素时结果不变但过程变了。题目里只要出现“一定”“必然”“任何情况下”都要找一个反例。怎么答对判断题遇到绝对化表述先找边界值n 0、n 1、全相同、最大值能举出一个反例就判错举不出来再判对。这个顺序反过来就会把“可能”当成“一定”。6. 考场上的答题顺序与押题思路我的习惯是拿到卷子先花 90 秒把三种题型的分值和题量扫一遍确认阅读程序的判断题、选择题各几分然后按“单选 → 完善程序 → 阅读程序”的顺序做。单选放在最前面因为它最快、最容易进状态25 分钟内必须结束。完善程序放在第二位因为题面有中文说明读完说明就能抓住算法框架五个空里通常有两到三个是“送分空”初始化、边界条件先把这些填掉心里就有底了。阅读程序放最后因为它最耗时一篇阅读程序的手算量可能顶三道单选而且判断题的容错率低状态不好时容易连续错。押题思路按 2020 年两卷的分布看阅读程序集中在三类结构循环嵌套模拟冒泡、选择、前缀和、递归斐波那契型、分治型、DFS 型、位运算或字符串处理lowbit、popcount、字符数组遍历。完善程序集中在两类模型二分或双指针找下界、找第一个满足条件的位置、动态规划或搜索01 背包、最长上升子序列、DFS 标记回溯。这五类结构覆盖了卷面上八成的代码题进考场前把这五类各手写一遍比刷十套卷子管用。还有一个容易被忽略的点时间分配要留出 10 分钟填涂和回查。我见过太多人最后五分钟才开始涂卡结果涂串行。从那以后我每次做完一个题型就涂一次卡单选涂完涂阅读阅读涂完涂完善最后 10 分钟只做检查不碰新题。希望帮到你。本文还有配套的精品资源点击获取
