CSP-J 数学知识题单
按 CSP-J 常见数学、数论、计数、逻辑和位运算知识整理的训练题单。
CSP-J 数学知识题单
这份题单用于训练 CSP-J 中常见的数学思维。CSP-J 的数学通常不是难在高等数学，而是难在：
text
把题意翻译成数学关系。做题时不要只问“这题是什么算法”，更要问：
text
这个题的条件能不能变成一个谓词？
合法不好数，能不能数非法？
有没有必然成立的条件？
有没有冲突？
有没有单调性、周期性、奇偶性？
能不能用取整、余数、前缀和或差分表达？1. 整数基础
这是 CSP-J 最常用的数学基础，重点是整数运算、取整、边界和十进制拆位。
需要掌握：
- 奇偶性
- 正负数
- 绝对值
- 最大值、最小值
- 整除
- 约数、倍数
- 余数
- 向上取整、向下取整
常见代码形式：
cpp
x % 2
a % b
(a + b - 1) / b很多 T1/T2 都不是思路难，而是取整和边界写错。
- 训练点：把时刻统一转成分钟，再做整数减法。
- 训练点：向上取整，三种购买方案取最小值。
- 训练点：按整数段分组累加，处理最后一段不足天数。
- 训练点：整数拆位，处理符号和前导零。
- 训练点：枚举整数并逐位统计数字出现次数。
2. 模运算与周期
取模常用于循环、轮流操作、周期行为和环形数组。
需要掌握：
- 同余
- 周期
- 循环节
- 取模后的位置变化
- 下标从 0 开始还是从 1 开始
人脑模型：
text
超过一圈后，只关心余数。- 训练点：按权值求和后对 11 取模，得到校验码。
- 训练点：环形序列上的方向变化，用取模维护当前位置。
- 训练点：每层楼梯形成循环数组，用取模跳到目标楼梯。
- 训练点：把狗的行为看成周期，用取模判断落在哪一段。
- 训练点：循环移位、模运算和位置映射。
3. 最大公约数与最小公倍数
gcd/lcm 是 CSP-J 必须熟悉的基础数论工具。
需要掌握：
- gcd
- lcm
- 辗转相除法
- 互质
- 分数化简
公式：
cpp
gcd(a, b)
lcm(a, b) = a / gcd(a, b) * b- 训练点：把 gcd/lcm 条件转成互质因子计数。
- 训练点：枚举约数，再检查 gcd 和 lcm 条件。
- 训练点：把追及问题转成同余方程。
- 训练点：二元一次不定方程和整数解范围。
4. 质数与因数分解
CSP-J 层面通常不考很深的数论，但要能稳定写出质数判断、质因数分解和简单筛法。
需要掌握：
-
判断质数
-
质因数分解
-
约数个数
-
约数枚举
-
简单筛法
- 训练点：从小到大试除，找到质因数后输出另一半。
- 训练点：构造回文数，再判断质数。
- 训练点：筛法预处理素数。
- 训练点：把素数当成物品，用完全背包做计数。
- 训练点：字符串提取数字后做素数判断和质因数分解。
5. 代数变形
这几年 CSP-J 常把数学藏在题意里。关键不是背公式，而是把题目条件改写成可判断的等式或不等式。
需要会：
- 一元一次方程
- 二元关系
- 简单不等式
- 平方、开方
- 判别式思想
- 把题目条件转成公式
核心问题：
text
题目给出的条件，能不能化成一个整数解是否存在的问题？- 训练点：由条件推出二次方程，用判别式判断正整数解。
- 训练点：把乘积最大转成尽量平均分配。
- 训练点：确定螺旋层，再按边分段计算编号。
- 训练点：先判断总人数范围，再统计缺口和超额。
- 训练点：枚举并检查数字集合约束。
6. 计数基础
计数是 CSP-J 很重要的数学能力。很多题不是“模拟所有情况”，而是把合法条件转成一个可以直接计算的数量。
需要掌握：
- 加法原理
- 乘法原理
- 补集计数
- 简单排列组合
- 去重
- 分类讨论
典型人脑模型：
text
合法不好数，就数非法。
非法 = 条件 A 不满足 且 条件 B 不满足。
如果两个选择独立，就用乘法规则。- 训练点：逻辑谓词、补集、乘法规则。
- 训练点：在 BFS 最短路层次上累计方案数。
- 训练点：组合数递推和二维前缀和统计。
- 训练点：按余数做计数 DP，统计模意义下的方案数。
- 训练点：把最小值恰好等于 100 转成两个计数相减。
7. 逻辑与集合
很多 CSP-J 题看起来是模拟，其实是逻辑判断和集合约束。
需要会：
- 且
and - 或
or - 非
not - 必要条件
- 充分条件
- 反证法
- 冲突判断
- 集合补集
典型思考：
text
先确定必然成立的事情，再检查是否冲突。- 训练点：先确定黑色格子的必然条件，再检查白色冲突，灰色用贪心补齐。
- 训练点：枚举候选点，用逻辑条件统计矛盾陈述。
- 训练点：把合法 leader pair 归类成有限几种情况。
- 训练点：枚举骰子并判断循环胜负关系。
- 训练点：枚举密码，用差分模式判断能否由一次操作得到记录状态。
8. 坐标与几何基础
坐标题不一定是几何题。CSP-J 中更常见的是网格、行列、距离、方向和区域。
需要会：
- 平面坐标
- 行列坐标
- 曼哈顿距离
- 矩形面积
- 三角形面积基础
- 多边形简单性质
- 方向移动
常见代码：
cpp
dx, dy
abs(x1 - x2) + abs(y1 - y2)- 训练点：三点枚举，坐标轴对齐和面积公式。
- 训练点：坐标变换和分类讨论。
- 训练点：棋盘坐标、马控制点和网格路径。
- 训练点：螺旋矩阵中的层数和边界坐标。
- 训练点：网格时间约束和位置扩展。
9. 二进制与位运算
二进制越来越常见。它常把“选择、开关、集合、奇偶状态”压成整数。
需要会：
- 二进制表示
- 2 的幂
- 位与
& - 位或
| - 异或
^ - 左移
<< - 右移
>> - 状态压缩的基本含义
人脑模型：
text
一个二进制位表示一个开关 / 选择 / 状态。- 训练点：二进制末尾 0 的个数，理解连续除以 2。
- 训练点：按二进制位分解指数。
- 训练点：快速幂，把指数按二进制拆分。
- 训练点：异或前缀和与区间异或。
- 训练点：按二进制位构造，处理 popcount 和异或。
- 训练点：二进制前缀和贪心状态压缩。
10. 数列、前缀和、差分
前缀和和差分严格说偏算法，但它们背后是数学表达：把区间和、区间修改、相邻变化写成可维护的形式。
需要会：
- 等差数列求和
- 前缀和
- 差分
- 累加贡献
- 区间和
常见公式：
cpp
sum[l..r] = pre[r] - pre[l - 1]cpp
diff[i] = a[i] - a[i - 1]- 训练点：把操作次数转成相邻差分中的正增量。
- 训练点：坐标亮度合并后，用固定长度窗口求最大区间和。
- 训练点：用差分数组把区间加转成两次单点修改。
- 训练点：目标温度差分，两端补 0 后计数。
- 训练点：把操作影响转成二阶差分。
- 训练点：按行预处理代价，再枚举分界位置。
最终训练方法
优先级建议：
- 整数、取整、余数
- 逻辑条件、补集、分类讨论
- gcd、质数、约数倍数
- 代数变形、不等式
- 计数：加法原理、乘法原理、补集
- 坐标、网格、距离
- 二进制和异或
- 前缀和、差分、数列规律
每做完一道题，建议写一段复盘：
text
这题的数学对象是什么：
题目条件能否写成谓词：
有没有必然成立的条件：
有没有冲突：
合法不好数时，能不能数非法：
有没有取模、周期、奇偶性或单调性：
最终公式或判断条件是什么：这份题单的目标不是背数学知识点，而是训练把题面翻译成数学关系的能力。