简介《2020 CSP-J1 CSP-S1答案解析及总结.pdf》面向准备参加CSP-J/S第一轮认证的中学生、大学生及信息学教练聚焦2020年入门级与提高组初赛的答案核对、试题解析和备考复盘。文件为1个PDF约63KB篇幅轻量便于在电脑或移动端快速查阅适合考前熟悉题型、考后估分与梳理知识点。内容围绕真题答案、解析线索及相关分数线资料展开可帮助读者定位易错点、理解命题思路并对照入门级与提高组差异安排后续训练。已有4584人学习适合作为初赛入门到进阶阶段的辅助资料用于查漏补缺和建立复习框架。1. 从 30 分选择题开始丢分2020 CSP-J1/S1 初赛到底考什么2020 年 CSP-J1、CSP-S1 的初赛卷面最能拉开差距的往往不是最后两道完善程序而是开头 15 道选择题里那些看着眼熟、答起来含糊的边角知识。整卷 100 分、120 分钟单项选择 30 分、阅读程序 40 分、完善程序 30 分真正决定你能不能进第二轮的是选择题能不能稳在 24 分以上、阅读程序里的判断题能不能少丢 4 分。算法水平差不多的人最后差的就是这几道“本该拿”的题。这份 2020 年 CSP-J1 与 CSP-S1 的答案解析材料价值不在于给你一个正确答案的字母而在于把两套卷子逐题拆开每道题考的是哪个模块、干扰项是按什么思路设的、同一类题下次换个数字还能不能答对。它适合三类人第一次上考场的初中、高中选手去年卡在晋级线附近想补齐盲区的复读型选手以及带学生却没有系统梳理过初赛考点分布的教练型读者。拿分的顺序也要讲清楚先把选择题的固定考点做成条件反射再用阅读程序练“读代码手算”的耐性最后把完善程序当模板识别题来做。顺序反了就会出现“算法会写、卷子做不完”的经典情况。2. 选择题七大考点把送分题按模块吃干净的答题模板15 道选择题摊到 30 分平均每题 2 分看起来不起眼但它是全卷唯一“可以靠背和套路拿满”的部分。2020 年两张卷子的选择题考来考去绕不开下面几块进制与机器数、编码与存储、数据结构性质、排序与复杂度、树与图的基本公式、组合计数与概率、计算机常识与网络基础。前六块占了绝大多数而且每一块都有固定答法。2.1 进制与机器数补码、溢出与取值范围这类题的典型面貌是“求某个负数的 8 位补码”“判断某类型变量的取值范围”“给出两个数做位运算求结果”。答法固定成三步先定字长再定符号位最后按“原码取反加一”走。求 -37 的 8 位补码37 的二进制是 0010 0101取反得 1101 1010加一得 1101 1011也就是十六进制的 0xDB。答题时把这三步写在草稿上比在脑子里默算稳得多。取值范围要背成条件反射8 位有符号补码是 -128 到 12716 位是 -32768 到 32767n 位有符号补码是 -2^(n-1) 到 2^(n-1)-1无符号是 0 到 2^n-1。为什么负数比正数多一个因为 0 占掉了正数那一侧的编码1000…0 这个“负零”被规定成最小负数这就是补码比原码多表示一个数的原因也是选择题最爱设的干扰点。位运算题不要硬算十进制。看到x (x - 1)就想“消掉最低位的 1”看到x -x就想“取出最低位的 1”看到x ^ x 0就想“成对消除”。这三条在 2020 年的选择题和阅读程序里都反复出现记住语义比记住结果有用。提示凡是题目给了“8 位”“16 位”“unsigned”这类字眼先在草稿纸角上写下范围再动手算能挡掉一半的粗心错。2.2 数据结构性质栈、二叉树、图的三个必背公式栈的题只有两种问法给入栈序列问“哪个出栈序列不可能”或者问“n 个元素有多少种合法出栈序列”。前者用模拟法逐个选项拿栈走一遍遇到“栈顶不是当前该出的元素却硬要出”的选项直接排除后者是卡特兰数 C(2n, n)/(n1)n3 得 5n4 得 14n5 得 42把这四个数记住考场上不用推。二叉树的公式必须张口就来叶子结点数 n0 度为 2 的结点数 n2 1结点总数 n n0 n1 n2高度为 h 的二叉树最多 2^h - 1 个结点n 个结点的完全二叉树高度是 ⌈log2(n1)⌉。这条 n0 n2 1 的推导逻辑是“每个度为 2 的结点贡献两个分支除根以外每个结点都被一个分支指向”理解了就不用死记忘了也能现场推。图的公式同样是三句话n 个顶点的无向连通图最少 n-1 条边n 个顶点的无向完全图有 n(n-1)/2 条边有向完全图是 n(n-1) 条弧所有顶点度数之和等于边数的两倍。这三条几乎每年都以不同包装出现比如“至少删掉几条边才能让图不连通”“握手问题”。遍历序列还原二叉树是这类题的难点。答法只有一句前序的第一个或后序的最后一个是根拿它去中序里切左右子树然后递归。给前序 ABDECF、中序 DBEAFC根是 A左子树中序 DBE、右子树中序 FC再依次切下去画完就出来了。不要试图“凭感觉拼”一定按这个切分流程走。2.3 排序与复杂度稳定性和比较次数要分清排序题在初赛里只考两件事稳定性和复杂度。把下面这张表记牢比记十段代码都有用。排序算法平均时间最坏时间额外空间稳定性冒泡排序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(d(nr))O(d(nr))O(nr)稳定“稳定”的意思是相等元素排序后相对位置不变。选择题最爱拿“快速排序最坏是 O(n log n)”来设陷阱正确说法是最坏 O(n²)出现在每次划分都极不均匀的时候比如已经有序还取首元素做基准。这条在阅读程序里也可能变成“这份代码在什么输入下最慢”的判断题。比较次数类问题有个常用结论在 n 个元素里找最大值至少需要 n-1 次比较找最大和次大值至少需要 n ⌈log2 n⌉ - 2 次比较基于比较的排序下界是 ⌈log2(n!)⌉。这几个数不需要推导但要在选择题里认出来。2.4 组合计数与概率从鸽巢到卡特兰排列组合题的标准打法是“先分类、再相乘、后去重”。从 5 个人里选 3 个人排队是 A(5,3)60选 3 个人不分顺序是 C(5,3)10这两个数的区别就是“要不要管顺序”题干里出现“排列、排队、依次”就用 A出现“选出、任取、组成集合”就用 C。圆桌排列、相邻问题、不相邻问题各有一个固定处理圆桌 n 个人是 (n-1)!要求某两人相邻就把他们捆成一个整体再乘 2要求不相邻就用插空法先排其他人再把指定元素插进空隙。这三招覆盖面很广。鸽巢原理的题通常是“至少多少个里面一定有两个满足某条件”答法是构造“最坏情况下的抽屉”一年 12 个月13 个人必定有两人同月生日n 个抽屉放 n1 个苹果必定有一个抽屉不少于两个。概率题则基本停留在古典概型用“满足条件的方案数除以总方案数”注意题目说的是“至少”还是“恰好”。3. 阅读程序题三篇代码的复杂度判断与代入法路径阅读程序是 2020 卷面里性价比最高也最容易翻车的部分三个程序每个程序配判断题和单选题判断题考“这段代码的正确性、复杂度、边界行为”单选题考“给定输入的输出”。它对算法能力的要求其实不高真正考的是耐心和手算纪律。很多人栽在这里不是因为不会而是因为“看一眼觉得懂了就选”。3.1 先看输入范围再读代码复杂度的三个判据拿到一段代码先别急着逐行读先看三样东西输入规模 n 的范围、循环的嵌套层数、有没有递归。这三样决定了复杂度也决定了你该用多大的数据手算。循环嵌套两层是 O(n²)三层是 O(n³)递归看每次调用把问题缩到多大除以 2 就是 O(log n)减 1 就是 O(n)。下面这段代码是初赛里常见的三层结构先自己判断它的复杂度再算输出#include iostream using namespace std; int a[1005]; int main() { int n, cnt 0; cin n; // 输入规模 n本题 n 1000 for (int i 1; i n; i) a[i] i; // 初始化a[i] i for (int i 1; i n; i) // 枚举区间左端点 for (int j i; j n; j) { // 枚举区间右端点 int s 0; for (int k i; k j; k) s a[k]; // 暴力求区间和第三层循环 if (s % 2 0) cnt; // 统计和为偶数的区间个数 } cout cnt endl; return 0; }逻辑说明外层两重循环枚举所有区间 [i, j]第三重循环把区间内的 a[k] 累加得到 s再判断奇偶。三层循环各自最多 n 次总运算量约为 n³/6复杂度是 O(n³)。参数上n 的取值直接决定运行时间n 1000 时约 1.7 亿次加法这就是为什么初赛只让你手算小数据而不是真跑。答这类题的标准动作是代入小数据。取 n 4数组是 1、2、3、4区间和分别是长度 1 有 1、2、3、4长度 2 有 3、5、7长度 3 有 6、9长度 4 有 10。其中偶数是 6、10、2、4共 4 个输出 4。手算时把区间和列成三角表比在脑子里默念可靠得多。3.2 代入法把小数据手算成表代入法是阅读程序的通用解法关键在“小”和“全”。小是指 n 取 3 到 6 之间太大手算不完太小触发不了边界全是指要把题目给的每种输入都代一遍尤其是“输入保证”里的特殊值。递归程序更要代入而且要画调用树。下面这个函数是 2020 卷面上常见的递归形态int f(int n) { if (n 1) return 1; // 递归出口 if (n % 2 0) return f(n / 2) 1; // 偶数除以 2步数加 1 return f(n - 1) 1; // 奇数减 1 变成偶数步数加 1 }逻辑说明这个函数返回的是“把 n 降到 1 所需的操作步数再加 1”。偶数的操作是除以 2奇数的操作是减 1每条路径都累加一次。参数说明n 必须为正整数n 1 时直接返回 1是递归出口。手算 f(7)f(7) f(6)1 f(3)2 f(2)3 f(1)4 5。手算 f(8)f(8) f(4)1 f(2)2 f(1)3 4。把 n 从 1 到 8 的值列成一行 1、2、2、3、3、4、4、4规律立刻显出来大致等于 ⌊log2 n⌋ 2。有了这张表选项里哪个对直接对号入座。复杂度要单独判断偶数分支每次把 n 减半奇数分支只多走一步总步数是 O(log n) 量级。判断题若写“该函数的时间复杂度为 O(n)”直接判错。3.3 判断题的四个常设陷阱阅读程序的判断题有几套固定陷阱认出来就能避开。第一类是“边界陷阱”代码在 n 1 或数组下标为 0 时会怎样。判断题说“对任意正整数输入都正确”你就去找那个会越界或死循环的边界值。第二类是“类型陷阱”int相乘溢出、char参与运算被当作小整数、整数除法丢小数。代码里出现a * b而两个数都可能接近 10^5 时溢出几乎必然发生判断题很可能就考这一点。第三类是“初始化陷阱”全局数组默认是 0局部数组不初始化就是随机值。如果代码在函数内部定义了数组却直接累加答案就是不确定这类判断题往往判错。第四类是“复杂度陷阱”把 O(n log n) 写成 O(n)把 O(n²) 写成 O(n log n)或者把“最坏”写成“平均”。做判断题时把“最坏、平均、最好”三个词在题干里圈出来能省下不少后悔药。注意阅读程序的单选题通常一个 3 分错一道等于选择题错一道半所以宁可多花两分钟手算也不要靠“感觉这段代码应该是求最大值”蒙。4. 完善程序题从题干条件反推五个空的标准动作完善程序是两题共 30 分每题 5 个空、每空 3 分。它的题干通常先用一段中文说清楚“这个程序要做什么”再给一段挖了空的代码。很多人在这里失分是因为把它当成“写代码题”其实它更像“模板识别题”——命题人挖掉的空绝大多数落在初始化、循环条件和递推转移这三个位置上。4.1 空位分三类初始化、循环条件、递推转移第一类是初始化空出现在变量定义处或循环开始前。判断依据是“这个变量在后面被谁用、按什么语义用”。代码后面写while (l r)那 l 和 r 的初值就必须构成一个合法区间后面写best max(best, cur)那 best 的初值就必须是一个“足够小”的数写成 0 就会在全是负数时出错。第二类是循环条件空出现在for或while里。判断依据是“循环体里最后一次有效操作是什么”。双指针的循环条件通常是l r而不是l r因为 l r 时指向同一个元素两数之和就变成同一个数用两次语义错了。二分查找的循环条件通常是l r因为区间里只剩一个元素时还要再判断一次。第三类是递推转移空出现在状态转移方程或指针移动处。判断依据是“当前状态不满足条件时应该往哪边收缩”。有序数组求和偏小就往大的一边走偏大就往小的一边走动态规划里当前元素接在前一段后面更优还是单独成段更优取决于“前面的累积和是不是正数”。4.2 模板识别双指针与二分答案的两个固定骨架双指针是初赛完善程序的高频题材骨架几乎是固定的。下面这道“有序数组求两数之和”就是标准形态// 在严格递增的数组 a[1..n] 中找一对下标 l r使 a[l] a[r] m // 题目保证有且仅有一组解 int l 1, r n; while (______①______) { int s a[l] a[r]; if (s m) { cout l r endl; return 0; } else if (s m) ______②______; // 和偏小 else ______③______; // 和偏大 }答案是 ①l r、②l、③r--。逻辑说明数组递增左端右移会让和变大右端左移会让和变小所以和偏小就动左端、和偏大就动右端。参数说明① 处不能写l r因为题干要求 l r 且是两数之和写等号会允许同一个元素用两次② ③ 处不能写反写反会让区间朝错误方向收缩直接死循环。二分答案是另一种固定骨架题干里出现“最小的最大值”“最大的最小值”“至少需要多少”“最多能装多少”这类字眼基本就是二分答案// check(x) 表示“以 x 为答案是否可行”且可行性随 x 增大单调不增 int l 1, r n, ans -1; while (l r) { int mid l (r - l) / 2; // 防溢出写法 if (check(mid)) { ans mid; r mid - 1; } // 可行记录并尝试更小 else l mid 1; // 不可行只能往大找 } cout ans endl;逻辑说明这是“求最小可行值”的模板可行就记录下来并往左半区间继续找不可行就往右半区间找。参数说明mid写成l (r - l) / 2而不是(l r) / 2是为了避免 l 和 r 都接近 int 上限时相加溢出这个细节本身就可能是一个空。答案初始化为 -1 表示“暂时没有可行解”如果题目保证有解也可以写成 l 的初值。判断该用哪个模板看题干里的两个词就够了说“单调”“有序”“递增”就往双指针想说“最大值最小”“最小值最大”“判定可行”就往二分答案想。动态规划的题则看有没有“前 i 个”“以 i 结尾”这类状态描述有就是线性 DP。4.3 填完必须回代三步验证法填完空不等于做完必须回代验证而且是三步。第一步代小数据跑一遍。n 3 或 4把每个空里的语句代进去在草稿纸上走完整个流程看输出和题干描述是否一致。这一步能挡掉一半的“左右写反”和“边界少一次”。第二步检查每个变量在第一次被使用之前有没有被赋值。初赛的完善程序特别爱在初始化处挖空而很多人只顾着填循环条件回头发现计数器根本没清零。第三步看特殊输入。全是负数、全部相同、只有一个元素这三种输入是命题人最爱设的暗坑。最大子段和的代码如果把 best 初始化成 0全负数时就返回 0 而不是最大的负数这个空就是典型的“送分变送命”。做完这三步再涂卡比做完就涂多花三分钟但通常能多拿 3 到 6 分。5. 失分点五类最容易翻车的题和对应的纠正答法5.1 机器数与运算类三条必错题错在哪把无符号数的减法当成有符号算或者把char的取值范围记成 0 到 255。典型错法是“unsigned char 类型的 0 减 1 等于 -1”。为什么错无符号数的运算是模 2^n 的0 减 1 会回绕到最大值 255不是负数。很多人脑子里只有“补码”一套规则遇到 unsigned 就直接套用忽略了类型本身的语义。怎么答对遇到无符号数先写出模数 2^n所有运算结果都对模数取模遇到有符号数先写范围再算。判断“溢出”时看清是“编译期常量溢出”还是“运行期回绕”两者结论可能不同。错在哪求负数补码时忘了“取反加一”里的“加一”或者把符号位也一起取反。为什么错补码的定义是“原码除符号位外取反再加一”符号位保持不变。手快的人常常整串取反得到的结果差 1。怎么答对固定写三步写出绝对值的二进制、除符号位外逐位取反、末位加一。写完用“补码加原码绝对值应等于 2^n”验算一次。错在哪混淆 ASCII 码里数字字符和数字本身的差。看到7 - 0以为是 7 的编码。为什么错字符0到9的编码是连续的 48 到 57两个字符相减得到的是它们的编码差恰好等于数值差7 - 0得 7 是对的但7 - 7得到的是 48 这个编码值不是 0。怎么答对记住三个锚点0是 48、A是 65、a是 97。字符与数字互转时一律通过减0或加0完成别直接加减整数。5.2 程序阅读与填空类两条必错题错在哪阅读程序里看到双重循环就写 O(n²)没注意内层循环的上界是变化的。为什么错内层循环上界跟着外层走时总运算量常常是 n(n1)/2量级仍是 O(n²)但如果内层是倍增的j * 2总复杂度就降到 O(n log n)。只看“几层循环”这个表面特征一定会判断错。怎么答对数循环次数要看“每个循环变量实际走了多少步”而不是看嵌套层数。外层 n 次、内层 log n 次就是 O(n log n)外层 n 次、内层从 i 开始就是 O(n²) 但常数只有一半。错在哪完善程序里把所有空都填成“看起来最合理”的那句填完不代数据直接涂卡。为什么错五个空之间有依赖关系前一个空填错后面四个全废。命题人恰恰会把最像正确答案的干扰项放在最前面。怎么答对先通读题干的中文描述把“程序要做什么”写成一句话再按“初始化 → 循环条件 → 转移”的顺序填填完用 n 3 走一遍。凡是填完说不清“这个变量现在代表什么”的空一律重填。6. 押题与临场把 2020 两张卷子拆成一套可复用的答题流程把 2020 年的两张卷子当模板复盘比刷十套来源不明的模拟题管用。具体做法是四个动作每个动作都对应一个明确的产出。第一个动作是分模块统计错题。把两张卷子的错题按第 2 章那七块分类统计每块错了几道。如果进制和机器数错 3 道以上说明这块根本没建立条件反射需要重新背取值范围和补码三步如果阅读程序错得多说明问题不在知识而在手算纪律。统计完你会发现失分往往集中在两块而不是均匀分布。第二个动作是把阅读程序的代码抄一遍。抄的时候把每个变量的含义写在注释里抄完对着题目再算一次输出。这个动作的价值在于暴露“我以为我懂了”的地方很多代码看的时候觉得清楚一落笔就发现不知道自己算的是哪一步。第三个动作是把完善程序的五个空遮住自己从头写一遍。写不出来再看答案然后合上答案再写一遍。初赛的完善程序题材高度重复双指针、二分答案、线性 DP、简单图遍历、字符串处理把这五类各写三遍考场上基本就是认模板。第四个动作是限时套卷。120 分钟选择题 30 分钟、阅读程序 45 分钟、完善程序 35 分钟留 10 分钟检查。限时不是为了压速度而是为了让你体验“在时间压力下仍然坚持手算”的感觉这个习惯只能靠练出来。时间分配上有个血泪经验不要在选择题上恋战。一道题超过 90 秒还没有明确思路先标记跳过把会做的全做完再回头。初赛的选择题里总有两三道是“记忆型偏门知识”卡在那里性价比极低而后面阅读程序的 3 分题反而更好拿。题型分值建议用时拿分目标单项选择30 分30 分钟24 分以上阅读程序40 分45 分钟28 分以上完善程序30 分35 分钟21 分以上检查—10 分钟补标记题、核对答题卡最后说一个最容易被忽略的点两套卷子的难度并不完全相同入门组和提高组的同一知识点问法深度不一样。入门组的阅读程序更偏“模拟”提高组更偏“复杂度判断和边界”。复盘时把两组同知识点的题并排看能很清楚地看出命题人的加码方向这比单纯记住某道题的答案有用得多。从那以后我每次带人复盘初赛都强制走一遍“分模块统计 → 抄代码 → 遮空重写 → 限时套卷”这四步谁跳过第一步后面三步就都在重复犯同一个错。这套流程用在这份 2020 年 CSP-J1、CSP-S1 的答案解析材料上正好试题、答案、解析都在同一处逐题过完就能直接整理出自己的错题分布表再从表里挑最薄弱的两块反复练。希望帮到你。本文还有配套的精品资源点击获取