简介这份PDF资料面向备战CSP-J/S初赛的信奥选手与算法竞赛入门学习者系统梳理了初赛所需的核心知识点与真题解析。内容覆盖计算机结构与组成、算法竞赛准备、计算机基础、计数与组合数学、进制转换与位运算等模块并汇总了2020年CSP-J/S初赛试题讲解、历年NOIP/CSP普及组真题解析、优秀拆分等典型题目分析以及初赛形式说明与模拟题资源便于读者按知识板块查漏补缺、对照真题复盘解题思路。资源包共1个PDF文件约1.23MB56页篇幅结构清晰适合赛前集中复习与日常知识点巩固。目前已有1983人学习下载可作为初赛备考阶段的知识梳理与真题演练参考。1. 从一份 56 页的 CSP-J1/S1 解析说起初赛到底在考什么每年九月信息学奥赛圈子里最热闹的话题之一就是 CSP-J1 和 CSP-S1 的初赛。很多人第一次接触这套卷子时会觉得它像一门玄学——全是选择题却比写代码还难拿分。我见过太多选手复赛能 AC 好几道题初赛却卡在分数线下面连门都进不去。这份 56 页的解析文档把 2020 年 CSP-J1 和 CSP-S1 的题目逐道拆开讲正好是一个把初赛从凭感觉蒙变成有章法做的切入点。初赛考的不是你会不会写代码而是你对计算机科学基础的掌握程度进制转换、逻辑运算、数据结构性质、算法复杂度、组合数学、图论常识还有一点点计算机组成原理。它像一张筛子筛掉那些只会背模板、不理解原理的人。这篇文章不打算复述那份 PDF 的每一道题而是借它把初赛备考这件事讲透——考什么、怎么练、参数怎么记、坑在哪。适合正在准备 CSP-J1/S1 的选手也适合想系统梳理计算机基础的从业者。2. CSP-J1 与 CSP-S1 的题型拆解从 2020 年卷面看命题逻辑2.1 两张卷子的结构差异与共同底盘CSP-J1入门级和 CSP-S1提高级在题型结构上高度相似都是 15 道单选 5 道阅读程序 2 道完善程序但难度和知识覆盖有明显分层。2020 年的 J1 卷子里前 15 道单选大量涉及进制转换、ASCII 码、二叉树性质、简单排列组合S1 卷子则在同一位置塞进了更深的复杂度分析、图论概念、递归式求解和位运算技巧。共同底盘是计算机基础 数学 数据结构 算法常识。这四块在两张卷子里都出现只是 S1 的题目会多绕一到两个弯。比如同样是考二叉树J1 可能直接给你节点数问叶子数S1 则会结合完全二叉树编号、遍历序列还原、或者带权路径长度来出题。阅读程序题是分水岭。J1 的阅读程序通常是一段 20 到 30 行的代码考的是循环边界、数组下标、简单递归S1 的阅读程序会出现位运算压缩、字符串哈希、动态规划状态转移甚至需要你在脑子里模拟一个小型算法。完善程序题则更直接——给你一个算法框架挖 5 个空考的是你对标准算法实现细节的记忆和理解。2.2 从 2020 年真题看高频考点分布把 2020 年 J1 和 S1 的题目按知识点归类能看出一个很明显的分布规律。下面这张表是我自己整理的高频考点对照不是官方数据但和历年趋势基本吻合考点类别J1 出现频次S1 出现频次典型考法进制与编码3-4 题2-3 题二进制/十六进制转换、补码、ASCII逻辑与位运算2-3 题3-4 题与或非异或、移位、掩码数据结构性质3-4 题4-5 题二叉树、栈队列、哈希、图算法复杂度2-3 题3-4 题时间/空间复杂度、递归式组合数学2-3 题3-4 题排列组合、容斥、概率计算机组成1-2 题1-2 题存储单位、CPU、总线图论基础1-2 题2-3 题最短路、生成树、拓扑排序从这张表能看出数据结构和算法复杂度是两张卷子的绝对重心合计占了一半以上的分值。进制和位运算虽然题量不大但几乎是必考而且容易因为粗心丢分。组合数学在 S1 里的权重明显高于 J1因为提高级更看重数学建模能力。2.3 阅读程序题的拆解方法手动模拟 边界标记阅读程序题是很多人翻车的地方。代码不长但陷阱密集。我自己的做法是三步走第一步先看输入输出格式确定程序在干什么。很多题目会在注释里暗示算法类型比如求最大子段和或者判断回文。第二步手动模拟小数据。不要试图在脑子里跑完整程序而是取 n3 或 n4 的小规模把每一步的变量值写在草稿纸上。这一步能解决 80% 的阅读程序题。第三步标记边界条件。循环的起止、数组下标是从 0 还是 1 开始、递归的终止条件、取模的时机——这些地方是出题人最爱挖坑的位置。以 2020 年 S1 的一道阅读程序为例题目给了一段看似简单的递归函数但递归深度和返回值类型都有陷阱。如果只靠眼睛看很容易忽略整数溢出或者递归基写错的情况。手动模拟 n5 的情况把每次调用的参数和返回值列成表格问题就一目了然。2.4 完善程序题的填空策略从算法框架反推完善程序题考的是补全标准算法。这类题目的特点是算法你一定见过但实现细节你不一定记得住。比如快速排序的分区、Dijkstra 的松弛、KMP 的 next 数组、01 背包的倒序循环。我的策略是先识别算法再回忆模板最后用变量名和上下文验证。2020 年 S1 有一道完善程序考的是区间 DP空的位置分别在状态定义、转移方程和边界初始化。如果你知道区间 DP 的通用框架是f[i][j] min(f[i][k] f[k1][j] cost)那么填空时只需要确认循环顺序和 cost 的计算方式。这里有一个血泪经验不要凭感觉填要用小数据验证。填完之后取一个 n3 的简单例子手动跑一遍你填的代码看结果是否符合预期。这一步能救回很多因为下标写错而丢的分。3. 初赛核心知识点的最小复习路径从进制到复杂度3.1 进制转换与位运算必须练到条件反射进制转换是初赛的送分题但也是粗心重灾区。十进制转二进制用除二取余二进制转十六进制用四位一组这些方法大家都知道但考场上时间紧容易算错。我的建议是把 0 到 255 的二进制和十六进制对照表背下来至少做到看到 0x3F 能立刻反应出是 63看到 0b101101 能立刻算出是 45。位运算在 S1 里考得更深。常见的考点包括x (x-1)消除最低位的 1x -x取出最低位的 1x ^ x 0用于判断成对出现移位运算的优先级低于加减法下面这段 Python 代码可以用来验证你对位运算的理解建议在本地跑一遍把每个表达式的结果和你的预期对比# 位运算常见性质验证 x 0b10110100 # 180 # 消除最低位的 1 print(bin(x (x - 1))) # 0b10110000最低位的 1 被消除 # 取出最低位的 1 print(bin(x -x)) # 0b100只保留最低位的 1 # 判断是否为 2 的幂 print((x (x - 1)) 0) # False因为 x 不是 2 的幂 # 异或交换两个数 a, b 5, 9 a ^ b b ^ a a ^ b print(a, b) # 9 5交换成功 # 移位优先级 print(1 2 3) # 32因为 优先级高于 这段代码的关键在于理解每个操作的二进制含义。x (x-1)之所以能消除最低位的 1是因为减一会把最低位的 1 变成 0并把后面的 0 全变成 1再与运算就只剩高位不变。x -x利用的是补码性质-x的二进制是x取反加一与运算后只保留最低位的 1。参数说明x取任意正整数建议从 1 到 255 逐个测试观察二进制变化。移位运算的优先级问题在初赛里考过多次记住口诀加减乘除高于移位移位高于比较比较高于逻辑。3.2 数据结构性质二叉树、栈、队列、哈希的必记结论数据结构部分初赛最爱考的是性质类结论而不是实现。比如二叉树第 i 层最多有 2^(i-1) 个节点深度为 k 的二叉树最多有 2^k - 1 个节点完全二叉树中节点 i 的左孩子是 2i右孩子是 2i1n 个节点的二叉树有 C(2n, n)/(n1) 种形态卡特兰数栈的出栈序列数量也是卡特兰数哈希表在理想情况下查找复杂度是 O(1)最坏是 O(n)这些结论不需要推导但必须记牢。2020 年 J1 考了一道完全二叉树编号的题目如果记得 2i 和 2i1 的规律十秒钟就能选出答案如果不记得现场推导至少要两分钟。栈和队列的题目通常考合法出栈序列或者循环队列的判空判满。循环队列的判满条件常见有两种牺牲一个存储单元或者用计数器。初赛里如果考到注意看题目给的是哪种实现。哈希部分初赛一般考冲突处理和装填因子。线性探测、二次探测、链地址法这三种要能区分。装填因子 元素个数 / 表长装填因子越大冲突概率越高。3.3 算法复杂度分析主定理与递归式求解复杂度分析是 S1 的必考内容而且往往结合递归式出题。常见的形式是T(n) aT(n/b) f(n)要求你判断时间复杂度。主定理Master Theorem是解这类题的利器但初赛不会考太复杂的变形。记住三种情况如果 f(n) O(n^(log_b(a) - ε))则 T(n) Θ(n^(log_b(a)))如果 f(n) Θ(n^(log_b(a)))则 T(n) Θ(n^(log_b(a)) * log n)如果 f(n) Ω(n^(log_b(a) ε))且满足正则条件则 T(n) Θ(f(n))举个例子T(n) 2T(n/2) n。这里 a2, b2, log_b(a)1, f(n)n属于第二种情况所以 T(n) O(n log n)。这就是归并排序的复杂度。如果不想记主定理也可以用递归树展开。把每一层的代价写出来求和即可。2020 年 S1 有一道题考的是 T(n) T(n-1) n展开后是 n (n-1) ... 1 O(n^2)这是冒泡排序的复杂度。下面这段代码可以用来验证不同算法的实际运行时间帮助你建立复杂度直觉import time def bubble_sort(arr): n len(arr) for i in range(n): for j in range(n - i - 1): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] return arr def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): result [] i j 0 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 result.extend(left[i:]) result.extend(right[j:]) return result # 测试不同规模下的运行时间 for n in [100, 500, 1000]: data list(range(n, 0, -1)) start time.time() bubble_sort(data[:]) t1 time.time() - start start time.time() merge_sort(data[:]) t2 time.time() - start print(fn{n}: bubble{t1:.4f}s, merge{t2:.4f}s)这段代码对比了冒泡排序和归并排序的实际运行时间。冒泡排序是 O(n^2)归并排序是 O(n log n)。当 n 从 100 增加到 1000 时冒泡排序的时间增长大约是 100 倍而归并排序只增长约 10 倍。这个实验能帮你直观感受复杂度差异而不是死记公式。参数说明n是数据规模建议从 100 开始逐步增加到 1000 或 2000。注意冒泡排序在 n2000 时可能已经明显变慢这是正常的。data是逆序列表这是两种排序的最坏情况之一。3.4 组合数学与概率初赛里的数学题怎么破组合数学在初赛里的考法比较固定排列组合、容斥原理、鸽巢原理、简单概率。2020 年 J1 考了一道从 5 个人里选 3 个人排成一排的题直接套 A(5,3) 60 就行。S1 则考了一道带限制条件的排列需要用容斥或者分类讨论。必记公式排列数 A(n, m) n! / (n-m)!组合数 C(n, m) n! / (m! * (n-m)!)卡特兰数 C_n C(2n, n) / (n1)容斥原理|A ∪ B| |A| |B| - |A ∩ B|概率题一般考古典概型关键是数清楚样本空间和事件空间。如果题目复杂可以画树状图或者列表。4. 避坑与排查初赛备考中最容易翻车的 5 个地方4.1 坑一进制转换时符号位和补码搞混现象题目给一个 8 位二进制数 11111111问它作为有符号整数是多少。很多人答 255但正确答案是 -1。原因没有区分无符号数和有符号数。在有符号补码表示中最高位是符号位11111111 表示 -1。解决看到二进制数先问自己这是有符号还是无符号。如果是补码先判断最高位再决定是否取反加一。平时练习时把 8 位补码的 -128 到 127 对照表过一遍。4.2 坑二阅读程序时忽略循环变量的作用域现象阅读程序题里有两层循环内层和外层用了同一个变量名或者内层修改了外层变量的值导致模拟结果和实际不符。原因C 里变量的作用域是块级的但初赛代码经常写得很紧凑容易看漏。解决模拟时把每个变量的当前值写在草稿纸的表格里每执行一行就更新一次。遇到同名变量标注清楚是哪个作用域的。4.3 坑三完善程序填空时下标从 0 还是 1 开始没确认现象填完代码后运行结果总是差一位或者数组越界。原因题目给的代码框架可能用 0-based 下标也可能用 1-based 下标填空时没有统一。解决先看数组声明和循环起止确定下标基准。如果题目用for (int i 1; i n; i)那数组大小至少是 n1填空时所有下标都要加一。4.4 坑四复杂度分析时把 log 的底数搞错现象题目问 T(n) 2T(n/4) n 的复杂度有人答 O(n log n)实际是 O(n)。原因log_b(a) 中 b4, a2log_4(2) 0.5而 f(n)n 是 O(n^1)大于 n^0.5所以属于主定理第三种情况T(n) O(n)。解决套主定理前先算 log_b(a)再和 f(n) 的指数比较。如果不想算用递归树展开看每一层的代价和层数。4.5 坑五考试时在一道题上死磕超过 5 分钟现象前面一道阅读程序题卡住了花了 15 分钟后面完善程序没时间做。原因初赛题量不小平均每道题只有 2 到 3 分钟。死磕一道题会打乱节奏。解决给自己定规矩——单选题超过 1 分钟没思路就标记跳过阅读程序超过 5 分钟没模拟完就猜一个完善程序超过 8 分钟就凭第一感觉填。全部做完后再回头检查标记的题。5. 从 56 页解析到考场实战把错题变成得分点那份 56 页的解析文档最大的价值不是告诉你正确答案而是展示每道题的思考路径。我自己的习惯是做完一套真题后把错题按知识点分类然后针对每个知识点找 3 到 5 道同类题集中练。比如进制转换错了就连续做 10 道进制题直到条件反射为止。下面这张表是我用来跟踪错题的知识点清单你可以直接抄知识点错题数重做日期是否掌握补码与符号位2考前一周是二叉树性质1考前三天是主定理3考前一周否容斥原理1考前三天是位运算优先级2考前一周是对于否的知识点不要只背结论要找一道最简单的例题手动推一遍。比如主定理不熟就从 T(n) 2T(n/2) n 开始画递归树数层数算每层代价最后求和。推完三道题基本就记住了。还有一个技巧把阅读程序题当代码调试来练。找一台电脑把题目里的代码敲进去加打印语句看每一步的变量值。这比纯手算快得多而且能发现很多肉眼看不到的陷阱。2020 年 S1 有一道阅读程序考的是字符串哈希我在本地跑了一遍发现哈希冲突的处理方式和我想的不一样这个教训在考场上直接帮我避开了一道类似的题。最后说一个我自己的习惯考前一周每天限时做一套真题做完立刻对答案、记错题。不追求分数追求的是把每一道错题的原因写清楚。是知识点不会还是粗心还是时间不够。知识点不会就补知识点粗心就练检查时间不够就调整做题顺序。这个习惯让我从第一次初赛差 3 分到后来稳定高出分数线 20 分以上。希望帮到你。本文还有配套的精品资源点击获取
简介这份PDF资料面向备战CSP-J/S初赛的信奥选手与算法竞赛入门学习者系统梳理了初赛所需的核心知识点与真题解析。内容覆盖计算机结构与组成、算法竞赛准备、计算机基础、计数与组合数学、进制转换与位运算等模块并汇总了2020年CSP-J/S初赛试题讲解、历年NOIP/CSP普及组真题解析、优秀拆分等典型题目分析以及初赛形式说明与模拟题资源便于读者按知识板块查漏补缺、对照真题复盘解题思路。资源包共1个PDF文件约1.23MB56页篇幅结构清晰适合赛前集中复习与日常知识点巩固。目前已有1983人学习下载可作为初赛备考阶段的知识梳理与真题演练参考。1. 从一份 56 页的 CSP-J1/S1 解析说起初赛到底在考什么每年九月信息学奥赛圈子里最热闹的话题之一就是 CSP-J1 和 CSP-S1 的初赛。很多人第一次接触这套卷子时会觉得它像一门玄学——全是选择题却比写代码还难拿分。我见过太多选手复赛能 AC 好几道题初赛却卡在分数线下面连门都进不去。这份 56 页的解析文档把 2020 年 CSP-J1 和 CSP-S1 的题目逐道拆开讲正好是一个把初赛从凭感觉蒙变成有章法做的切入点。初赛考的不是你会不会写代码而是你对计算机科学基础的掌握程度进制转换、逻辑运算、数据结构性质、算法复杂度、组合数学、图论常识还有一点点计算机组成原理。它像一张筛子筛掉那些只会背模板、不理解原理的人。这篇文章不打算复述那份 PDF 的每一道题而是借它把初赛备考这件事讲透——考什么、怎么练、参数怎么记、坑在哪。适合正在准备 CSP-J1/S1 的选手也适合想系统梳理计算机基础的从业者。2. CSP-J1 与 CSP-S1 的题型拆解从 2020 年卷面看命题逻辑2.1 两张卷子的结构差异与共同底盘CSP-J1入门级和 CSP-S1提高级在题型结构上高度相似都是 15 道单选 5 道阅读程序 2 道完善程序但难度和知识覆盖有明显分层。2020 年的 J1 卷子里前 15 道单选大量涉及进制转换、ASCII 码、二叉树性质、简单排列组合S1 卷子则在同一位置塞进了更深的复杂度分析、图论概念、递归式求解和位运算技巧。共同底盘是计算机基础 数学 数据结构 算法常识。这四块在两张卷子里都出现只是 S1 的题目会多绕一到两个弯。比如同样是考二叉树J1 可能直接给你节点数问叶子数S1 则会结合完全二叉树编号、遍历序列还原、或者带权路径长度来出题。阅读程序题是分水岭。J1 的阅读程序通常是一段 20 到 30 行的代码考的是循环边界、数组下标、简单递归S1 的阅读程序会出现位运算压缩、字符串哈希、动态规划状态转移甚至需要你在脑子里模拟一个小型算法。完善程序题则更直接——给你一个算法框架挖 5 个空考的是你对标准算法实现细节的记忆和理解。2.2 从 2020 年真题看高频考点分布把 2020 年 J1 和 S1 的题目按知识点归类能看出一个很明显的分布规律。下面这张表是我自己整理的高频考点对照不是官方数据但和历年趋势基本吻合考点类别J1 出现频次S1 出现频次典型考法进制与编码3-4 题2-3 题二进制/十六进制转换、补码、ASCII逻辑与位运算2-3 题3-4 题与或非异或、移位、掩码数据结构性质3-4 题4-5 题二叉树、栈队列、哈希、图算法复杂度2-3 题3-4 题时间/空间复杂度、递归式组合数学2-3 题3-4 题排列组合、容斥、概率计算机组成1-2 题1-2 题存储单位、CPU、总线图论基础1-2 题2-3 题最短路、生成树、拓扑排序从这张表能看出数据结构和算法复杂度是两张卷子的绝对重心合计占了一半以上的分值。进制和位运算虽然题量不大但几乎是必考而且容易因为粗心丢分。组合数学在 S1 里的权重明显高于 J1因为提高级更看重数学建模能力。2.3 阅读程序题的拆解方法手动模拟 边界标记阅读程序题是很多人翻车的地方。代码不长但陷阱密集。我自己的做法是三步走第一步先看输入输出格式确定程序在干什么。很多题目会在注释里暗示算法类型比如求最大子段和或者判断回文。第二步手动模拟小数据。不要试图在脑子里跑完整程序而是取 n3 或 n4 的小规模把每一步的变量值写在草稿纸上。这一步能解决 80% 的阅读程序题。第三步标记边界条件。循环的起止、数组下标是从 0 还是 1 开始、递归的终止条件、取模的时机——这些地方是出题人最爱挖坑的位置。以 2020 年 S1 的一道阅读程序为例题目给了一段看似简单的递归函数但递归深度和返回值类型都有陷阱。如果只靠眼睛看很容易忽略整数溢出或者递归基写错的情况。手动模拟 n5 的情况把每次调用的参数和返回值列成表格问题就一目了然。2.4 完善程序题的填空策略从算法框架反推完善程序题考的是补全标准算法。这类题目的特点是算法你一定见过但实现细节你不一定记得住。比如快速排序的分区、Dijkstra 的松弛、KMP 的 next 数组、01 背包的倒序循环。我的策略是先识别算法再回忆模板最后用变量名和上下文验证。2020 年 S1 有一道完善程序考的是区间 DP空的位置分别在状态定义、转移方程和边界初始化。如果你知道区间 DP 的通用框架是f[i][j] min(f[i][k] f[k1][j] cost)那么填空时只需要确认循环顺序和 cost 的计算方式。这里有一个血泪经验不要凭感觉填要用小数据验证。填完之后取一个 n3 的简单例子手动跑一遍你填的代码看结果是否符合预期。这一步能救回很多因为下标写错而丢的分。3. 初赛核心知识点的最小复习路径从进制到复杂度3.1 进制转换与位运算必须练到条件反射进制转换是初赛的送分题但也是粗心重灾区。十进制转二进制用除二取余二进制转十六进制用四位一组这些方法大家都知道但考场上时间紧容易算错。我的建议是把 0 到 255 的二进制和十六进制对照表背下来至少做到看到 0x3F 能立刻反应出是 63看到 0b101101 能立刻算出是 45。位运算在 S1 里考得更深。常见的考点包括x (x-1)消除最低位的 1x -x取出最低位的 1x ^ x 0用于判断成对出现移位运算的优先级低于加减法下面这段 Python 代码可以用来验证你对位运算的理解建议在本地跑一遍把每个表达式的结果和你的预期对比# 位运算常见性质验证 x 0b10110100 # 180 # 消除最低位的 1 print(bin(x (x - 1))) # 0b10110000最低位的 1 被消除 # 取出最低位的 1 print(bin(x -x)) # 0b100只保留最低位的 1 # 判断是否为 2 的幂 print((x (x - 1)) 0) # False因为 x 不是 2 的幂 # 异或交换两个数 a, b 5, 9 a ^ b b ^ a a ^ b print(a, b) # 9 5交换成功 # 移位优先级 print(1 2 3) # 32因为 优先级高于 这段代码的关键在于理解每个操作的二进制含义。x (x-1)之所以能消除最低位的 1是因为减一会把最低位的 1 变成 0并把后面的 0 全变成 1再与运算就只剩高位不变。x -x利用的是补码性质-x的二进制是x取反加一与运算后只保留最低位的 1。参数说明x取任意正整数建议从 1 到 255 逐个测试观察二进制变化。移位运算的优先级问题在初赛里考过多次记住口诀加减乘除高于移位移位高于比较比较高于逻辑。3.2 数据结构性质二叉树、栈、队列、哈希的必记结论数据结构部分初赛最爱考的是性质类结论而不是实现。比如二叉树第 i 层最多有 2^(i-1) 个节点深度为 k 的二叉树最多有 2^k - 1 个节点完全二叉树中节点 i 的左孩子是 2i右孩子是 2i1n 个节点的二叉树有 C(2n, n)/(n1) 种形态卡特兰数栈的出栈序列数量也是卡特兰数哈希表在理想情况下查找复杂度是 O(1)最坏是 O(n)这些结论不需要推导但必须记牢。2020 年 J1 考了一道完全二叉树编号的题目如果记得 2i 和 2i1 的规律十秒钟就能选出答案如果不记得现场推导至少要两分钟。栈和队列的题目通常考合法出栈序列或者循环队列的判空判满。循环队列的判满条件常见有两种牺牲一个存储单元或者用计数器。初赛里如果考到注意看题目给的是哪种实现。哈希部分初赛一般考冲突处理和装填因子。线性探测、二次探测、链地址法这三种要能区分。装填因子 元素个数 / 表长装填因子越大冲突概率越高。3.3 算法复杂度分析主定理与递归式求解复杂度分析是 S1 的必考内容而且往往结合递归式出题。常见的形式是T(n) aT(n/b) f(n)要求你判断时间复杂度。主定理Master Theorem是解这类题的利器但初赛不会考太复杂的变形。记住三种情况如果 f(n) O(n^(log_b(a) - ε))则 T(n) Θ(n^(log_b(a)))如果 f(n) Θ(n^(log_b(a)))则 T(n) Θ(n^(log_b(a)) * log n)如果 f(n) Ω(n^(log_b(a) ε))且满足正则条件则 T(n) Θ(f(n))举个例子T(n) 2T(n/2) n。这里 a2, b2, log_b(a)1, f(n)n属于第二种情况所以 T(n) O(n log n)。这就是归并排序的复杂度。如果不想记主定理也可以用递归树展开。把每一层的代价写出来求和即可。2020 年 S1 有一道题考的是 T(n) T(n-1) n展开后是 n (n-1) ... 1 O(n^2)这是冒泡排序的复杂度。下面这段代码可以用来验证不同算法的实际运行时间帮助你建立复杂度直觉import time def bubble_sort(arr): n len(arr) for i in range(n): for j in range(n - i - 1): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] return arr def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): result [] i j 0 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 result.extend(left[i:]) result.extend(right[j:]) return result # 测试不同规模下的运行时间 for n in [100, 500, 1000]: data list(range(n, 0, -1)) start time.time() bubble_sort(data[:]) t1 time.time() - start start time.time() merge_sort(data[:]) t2 time.time() - start print(fn{n}: bubble{t1:.4f}s, merge{t2:.4f}s)这段代码对比了冒泡排序和归并排序的实际运行时间。冒泡排序是 O(n^2)归并排序是 O(n log n)。当 n 从 100 增加到 1000 时冒泡排序的时间增长大约是 100 倍而归并排序只增长约 10 倍。这个实验能帮你直观感受复杂度差异而不是死记公式。参数说明n是数据规模建议从 100 开始逐步增加到 1000 或 2000。注意冒泡排序在 n2000 时可能已经明显变慢这是正常的。data是逆序列表这是两种排序的最坏情况之一。3.4 组合数学与概率初赛里的数学题怎么破组合数学在初赛里的考法比较固定排列组合、容斥原理、鸽巢原理、简单概率。2020 年 J1 考了一道从 5 个人里选 3 个人排成一排的题直接套 A(5,3) 60 就行。S1 则考了一道带限制条件的排列需要用容斥或者分类讨论。必记公式排列数 A(n, m) n! / (n-m)!组合数 C(n, m) n! / (m! * (n-m)!)卡特兰数 C_n C(2n, n) / (n1)容斥原理|A ∪ B| |A| |B| - |A ∩ B|概率题一般考古典概型关键是数清楚样本空间和事件空间。如果题目复杂可以画树状图或者列表。4. 避坑与排查初赛备考中最容易翻车的 5 个地方4.1 坑一进制转换时符号位和补码搞混现象题目给一个 8 位二进制数 11111111问它作为有符号整数是多少。很多人答 255但正确答案是 -1。原因没有区分无符号数和有符号数。在有符号补码表示中最高位是符号位11111111 表示 -1。解决看到二进制数先问自己这是有符号还是无符号。如果是补码先判断最高位再决定是否取反加一。平时练习时把 8 位补码的 -128 到 127 对照表过一遍。4.2 坑二阅读程序时忽略循环变量的作用域现象阅读程序题里有两层循环内层和外层用了同一个变量名或者内层修改了外层变量的值导致模拟结果和实际不符。原因C 里变量的作用域是块级的但初赛代码经常写得很紧凑容易看漏。解决模拟时把每个变量的当前值写在草稿纸的表格里每执行一行就更新一次。遇到同名变量标注清楚是哪个作用域的。4.3 坑三完善程序填空时下标从 0 还是 1 开始没确认现象填完代码后运行结果总是差一位或者数组越界。原因题目给的代码框架可能用 0-based 下标也可能用 1-based 下标填空时没有统一。解决先看数组声明和循环起止确定下标基准。如果题目用for (int i 1; i n; i)那数组大小至少是 n1填空时所有下标都要加一。4.4 坑四复杂度分析时把 log 的底数搞错现象题目问 T(n) 2T(n/4) n 的复杂度有人答 O(n log n)实际是 O(n)。原因log_b(a) 中 b4, a2log_4(2) 0.5而 f(n)n 是 O(n^1)大于 n^0.5所以属于主定理第三种情况T(n) O(n)。解决套主定理前先算 log_b(a)再和 f(n) 的指数比较。如果不想算用递归树展开看每一层的代价和层数。4.5 坑五考试时在一道题上死磕超过 5 分钟现象前面一道阅读程序题卡住了花了 15 分钟后面完善程序没时间做。原因初赛题量不小平均每道题只有 2 到 3 分钟。死磕一道题会打乱节奏。解决给自己定规矩——单选题超过 1 分钟没思路就标记跳过阅读程序超过 5 分钟没模拟完就猜一个完善程序超过 8 分钟就凭第一感觉填。全部做完后再回头检查标记的题。5. 从 56 页解析到考场实战把错题变成得分点那份 56 页的解析文档最大的价值不是告诉你正确答案而是展示每道题的思考路径。我自己的习惯是做完一套真题后把错题按知识点分类然后针对每个知识点找 3 到 5 道同类题集中练。比如进制转换错了就连续做 10 道进制题直到条件反射为止。下面这张表是我用来跟踪错题的知识点清单你可以直接抄知识点错题数重做日期是否掌握补码与符号位2考前一周是二叉树性质1考前三天是主定理3考前一周否容斥原理1考前三天是位运算优先级2考前一周是对于否的知识点不要只背结论要找一道最简单的例题手动推一遍。比如主定理不熟就从 T(n) 2T(n/2) n 开始画递归树数层数算每层代价最后求和。推完三道题基本就记住了。还有一个技巧把阅读程序题当代码调试来练。找一台电脑把题目里的代码敲进去加打印语句看每一步的变量值。这比纯手算快得多而且能发现很多肉眼看不到的陷阱。2020 年 S1 有一道阅读程序考的是字符串哈希我在本地跑了一遍发现哈希冲突的处理方式和我想的不一样这个教训在考场上直接帮我避开了一道类似的题。最后说一个我自己的习惯考前一周每天限时做一套真题做完立刻对答案、记错题。不追求分数追求的是把每一道错题的原因写清楚。是知识点不会还是粗心还是时间不够。知识点不会就补知识点粗心就练检查时间不够就调整做题顺序。这个习惯让我从第一次初赛差 3 分到后来稳定高出分数线 20 分以上。希望帮到你。本文还有配套的精品资源点击获取
