CSP-J 第一轮通关指南 CSP-J R1 Passport¶

面向 CSP-J（入门级）第一轮（初赛）。本文按 NOI 大纲 2025（入门级）梳理常考知识点，结合 CSP-J 2025 真题、洛谷 SCP2025-J 与 SCP2026-J1（偏难）模拟赛，总结"初赛爱考、平时写题很少用"的内容，并给出经验之谈与易错坑点。

参考：NOI 大纲 2025 ｜ CSP-J 2025 真题｜洛谷 SCP2025-J、SCP2026-J1 模拟赛

每个考点统一按「知识点 → 讲解 → 例题 → 解析 → 易错辨析 / 常见变形 / 使用条件与技巧」的结构整理：先讲清楚概念，再给真题例子，最后收口"哪里会错、还能怎么变、什么时候能用"。

0. 考试结构先搞清楚¶

板块	题量	分值	题型
单项选择题	15 题	30 分（每题 2 分）	四选一
阅读程序	3 题 17 小问	40 分	判断 T/F（2 分）+ 单选（3 分）+ 多选（4 分）
完善程序	2 题 10 小问	30 分（每题 3 分）	选代码片段

时间与策略

考试 120 分钟。建议：单选 25~30 min，阅读程序 50~60 min，完善程序 30 min，留 10 min 检查。
判断题不会做也要蒙一个（近年初赛答错不倒扣，以当年通知为准），空着一定没分。
先易后难：阅读程序往往比单选更好拿分，别在单选最后一题死磕。

1. 计算机基础（初赛专属，复赛完全用不到）¶

1.1 计算机组成¶

讲解

CPU = 运算器（ALU）+ 控制器（CU）+ 寄存器组。ALU 负责算术/逻辑运算。
内存（RAM） 断电数据丢失；外存（硬盘、U 盘）断电保留；Cache 是 CPU 与内存之间的高速缓冲。
存储层次：寄存器 > Cache > 内存 > 外存（速度递减、容量递增、单位成本递减）。

易错辨析

"ALU 属于 CPU 的一部分"是经典送分/送命题（SCP2026 考过）——ALU 是 CPU 的内部部件，别当成独立于 CPU 的器件。
文件存在外存上，程序运行时才调入内存；"关机后数据还在"说的是外存。RAM 一断电就清空。

1.2 操作系统与文件命令（Linux 为主）¶

讲解

常用命令对照表：

命令	作用	备注
`pwd`	显示当前目录
`cd`	切换目录	`cd ..` 上一级
`ls`	列出文件
`mkdir`	新建目录	多层需 `mkdir -p`
`rm -r`	递归删除	慎用
`cp` / `mv`	复制 / 移动（重命名）
`g++ a.cpp -o a`	编译	头文件不参与编译

路径记号：/ 根目录，. 当前目录，.. 父目录，~ 当前用户家目录，- 上次所在目录。
绝对路径以 / 开头；相对路径从当前目录出发。

易错辨析

~ 表示当前登录用户的家目录，不等于别人的家目录。若当前用户在 /home/luogu，mkdir ~/sjtu/phd/paper 建到的是 /home/luogu/sjtu/phd/paper 而不是 /home/sjtu/...（SCP2026 考过）。
做题方法：把整条命令翻译成"起点 + 操作 + 目标路径"再核对，别凭感觉选。
编译命令别写反：g++ -o luogu luogu.cpp 中源文件 .cpp 放最后、-o 后面紧跟输出文件名（SCP2025 考过）。g++ -o luogu.cpp luogu 就把输出名和源文件搞反了。

常见变形

命令与路径可以串起来考（先 cd 再 mkdir 再到别处），把每一步的"当前位置"标出来再走一遍最稳。
命令的坑常伪装在"家目录/相对路径"里：把 ~、..、- 各自先翻译成具体路径，再合并。

使用条件与技巧

编译语言（C/C++）先编译成可执行文件，编译一次即可反复运行；解释语言（Python 等）由解释器逐句翻译执行，每次运行都要"翻译"一遍，但无需单独编译——问到"编译 vs 解释"先答这两句。

1.3 位、字节、字¶

讲解

1 字节 = 8 位（bit）；1KB = 2¹⁰ B = 1024 B；字长 = CPU 一次处理的位数（32 位/64 位）。

使用条件与技巧

注意 K/M/G 在初赛语境下默认按 2 的幂算（1KB = 1024B），与硬盘厂商的 1000 进制约定不同，看清题目假设。

1.4 进制转换（初赛高频）¶

讲解

二转八：3 位一组；二转十六：4 位一组（高位不足补 0）。
十六进制 A~F 对应 10~15，例如 \((1C)_{16}=1\times16+12=28\)。
十进制转其他进制：除基取余、倒序写。
k 进制数按位权展开：\((4321)_k=4k^3+3k^2+2k+1\)（SCP2025 考过）——最高位在最左，指数从右往左从 0 递增。

例题（CSP-J 2025 原题） \(720_{10}+270_{8}=388_{16}\)，判断是否成立。

- 解析

混合进制不能直接对位加，全部先转十进制，算完再转目标进制：

\(270_8=2\times64+7\times8+0=184\)，\(720+184=904\)；
\(388_{16}=3\times256+8\times16+8=768+128+8=904\)；
两边相等，成立。

使用条件与技巧

口算前先背熟 \(2^{10}=1024\)、\(0x10=16\)、\(0x100=256\)、\(0x400=1024\)。
二进制高位连续 1 的速算：\((1111)_2=15\)，\((11111111)_2=255\)。
见到"混合进制加减"一律转十进制，别试图在进制间直接借位/进位。

1.5 原码 / 反码 / 补码（重灾区）¶

讲解

正数：原码 = 反码 = 补码；负数补码 = 原码取反 + 1（符号位不变）。
\(n\) 位补码范围 \(-2^{n-1}\sim 2^{n-1}-1\)：32 位 int 约 \(\pm2.1\times10^9\)，无符号最大 \(2^{32}-1\approx4.3\times10^9\)。
\(-1\) 的 32 位补码 = 0xFFFFFFFF，按无符号解释就是 4294967295。
类型转换/溢出 = 按位重解释：
无符号值 \(\ge 2^{31}\) 强转 int 时，等于原值减 \(2^{32}\)；
无符号视角的和 \(\ge 2^{31}\) 时，按有符号重解释为负数（如 unsigned 2147483648 + 1234567890 按 int 输出为 \(-912915758\)）。

例题（SCP2025 原题）写出 \(-17\) 的原码、\(22\) 的补码、\(-13\) 的反码。

- 解析

流程固定：先写绝对值的二进制 → 按需取反（反码）/ 取反加一（补码）→ 补符号位。

\(-17\) 原码：\(|{-17}|=17=(00010001)_2\)，最高位补符号位 1 → 10010001；
\(22\) 补码：正数补码 = 原码 → 00010110；
\(-13\) 反码：\(13=(00001101)_2\) 按位取反 → 11110010。

易错辨析

有符号与无符号混合运算时，有符号会自动转成无符号（不是反过来），这是编译期常见坑。
看到"输出 int(x) 的值"先想"\(\ge 2^{31}\) 就减 \(2^{32}\)"，别直接按十进制重算。

常见变形

溢出题：两正数相加变负数（和超过 \(2^{31}-1\)）、x * 2 变负等，本质都是"结果按有符号重新解释"。
把负数当无符号输出：\(-1\) → 4294967295，问的就是补码 0xFFFFFFFF 的无符号读法。

使用条件与技巧

只有负数才需要"取反加一"，正数三码相同——先判符号再动手。
手算范围题背两条边界：int 最大 \(2^{31}-1=2147483647\)，unsigned 最大 \(2^{32}-1=4294967295\)。

1.6 ASCII¶

讲解

三个锚点：'A'=65、'a'=97、'0'=48；大小写差 'a'-'A'=32。
数字字符转数字：c - '0'。

常见变形

'0' ^ 1 == '1'：异或 1 恰好翻转字符 0/1（SCP2026 阅读程序考过）——看到字符与 1 异或，先想到"0↔1 翻转"。
大小写转换：c ^ 32 或 c ± 32 翻转大小写（由 65 与 97 差 32 推出）。

使用条件与技巧

背 65/97/48 三个锚点，其余字符用偏移口算，别硬背整张表。

1.7 网络与 CCF 常识¶

讲解

了解 IP 地址、域名、HTTP/HTTPS 等基本概念即可（偶尔一题）。
CSP-J/S 由 CCF 主办，分第一轮（初赛，闭卷）与第二轮（复赛）。

易错辨析

初赛禁止使用任何电子设备与外部资料，更不可能允许用 LLM 做题——任何"初赛可以查资料/开卷"的说法都是错的。

2. C++ 语言（语法细节是区分度来源）¶

2.1 基本类型大小（64 位平台）¶

讲解

类型	字节	范围速记
`char`	1	-128 ~ 127
`bool`	1	true / false
`short`	2	约 ±3.3 万
`int`	4	约 ±2.1×10⁹
`long long`	8	约 ±9.2×10¹⁸
`float`	4	有效数字约 7 位
`double`	8	有效数字约 15~16 位
指针	8	64 位下

易错辨析

标准只保证 1 == sizeof(char) ≤ sizeof(short) ≤ ... ≤ sizeof(long long)，不保证具体值；Windows 下 long 是 4 字节，Linux 下是 8 字节——考场上按题目声明的平台来。
sizeof(a)/sizeof(a[0]) 求数组长度；但 sizeof(指针) 永远是 8（64 位下），不是数组长度——把数组"传参"后再 sizeof 是经典错法。

2.2 溢出与类型提升¶

讲解

int 相乘可能溢出，习惯写 1ll * a * b。
1 << n：\(n\ge31\) 时是未定义行为；计算 \(2^k\) 用 1ll << k。
混合运算中 int + unsigned 结果是无符号（见 1.5 易错辨析）。

易错辨析

删掉 1ll* 可能因 int 溢出悄悄改变结果——判断题里"删掉这行输出会不会变"，先查有没有可能超过 \(2^{31}\)。

常见变形

取模防溢出：(a+b)%m 前若 \(a,b\) 可能接近 \(m\) 先用 1ll 抬升再模；这类空在完善程序里出现时，答案几乎都是"加 1ll/换 long long"。

2.3 位运算（初赛最爱）¶

讲解

操作	含义	典型用途
`x & (x-1)`	消掉最低位的 1	判断 2 的幂；配合循环数 1 的个数
`x & 1`	取最低位	判断奇偶
`x >> k & 1`	取第 k 位	状态压缩
`x ^ 1`	翻转最低位	0/1 状态切换
`x << k` / `x >> k`	乘 / 除以 \(2^k\)	快速缩放（非负整数）

逻辑运算短路：a && b 中 a 为假则不算 b；a || b 中 a 为真则不算 b。可用来避免除零、越界。

例题（CSP-J 2025 原题） int x=255; cout << (x & (x-1)); 输出多少？

- 解析

255 = 0b11111111，x & (x-1) 的作用是消掉最低位的 1：0b11111111 & 0b11111110 = 0b11111110 = 254。输出 254。

易错辨析

x & (x-1) 消的是最低位的 1，不是最高位、也不是最低位本身——从低位往高位数。
判断 2 的幂的条件是 (x & (x-1)) == 0 && x > 0，别漏掉 x=0（0 不是 2 的幂）。

常见变形

数 1 的个数：while(x){ cnt++; x &= x-1; } 循环次数 = 二进制中 1 的个数。
状态压缩遍历子集、x ^ 1 做 0/1 开关切换，都是同一套位运算换壳。

使用条件与技巧

逻辑短路可用于防越界/防除零：i < n && a[i] > 0、b != 0 && a/b > 0——前面为假就不会执行后面的危险操作。判断题问"会不会越界/除零"先看短路顺序。

2.4 switch 的穿透（fall-through，SCP2025 考过）¶

讲解

switch(x) {
    case 1: { cout << "A"; break; }   // x=1  → 输出 A
    case 3: { cout << "C"; }          // x=3  → 输出 C，无 break 继续向下
    default: { cout << "Q"; }         //       → 输出 Q
    case 5: { cout << "E"; }          //       → 输出 E
}

例题（SCP2025 考过）上例中 x=3、x=2、x=5 分别输出什么？

- 解析

执行流从命中的 case 一路向下，直到遇到 break 或 switch 结束：

x=3 命中 case 3，无 break → 走 default 输出 Q → 继续走 case 5 输出 E，共 CQE；
x=2 无匹配 case → 从 default 进入，输出 QE（default 位置不特殊，也会穿透）；
x=5 命中 case 5 → 输出 E 后 switch 结束。

易错辨析

漏写 break 是最常见的 bug，阅读程序专门考"x 取哪些值、输出什么"。
default 不一定在最后：它只是一个入口，命中后同样向下穿透到 break 或结尾。
建议：从命中的 case 起，画一条执行流往下走，直到 break 或 }，别只看一个 case。

2.5 引用与指针（坑点之王）¶

讲解

int A = 1, B = 1;
int& a = A, b = B;   // 只有 a 是引用！b 是普通 int
a = 2, b = 2;
cout << A << ' ' << B;   // 输出 2 1

例题（CSP-J 2025 考过）上例最终输出什么？若把函数参数改成传引用，实参会不会被修改？

- 解析

int& a = A, b = B; 中修饰符只作用于第一个变量：a 绑定 A，b 是独立的普通 int。于是 a=2 改 A、b=2 只改 b 自己 → 输出 2 1。
传引用参数会改实参，传值不会——阅读程序见到"函数参数带 &"，实参在调用后可能被改写，逐参数盯。

易错辨析

修饰符只作用于声明的第一个变量：int& a, b; 只有 a 是引用；int* p, q; 只有 p 是指针。分开声明最安全。
& 在声明里是引用、在表达式里是取地址——先分清语境再判断。

使用条件与技巧

判断"调用后谁变了"：画出形参 ↔ 实参的绑定关系，引用=同一个人两个名字，传值=复制一份。
数组作参数退化为指针：函数内 sizeof(a) 是 8，不是数组长度（呼应 2.1）。

2.6 递归¶

讲解 - 三要素：递归边界 + 递归式 + 规模减小。没有边界或边界写错会无限递归/栈溢出。

易错辨析

递推是自底向上（从边界往上算），递归是自顶向下（从问题往下拆）——判断题里"递归=自底向上"是错的。
阅读程序里递归函数别硬展开：先看边界条件返回值，再顺着调用链往回推一层两层。

2.7 string 与字符数组¶

讲解 - string 支持 + 拼接（string+string、string+char 均可），有 length()/size()、substr(pos,len)（越界自动截到末尾）。 - 字符数组以 '\0' 结尾。

易错辨析

strlen 不含 '\0'，sizeof 包含——char s[10]="abc" 的 strlen 是 3，sizeof(s) 是 10。
string 与字符数组混用别用错函数：strlen 只接 char*，string 用 .size()。

2.8 STL 入门¶

讲解 - 栈：push/pop/top/empty（LIFO）；队列：push/pop/front/back/empty（FIFO）。 - vector、sort、min/max/swap。

易错辨析

空栈上调用 top()/pop() 是未定义行为，必须由调用方保证非空——阅读程序判断题爱在"栈空时操作"上做文章。

3. 数据结构¶

3.1 栈与队列¶

讲解 - 栈应用：括号匹配、后缀表达式求值、函数调用、DFS；队列应用：BFS、逐层处理。 - 双栈模拟队列：入队压入 s1；出队时若 s2 空，把 s1 全部倒入 s2（顺序翻转），再从 s2 弹出。每个元素最多进出栈两次，均摊 O(1)（SCP2026 考过输出序列）。

例题（SCP2025 考过） 1~n 依次入栈（可穿插出栈），若第一个出栈的是 \(x\)，第二个出栈的可能值有哪些？例如第一个出 8，第二个可能是 1 吗？

- 解析

第二个出栈的只能是 \(x\) 上方已入栈的元素（\(x+1,\dots,n\)，尚未入栈的部分）或 \(x\) 下方紧邻的元素 \(x-1\)——绝不可能是被压在深处的元素。

反例：1~8 依次入栈、8 第一个出。8 出栈前 1~7 全都已压在栈里（8 是最后入的），想出 1 得先依次出 2~7，所以第二个出栈只能是 7，不可能是 1。
判断"出栈序列是否合法"，用栈现场模拟一遍最稳，别空想。

常见变形

后缀表达式求值、括号匹配问"栈最深时的高度/栈底元素"——模拟时顺手记录栈 size 最大值。
双栈模拟队列与"火车进站"类题本质同一模型：合法出栈序列计数（卡特兰数，见 Senior 篇 8.2）。

使用条件与技巧

LIFO/FIFO 判定先问：后进来的先出去（栈）还是先进先出（队列）？函数调用/DFS 用栈，BFS/逐层用队列。

3.2 二叉树（初赛必考、考点密集）¶

讲解 - 完全二叉树 \(n\) 个节点，叶子数 = \(\lceil n/2 \rceil\)（CSP-J 2025：1000 节点 → 500 叶）。 - 完全二叉树数组存储：编号 \(i\) 的左孩子 \(2i\)、右孩子 \(2i+1\)、父亲 \(\lfloor i/2 \rfloor\)。 - 深度 \(h\) 的满二叉树共 \(2^{h+1}-1\) 个节点（根为第 0 层）。 - 三种遍历：前序（根左右）、中序（左根右）、后序（左右根）。 - 唯一性：中序+前序 → 唯一；中序+后序 → 唯一；前序+后序 → 不唯一。

例题（SCP2025 原题）已知某二叉树中序为 CGEADBF、后序为 GECDFBA，求前序遍历。

- 解析

重建方法每步只做一件事："后序最后一个（或前序第一个）是根 → 到中序里找到根 → 左边左子树、右边右子树 → 递归"：

后序末尾 A 是根；中序中 A 左边 CGE 是左子树中序、右边 DBF 是右子树中序；
左子树的后序为 GEC（从原后序中取属于左子树的字符，保持相对顺序），末尾 C 是左子树根；中序 CGE 中 C 左边为空、右边 GE，再看左子树后序 GE 的根为 E、G 是 E 的左孩子 → 左子树前序 CEG；
右子树的后序为 DFB，根 B；中序 DBF 中 D 在左、F 在右 → 右子树前序 BDF；
整体前序（根左右）：A + CEG + BDF = ACEGDBF。

易错辨析

只有"前序+后序"推不出唯一树——两个序列都只能定根、定不了左右子树的边界，判断题常考。
重建时左右子树的分界必须靠中序（它在根两侧天然切分），前序/后序只用来找根。
完全二叉树公式记牢：叶子数 \(\lceil n/2 \rceil\) 是对完全二叉树说的，满二叉树叶子数固定 \(2^h\)。

常见变形

给出"后序 + 升序"推树：升序=中序（BST 性质，见 3.4），回到"中序+后序"模型。
层序/前序变体、统计不同二叉树形态数（卡特兰数）、表达式树转中缀/后缀，都建立在"三种遍历 + 根定位"之上。

使用条件与技巧

手算模板：先写"后序末尾=根"，再找中序切分，每次只在当前子树区间内做，别跨区间取字符。

3.3 哈夫曼树与编码¶

讲解 - 构造：每次合并权值最小的两棵，新节点权值为两者之和。 - WPL（带权路径长度）= 所有叶子权值 × 深度之和 = 编码总长度。 - 哈夫曼编码是前缀码（任一编码不是另一编码的前缀）、变长，越常用的字符编码越短。 - 编码"种类数"：内部节点左右子树可互换 → \(2^{\text{内部节点数}}\) 种（如 6 个字符、5 个内部节点 → 32 种，SCP2026 考过）。

例题（CSP-J 2025 原题）权值分别为 10, 12, 15, 20, 25，构造哈夫曼树，求 WPL。

- 解析

每次取最小的两棵合并，新节点重新参与比较：

10+12=22 → {15,20,22,25}；
15+20=35 → {22,25,35}；
22+25=47 → {35,47}；
35+47=82（根）。

WPL = 各次合并权值之和 = 22+35+47+82 = 186（等价于叶子权值×深度求和）。

易错辨析

WPL 是"加权路径长度之和"，不是叶子个数、也不是树高。合并到只剩一棵树时，叶子总在下方。
"编码种类数"数的是内部节点（叶子交换没意义），\(2^{\text{内部节点数}}\) 别忘了指数是谁。

常见变形

问"编码总长度/平均码长"：平均码长 = WPL ÷ 字符总频数。
问"某字符编码长度"：先数它在哈夫曼树里的深度。
哈夫曼树的形态不唯一（相同权值不同合并顺序），但 WPL 唯一——考数值题给的是确定答案。

使用条件与技巧

手算 WPL 的最快方法：把所有中间合并值加起来（等价于加权深度和），比逐叶乘深度更快且不易错。

3.4 二叉搜索树 BST¶

讲解 - 性质：中序遍历 = 升序序列。 - 理想情况增删查 O(log n)，退化成链时 O(n)。

常见变形

由"后序 + 升序（=中序）"可还原唯一树并推出前序（CSP-S 2025 考过类似，J 组了解即可）——把 BST 的"升序中序"当已知条件用。

使用条件与技巧

见 BST 先想"中序=有序"这一条性质；判断题说 BST 任意子树也满足该性质（递归定义）。

3.5 图（J 组只考概念）¶

讲解 - 度数：无向图所有顶点度数和 = 2×边数；有向图入度和 = 出度和 = 边数（CSP-J 2025 单选）。 - 存储：邻接矩阵（\(O(n^2)\) 空间，判边 O(1)）vs 邻接表（\(O(n+m)\) 空间，遍历邻居快）。稀疏图用邻接表。 - 连通块：并查集或 BFS/DFS 数。

易错辨析

邻接矩阵求度数：数该行/列中 1 的个数即可（无向图对称，数一行即可；SCP2025 考过）。别去数全矩阵再除 2 绕弯。
邻接表每条边两端都出现只是"可能是无向图"的必要条件，不是充分条件——判断题别把"可能"说成"一定"。

使用条件与技巧

度数公式两类题通用：给了度数问边数（\(m=\sum deg/2\)），或给了边数反推度数。
"遍历所有顶点至少几条边连通"之类最值题，先想树（\(n-1\) 条边连通）。

4. 算法¶

4.1 枚举与模拟¶

讲解 - 枚举是最朴素的算法，先想"暴力能不能过"，再考虑优化。 - 模拟题务必读清操作顺序、边界条件（"第 1 轮 vs 第 0 轮"这类坑）。

易错辨析

模拟题丢分多在边界轮次与操作顺序：先把样例在草稿上按题意走一遍，确认"先判后改"还是"先改后判"。

4.2 排序¶

讲解 - 选择排序不稳定；快排最坏 O(n²)、平均 O(n log n)；归并稳定；计数排序 O(n+k) 适用于值域小。

例题（CSP-J 2025 原题）对 {6,1,5,2,4} 冒泡升序排序，共需要多少次交换？

- 解析

冒泡排序交换次数 = 逆序对数。逐轮看：第一轮 6 一路与 1、5、2、4 交换 4 次沉到底；第二轮 5 与 2、4 交换 2 次；第三轮后有序。共 4+2=6 次。速算法：对每个元素数"它后面有几个比它小"再求和 → 6 后面有 4 个、5 后面有 2 个 → 4+2=6。

常见变形

归并排序求逆序对（合并时右半元素前插几次就是几个逆序）、树状数组求逆序对——理解"交换次数=逆序对数"即可套。
稳定性判断题：选择/快排不稳定，归并/冒泡/插入/计数稳定，背结论。

使用条件与技巧

快排三件套（SCP2025 考过）：快排是分治 + 基于交换的排序；平均 \(O(n\log n)\)，最坏 \(O(n^2)\)（如原本有序、每次划分失衡）。
sort 是 STL 的排序函数，实现结合了快排 + 堆排 + 插入排序（内省排序），最坏也能做到 \(O(n\log n)\)。

4.3 二分（含二分答案）¶

讲解 - 二分答案三步：① 写判定函数 check(x)；② 二分枚举答案；③ 找"满足条件的最小/最大 x"。 - 模板要点：mid = l + (r-l)/2（防溢出）；while (l < r)；check(mid) 为真则 r = mid，否则 l = mid + 1（求最小可行值）。 - 若是"求最大可行值"，要用上取整 mid = (l+r+1)/2 且 l = mid，否则死循环。

例题（SCP2025 考过） 100 个元素的有序表二分查找，问"恰好 5 次找到"的元素有多少个？

- 解析

第 1 次命中中点；之后每轮把区间对半，能"恰好第 \(k\) 次命中"的位置是第 \(k-1\) 轮划分出的新区间中点，共 \(2^{k-1}\) 个。所以恰好 5 次找到的有 \(2^4=16\) 个。

易错辨析

(l+r)/2 在 \(l,r\) 接近 \(2^{31}\) 时会溢出，务必写 l + (r-l)/2。
二分答案右边界取值域上界（如 \(2\times10^9\)），别取成 \(n\) 或数组末元素（除非已排序）。
求最大值用 (l+r+1)/2 + l = mid：取整方向反了会在相邻两数间死循环。

常见变形

"第 k 小/统计不超过 x 的个数/最小化最大值"几乎都是二分答案换壳（SCP2026 第 k 小完善程序题）。
浮点二分问"精度到 \(10^{-k}\)"，循环改成 while (r-l > eps) 或直接二分 100 次。

4.4 贪心¶

讲解 - 贪心只在"局部最优 = 全局最优"时正确，需要验证或证明。 - 正确贪心例：活动安排（按结束时间排序）、哈夫曼、区间选点。

例题（SCP2026 考过） LIS（最长上升子序列）能否贪心？对 {3,1,2}，"每次取比上一个大且最小的数"能得到多长？

- 解析

不能贪心。若从 3 开始找比它大的最小数，序列只有 3（长度 1）；但真正的 LIS 是 {1,2}（长度 2）——第一步"取 3"就选错了。LIS 需要记录"以每个位置结尾"的最优值（DP），局部最优策略在这里失效。

易错辨析

看到"每次都取最……"先怀疑：贪心需要交换论证或反证支撑，DP/搜索题硬套贪心必错。
判断题"贪心一定能得到全局最优"缺前提，恒为假。

常见变形

活动安排（按结束时间最早排序）、区间覆盖/选点（按右端点排序）、哈夫曼（每次最小两棵）、找零钱（面额成倍数关系时贪心才成立）——记清每类排序依据。

使用条件与技巧

贪心失效时立刻退到 DP 或搜索；验证小反例（如上例 3 个元素）是最快的排除手段。

4.5 搜索 DFS / BFS¶

讲解 - DFS：递归 + 回溯，注意剪枝；BFS：队列，边权为 1 时第一次到达即最短路。 - 状态设计：把"位置 + 已用次数"等作为状态（如 dis[x][y][k]，SCP2026 迷宫传送题：步行 1 步 + 传送 1 步，三维 BFS）。 - 连通块、迷宫可达性：DFS/BFS 均可（Flood Fill）。

常见变形

BFS 最短路计数：第一次入队即最短，同时记录方案数（去重小心）。
状态维度扩展：不止二维坐标，把"已用道具/方向/剩余步数"加进状态，维度+1。

使用条件与技巧

判 BFS/DFS：求"最短步数"且边权相同 → BFS；只问"是否可达/连通块大小" → 随便，DFS 写起来短。
递归深度大（如 \(10^6\)）时 DFS 可能爆栈，优先 BFS 或迭代。

4.6 动态规划（J 组考得不深但必考）¶

讲解 | 类型 | 状态定义 | 转移要点 | |:-----|:---------|:---------| | LIS | dp[i] 以 \(a_i\) 结尾 | dp[i] = max(dp[j])+1（\(a_j<a_i\)），O(n²) | | LCS | dp[i][j] | 字符相等 dp[i-1][j-1]+1，否则取 max | | 0-1 背包 | dp[j] 容量 j | 容量倒序枚举 | | 路径计数 | dp[i][j] | dp[i][j] = dp[i-1][j] + dp[i][j-1] |

例题（CSP-J 2025 原题） 8×8 棋盘从 (1,1) 到 (4,5)，只能向下/向右走，共多少种走法？

- 解析

需走 3 下 + 4 右共 7 步，选 3 步向下（其余向右）即确定整条路径：\(C(7,3)=\frac{7!}{3!4!}=35\)。路径计数本质是组合数。

易错辨析

0-1 背包容量倒序枚举（倒序=每件只能取一次）；完全背包正序（可重复取）——阅读程序考背包常在此处埋坑。
边界（dp[0]）要单独初始化，别让转移读到垃圾值。

使用条件与技巧

DP 口决：先想清楚"状态是什么、从哪几个方向转移来"，再写循环；转移来自"上一步的所有可能"而非"这一步的所有选择"。

4.7 前缀和 / 差分（大纲 2025 新增考点）¶

讲解 - 前缀和：预处理后 O(1) 求区间和。 - 差分：O(1) 区间加，最后求前缀还原原数组。

常见变形

二维前缀和（容斥式：\(s_{ij}=s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}+a_{ij}\)），区间查询同样容斥。
差分配合"多次区间加，最后统一查询"是完美搭配——差分数组边界的 +1/-1 在 r+1 处别写错位置。

4.8 数论入门¶

讲解 - 素数判定试除法：只需试到 \(\sqrt n\)，条件写 i <= n/i（避免 i*i 溢出）；1 不是素数，isPrime(1) 必须返回 false（SCP2026 考了此 bug 的后果）。 - 辗转相除法：gcd(a,b) = gcd(b, a%b)。 - 埃氏筛 / 线性筛：快速筛素数。 - 欧拉筛（线性筛）：每个合数被最小质因子筛到恰好一次，\(O(n)\)。常配合数组记录"最小质因子"（SCP2025 阅读程序考过：comp_by[x*prime] = prime，且 x % prime == 0 时 break）。 - C++ 取模：-7 % 3 == -1（结果的符号与被除数一致），别想当然。

易错辨析

isPrime(1) 忘了特判 → 1 被当素数，判断题"对 1 调用会返回 true"要一眼看出。
欧拉筛的 break 条件 x % prime == 0 是正确性关键：不 break 会被更大的质因子重复筛到，退化成埃氏筛。

常见变形

试除写法三兄弟：i*i<=n（可能溢出）、i<=sqrt(n)（浮点误差）、i<=n/i（推荐）——判断题爱问哪个写法安全。
负号取模：(-7)%3==-1、7%(-3)==1，符号跟被除数走。

4.9 摩尔投票（2025 刚考过，别忽略）¶

讲解 - 用于找出现次数 > n/2 的"众数"：计数抵消法——候选者 count 增/减，count==0 换候选。

例题（CSP-J 2025 完善程序第 2 题）以"精明与糊涂"指认问题为背景，考了摩尔投票的变体。

- 解析

思路仍是计数抵消：维护一个候选与计数器，遇相同候选 +1、不同 -1，计数器归零就换候选。由于众数出现超过一半，抵消后剩下的候选必是它。（具体代码骨架见当年完善程序原题。）

易错辨析

摩尔投票只保证"若存在 > n/2 的元素，最终候选是它"——不保证一定存在，最后需再扫一遍验证计数 > n/2。
找的是严格超过一半，不是"出现最多"；恰好一半不满足条件。

常见变形

扩展到"出现次数 > n/3 的元素最多两个"：维护两个候选，双计数抵消。
完善程序里它常被包装成"多数决/指认"类故事，识别标志是 cnt==0 换人的 if 结构。

4.10 倍增（binary lifting，J 组大纲考点）¶

讲解 - 思想：预处理"跳 \(2^k\) 步到哪"（up[i][k]），询问时按 \(k\) 的二进制位逐位跳。 - 递推：up[i][k] = up[ up[i][k-1] ][k-1]；跳 \(k\) 步用 (k >> j) & 1 判断第 \(j\) 位是否要跳（SCP2025 完善程序考过"从 x 跳 k 次后的位置"）。 - 同构应用：LCA 的倍增、ST 表、快速幂。

易错辨析

up[i][k] 是"跳 \(2^k\) 步"，不是"跳 k 步"——递推式下标对应的是指数。
跳 k 步前先把 k 按二进制拆位，从低位到高位逐位试；超过表长的高位跳不到就留在原地（或按题意处理）。

常见变形

快速幂（指数二进制拆分）与倍增同构：while(k){ if(k&1) res*=a; a*=a; k>>=1; }。
ST 表查询区间最值 = 两个 \(2^k\) 段覆盖，预处理表同款递推。

使用条件与技巧

识别标志："从位置 x 出发操作 k 次（k 可达 \(10^9\)）后到哪/状态如何" → 先预处理倍增表再逐位跳。

5. 数学（初赛分值占比高）¶

5.1 排列组合¶

讲解 - 加法原理（分类）、乘法原理（分步）。 - 组合数 \(C(n,k)\)、杨辉三角即组合数表。 - 与顺序有关用 P（排列），与顺序无关用 C（组合）。

例题 1（SCP2026 考过）把 {1,2,3,4,5,6} 排成一排，要求奇数 {1,3,5} 与偶数 {2,4,6} 各自保持相对顺序不变，有多少种排法？

- 解析

相对顺序固定的元素视作"相同元素"，用组合数选位置：6 个位置里先给 3 个奇数占位 \(C(6,3)=20\)（选定位置后奇数内部顺序已定），剩下 3 个位置放偶数，共 \(C(6,3)=20\)。

例题 2（CSP-J 2025 原题） 5 男 4 女中选 4 人，要求男女都有，有多少种选法？

- 解析

"至少有一个"用补集：总数 − 不满足的 = \(C(9,4)-C(5,4)-C(4,4)=126-5-1=120\)（减掉全男与全女两种极端）。

易错辨析

排列和组合别混：与顺序有关用 P，与顺序无关用 C。分组后乘以组内排列就是"先分组再排列"。
"至少有一个"直接分类易漏，先总数后补集最不易错；顺序固定类题目别用排列硬算。

常见变形

带限制的选人（先分类再计数）：如"5 名教师、6 名学生选 5 人，至少 1 名教师且至少 2 名学生，且甲、乙不能同时入选"（SCP2025-S 考过，答案是 345）：先按"教师数"分类（1 师 4 生、2 师 3 生、3 师 2 生），每类用组合数相乘，再减去"甲、乙同时入选"的违规方案。分类讨论是这类题的通法。
圆排列、插空法、捆绑法在 S 组更常见（见 Senior 篇 8.2）。

5.2 容斥原理¶

讲解 - 两集合：\(|A\cup B|=|A|+|B|-|A\cap B|\)。 - 三集合：\(|A\cup B\cup C|=\sum|A_i|-\sum|A_i\cap A_j|+|A\cap B\cap C|\)（加奇减偶）。 - 整除计数：\(1\sim n\) 中 \(k\) 的倍数有 \(\lfloor n/k \rfloor\) 个。

例题（SCP2026 考过） 1~200 中能被 3 或 5 整除、但不能被 7 整除的数有多少个？

- 解析

先算 \(|A\cup B|\)（A=3 的倍数、B=5 的倍数）：\(\lfloor200/3\rfloor+\lfloor200/5\rfloor-\lfloor200/15\rfloor=66+40-13=93\)；
再减去其中被 7 整除的部分——注意要在 \(A\cup B\) 内部做容斥：\(|(A\cup B)\cap C|=|A\cap C|+|B\cap C|-|A\cap B\cap C|=\lfloor200/21\rfloor+\lfloor200/35\rfloor-\lfloor200/105\rfloor=9+5-1=13\)；
答案 \(93-13=80\)。

易错辨析

减"且不能被 7 整除"时，别直接 \(\lfloor 200/7\rfloor=28\) 去减——那会把不满足"被 3 或 5 整除"的数也误删。要在 \(A\cup B\) 范围内做三层容斥。
"加奇减偶"的顺序：奇数个集合相交的部分加，偶数个的部分减。

常见变形

"1~1000 中不被 2、3、5 整除"= 总数 − 三层容斥（Senior 篇 8.2 有完整式）。
二维前缀和的矩形部分和、错排计数也暗含容斥思想。

5.3 取整与模¶

讲解 - floor 向下、ceil 向上、C++ 整除向零取整（负数时与 floor 不同）。

易错辨析

-7/3：C++ 向零取整得 \(-2\)，而数学 floor 得 \(-3\)——负数除法别再按"向下取整"想。
判断是 floor 还是 ceil 的题，代一个负小数值进去试最稳。

5.4 斐波那契与周期¶

讲解 - 斐波那契数列取模后一定存在循环节（皮萨诺周期）。

例题（CSP-J 2025 原题） \(f_0=f_1=1,\ f_n=(f_{n-1}+f_{n-2})\bmod 7\)，求 \(f_{2025}\)。

- 解析

取模后数列周期为 16，\(2025\bmod 16=9\)，\(f_9=6\)。验证前几项：\(f_2=2,f_3=3,f_4=5,f_5=1,f_6=6,f_7=0,f_8=6,f_9=6\)。

易错辨析

下标从 \(f_0\) 还是 \(f_1\) 开始、初值是不是 1，会整体平移周期与结果——先确认定义再取模。
找周期要列到出现 (初值对) 重现为止，别列两三项就下结论。

使用条件与技巧

见到"大下标 + 取模"，第一反应就是"找循环节"：现场快速列出前 1~2 个周期即可，不需要背周期表（Mod 7 是 16 可以记一下）。

5.5 概率初步（几何概型偶尔考）¶

讲解 - 概率题先想"总体空间"与"有利空间"各占多大，再求比值，别硬背结论。

例题（SCP2025 考过）一根木棍随机折两刀成三段，能构成三角形的概率是多少？

- 解析

能构成三角形等价于"每段都小于总长的一半"。设两刀位置为 \((x,y)\)，总空间是单位正方形；三段都小于一半对应三个小三角区域，几何概型中有利区域占总体区域的 \(1/4\)。

常见变形

几何概型（面积比）、等可能事件计数（古典概型 \(P=k/n\)）两类别混：能数清的就数，数不清的画区域比面积。

6. 阅读程序与完善程序应试技巧¶

阅读程序（40 分，拿分大头）¶

先读 main 和变量声明，再读函数，判断程序"整体在做什么"（排序？DP？搜索？模拟？）。
判断题：用边界值 / 特殊值（0、1、n、全相同）代入验证，别硬推大输入。
单选题"输出是什么"：手算小样例，算完对照选项。
多选题（通常最后一小问，4 分）：逐项分析，用排除法。
高频考法："修改某行后输出是否变化"——重点盯循环边界（i<n vs i<=n）、比较符号（< vs <=）、初始值。
模拟卷常把"算法题伪装成代码"：欧拉筛（线性筛）、倍增、计数 DP——先说出"这段代码在算什么"，再逐问作答（SCP2025 三篇阅读分别是位运算统计、计数 DP、欧拉筛）。

易错辨析

注意函数写得不严谨的副作用：isPrime(1)、空栈 top()、数组越界这类"语义错误"。
1e9 这种"不可达"大值：只有当所有路径代价都小于它时，换更大的值输出才不变。

完善程序（30 分）¶

先通读全程序确定算法框架（枚举 / 二分 / BFS / DP / 贪心）。
填每个空时结合上下文：变量命名、注释、循环范围、数组大小。
重点检查：循环边界、比较符号、下标偏移（i-1/i+1）、是否 +1、取模、数据类型。

经验

完善程序大多数空靠语义就能直接推出：比如"统计不超过 x 的个数"就是 a[i] <= x，返回是否满足就是 k <= c（SCP2026 第 k 小二分题）。把 5 个空当成一个整体来读，不要孤立猜。

7. 考前速查：J 组高频考点清单¶

考点	怎么考	记忆要点
补码/溢出	无符号转有符号、两正数相加变负	\(\ge2^{31}\) 减 \(2^{32}\)；符号位
进制转换	互转、混合运算	统一十进制再算；3/4 位分组
位运算	`x&(x-1)`、`x^1`、取第 k 位	消最低位 1；翻转
二叉树	叶子数、遍历、重建	\(\lceil n/2\rceil\)；中序+前/后序→唯一
哈夫曼	WPL、编码种类	权×深度之和；\(2^k\) 种（k=内部节点数）
冒泡	交换次数 = 逆序对数	数"后面几个更小"
组合计数	至少型、顺序固定	补集、组合数选位置
容斥	两/三集合	加奇减偶；整除用 \(\lfloor n/k\rfloor\)
斐波那契周期	大下标取模	找循环节
栈/队列	双栈模拟队列、后缀表达式	LIFO/FIFO；倒栈
二分答案	完善程序高频	`l+(r-l)/2`；`r=mid` / `l=mid+1`
二分次数	恰好 k 次找到	\(2^{k-1}\) 个
欧拉筛	最小质因子数组	每个合数筛一次；`x%p==0` 停
倍增	跳 k 步到哪	`up[i][k]=up[up[i][k-1]][k-1]`
g++ / 编译	`-o` 用法、编译 vs 解释	源文件放最后；编译一次可反复运行
switch	穿透输出	无 break 一路向下
出栈序列	第二个出栈可能值	LIFO；被压住的出不了
概率	木棍折三段成三角形	\(1/4\) 几何概型
阅读程序	修改后输出变不变	盯边界与比较符号
摩尔投票	找众数变体	计数抵消

8. 经验之谈¶

初赛考的是"范围广、深度浅"：把大纲里每一项都过一遍，不要只盯复赛算法（复赛不考的进制、二叉树、哈夫曼恰恰是初赛送分题）。
手算能力是核心竞争力：进制、二叉树遍历、哈夫曼 WPL、排列组合、容斥必须能手算，且要算得快。
错题本记"为什么想错"：比如把"顺序固定"想成排列、把补码按原码算——比记正确答案更有用。
时间分配 + 先易后难：阅读程序是分数大头，别在单选最后一两题上耗死。
验证胜过记忆：二叉树公式、组合数、周期题，拿小数据现场算一遍最稳。
模拟赛偏难不必焦虑：SCP2026-J1 难度高于真实 CSP-J 初赛，用它练手时重点看"知识点覆盖"而非分数。
代码修改题是保分项：SCP2025 三篇阅读的判断题几乎全是"删某行/改某条件/改数据类型，输出变不变"——只需盯"会不会越界、会不会溢出、会不会少算/多算"三类问题。

CSP-J 第一轮通关指南 CSP-J R1 Passport¶

0. 考试结构先搞清楚¶

1. 计算机基础（初赛专属，复赛完全用不到）¶

1.1 计算机组成¶

1.2 操作系统与文件命令（Linux 为主）¶

1.3 位、字节、字¶

1.4 进制转换（初赛高频）¶

1.5 原码 / 反码 / 补码（重灾区）¶

1.6 ASCII¶

1.7 网络与 CCF 常识¶

2. C++ 语言（语法细节是区分度来源）¶

2.1 基本类型大小（64 位平台）¶

2.2 溢出与类型提升¶

2.3 位运算（初赛最爱）¶

2.4 switch 的穿透（fall-through，SCP2025 考过）¶

2.5 引用与指针（坑点之王）¶

2.6 递归¶

2.7 string 与字符数组¶

2.8 STL 入门¶

3. 数据结构¶

3.1 栈与队列¶

3.2 二叉树（初赛必考、考点密集）¶

3.3 哈夫曼树与编码¶

3.4 二叉搜索树 BST¶

3.5 图（J 组只考概念）¶

4. 算法¶

4.1 枚举与模拟¶

4.2 排序¶

4.3 二分（含二分答案）¶

4.4 贪心¶

4.5 搜索 DFS / BFS¶

4.6 动态规划（J 组考得不深但必考）¶

4.7 前缀和 / 差分（大纲 2025 新增考点）¶

4.8 数论入门¶

4.9 摩尔投票（2025 刚考过，别忽略）¶

4.10 倍增（binary lifting，J 组大纲考点）¶

5. 数学（初赛分值占比高）¶

5.1 排列组合¶

5.2 容斥原理¶

5.3 取整与模¶

5.4 斐波那契与周期¶

5.5 概率初步（几何概型偶尔考）¶

6. 阅读程序与完善程序应试技巧¶

阅读程序（40 分，拿分大头）¶

完善程序（30 分）¶

7. 考前速查：J 组高频考点清单¶

8. 经验之谈¶

参考链接¶