courses/noip
NOIP/省选高阶 · 冲击省赛与省队
课程简介
面向具备 CSP-S 水平、目标 NOIP 省级奖项与省队选拔的选手。本课程不是"把算法名字过一遍"，而是每个专题都配可运行代码与真实运行结果，让选手看清"状态怎么设计、转移怎么写、坑在哪里"。
课程按 DP 进阶 → 图论进阶 → 数论组合 → 数据结构进阶 → 字符串 → 计算几何 → 省选专题 → 集训冲刺 八章推进。每个算法先讲透原理，再给完整可编译的代码与运行示例，最后用省选级题目检验。配套省选级题库、定期模拟与赛前集训，帮助选手在高手如云的竞争中稳步提升。
适合对象
- 高中在读为主，也欢迎具备 CSP-S 高水平的初中拔尖选手。
- 目标参加当年 NOIP，冲击省一、省队乃至 NOI 国赛。
- 渴望系统补齐高阶算法盲区、提升竞赛上限。
课程大纲
第1章 动态规划进阶：区间、树形、状态压缩
第2章 图论进阶：最短路、最小生成树、网络流
第3章 数论与组合数学
第4章 数据结构进阶：线段树、树状数组、平衡树
第5章 字符串算法：KMP、Trie、哈希
第6章 计算几何与思维杂题
第7章 省选专题与历年真题
第8章 集训与赛前冲刺课程内容
本课目录（点击跳转）
↑ 目录第 1 章 动态规划进阶：区间、树形、状态压缩
本章目标：在基础 DP（线性、背包、LIS）之上，掌握区间 DP、树形 DP、状压 DP 三类高频进阶模型，理解"状态设计决定算法上限"。
1.1 从"线性"到"区间"：dp 的下标不再是一个点
基础 DP 里状态往往是一个位置 i。进阶第一步，是让状态变成一个区间 [i, j]：dp[i][j] 表示"处理完 i 到 j 这段"的答案。经典题是合并石子——每次合并相邻两堆，代价是两堆之和，求把 n 堆合成一堆的最小总代价。
关键洞察：最后一步一定是"把左右两大块合成一堆"，所以枚举分界点 k，把问题拆成 dp[i][k] 与 dp[k+1][j] 两个子问题。先求短的区间，再拼长的区间：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n + 1), sum(n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i]; // 前缀和，O(1) 求一段的代价
}
vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
for (int len = 2; len <= n; len++) { // 先枚举区间长度
for (int i = 1; i + len - 1 <= n; i++) { // 再枚举起点
int j = i + len - 1;
dp[i][j] = LLONG_MAX;
for (int k = i; k < j; k++) // 最后枚举分割点
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
dp[i][j] += sum[j] - sum[i - 1]; // 加上整段的合并代价
}
}
cout << "最小合并代价 = " << dp[1][n] << endl;
return 0;
}输入：
4
4 1 1 4
输出：最小合并代价 = 181.2 树形 DP：先算子树，再算父节点
树有天然的分层结构，很适合 DP：后序遍历——先递归算完每个孩子的答案，再在父节点上汇总。dp[u][0/1] 表示"以 u 为根的子树，且 u 不选/选"时的最优值。经典问题是树上最大独立集（选尽量多的点，任意两个不能相邻）：
#include <bits/stdc++.h>
using namespace std;
vector<int> g[105];
int dp[105][2];
void dfs(int u, int fa) {
dp[u][0] = 0; // u 不选：孩子随便选或不选
dp[u][1] = 1; // u 选（权值都为 1）
for (int v : g[u]) {
if (v == fa) continue; // 别走回父节点
dfs(v, u);
dp[u][0] += max(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0]; // u 选了，孩子只能不选
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
cout << "最大独立集大小 = "
<< max(dp[1][0], dp[1][1]) << endl;
return 0;
}输入：
6
1 2
1 3
2 4
2 5
3 6
输出：最大独立集大小 = 41.3 状压 DP：用二进制数表示"集合"
当问题规模很小（n ≤ 20），但需要记住"哪些已经用过"这种集合信息时，可以用一个整数的二进制位表示集合：第 i 位为 1 表示点 i 已在集合中。dp[S][u] = 已访问集合 S、当前在 u 的最短路。以旅行商（TSP）为例：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<vector<int>> d(n, vector<int>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) cin >> d[i][j];
vector<vector<int>> dp(1 << n, vector<int>(n, 1e9));
dp[1][0] = 0; // 从 0 出发，只访问过 0
for (int s = 1; s < (1 << n); s++) // 枚举集合状态
for (int u = 0; u < n; u++)
if (s >> u & 1) // u 在集合里
for (int v = 0; v < n; v++)
if (!(s >> v & 1)) // v 还没去过
dp[s | (1 << v)][v] =
min(dp[s | (1 << v)][v], dp[s][u] + d[u][v]);
int ans = 1e9;
for (int u = 1; u < n; u++) // 访问完全部再回 0
ans = min(ans, dp[(1 << n) - 1][u] + d[u][0]);
cout << "最短回路长度 = " << ans << endl;
return 0;
}输入：
4
0 2 9 10
1 0 6 4
15 7 0 8
6 3 12 0
输出：最短回路长度 = 21基础练习：写一个区间 DP 求"括号序列的最小添加数使其合法"（提示：dp[i][j] 表示区间 i~j 最少加几个括号）。
挑战练习：用树形 DP 求"树的最小支配集"；再思考：为什么 TSP 用状压而 n 大时只能用近似算法？提示：先想状态要记哪些信息，就知道集合为什么必须记。
↑ 目录第 2 章 图论进阶：最短路、最小生成树、网络流
本章目标：掌握最短路算法全家桶的选型，理解并查集与 Kruskal 最小生成树，认识最大流与最小割，构建完整图论工具箱。
2.1 最短路选型：Dijkstra / SPFA / Floyd 什么时候用
最短路算法没有银弹，关键是看数据范围：
- Dijkstra（堆优化）：单源、边权非负，竞赛首选，复杂度 O((n+m) log n)。
- SPFA：能处理负权边（Dijkstra 不行），但最坏能到 O(nm)，适合负权小图与判负环。
- Floyd：多源任意两点最短路，代码最短，但 O(n³)，n ≤ 300 才安全。
当题目要"所有点对"的最短路，或图很小（n ≤ 300），直接 Floyd：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<long long>> d(n, vector<long long>(n, 1e18));
for (int i = 0; i < n; i++) d[i][i] = 0;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
d[u][v] = w; d[v][u] = w; // 无向图
}
for (int k = 0; k < n; k++) // 中转点必须在外层
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
cout << "0 到 3 最短 = " << d[0][3] << endl;
return 0;
}输入：
4 5
0 1 1
0 2 4
1 2 2
1 3 5
2 3 1
输出：0 到 3 最短 = 42.2 Kruskal 最小生成树：并查集的黄金搭档
最小生成树（MST）要选 n-1 条边把所有点连通且总权最小。Kruskal 的思路极其简单：边按权从小到大排，能连就连。用并查集判断"连上会不会成环"：
#include <bits/stdc++.h>
using namespace std;
struct Edge { int u, v, w; };
vector<Edge> edges;
int fa[100005];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
edges.push_back({u, v, w});
}
sort(edges.begin(), edges.end(),
[](Edge a, Edge b) { return a.w < b.w; });
long long ans = 0, cnt = 0;
for (auto e : edges) {
int fu = find(e.u), fv = find(e.v);
if (fu != fv) { // 不在同一集合：不会成环
fa[fu] = fv;
ans += e.w;
cnt++;
}
}
cout << (cnt == n - 1 ? "MST权值 = " + to_string(ans) : "不连通")
<< endl;
return 0;
}输入：
4 5
1 2 1
1 3 4
2 3 2
2 4 5
3 4 3
输出：MST权值 = 62.3 网络流入门：Dinic 最大流
网络流是一大类问题的统一建模语言："源点"向"汇点"输送流量，边有容量上限，问最大能送多少。最大流用 Dinic 算法：先 BFS 分层，再沿可行增广路 DFS 找增广路。
#include <bits/stdc++.h>
using namespace std;
struct Edge { int to, cap, rev; };
vector<Edge> g[105];
int level[105], it[105];
void add(int u, int v, int c) { // 加正向边 + 反向边
g[u].push_back({v, c, (int)g[v].size()});
g[v].push_back({u, 0, (int)g[u].size() - 1});
}
bool bfs(int s, int t) { // 分层
memset(level, -1, sizeof level);
queue<int> q; q.push(s); level[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto &e : g[u])
if (e.cap > 0 && level[e.to] < 0)
level[e.to] = level[u] + 1, q.push(e.to);
}
return level[t] >= 0;
}
int dfs(int u, int t, int f) { // 找增广路
if (u == t) return f;
for (int &i = it[u]; i < (int)g[u].size(); i++) {
Edge &e = g[u][i];
if (e.cap > 0 && level[u] + 1 == level[e.to]) {
int d = dfs(e.to, t, min(f, e.cap));
if (d > 0) { e.cap -= d; g[e.to][e.rev].cap += d; return d; }
}
}
return 0;
}
int maxflow(int s, int t) {
int flow = 0;
while (bfs(s, t)) { // 循环直到没有增广路
memset(it, 0, sizeof it);
int f;
while ((f = dfs(s, t, 1e9)) > 0) flow += f;
}
return flow;
}
int main() {
int n, m;
cin >> n >> m; // 1 为源，n 为汇
for (int i = 0; i < m; i++) {
int u, v, c;
cin >> u >> v >> c;
add(u, v, c);
}
cout << "最大流 = " << maxflow(1, n) << endl;
return 0;
}输入：
4 5
1 2 3
1 3 2
2 3 1
2 4 2
3 4 3
输出：最大流 = 5基础练习：用 Floyd 求"传递闭包"；用并查集判断一张图是否连通。
挑战练习：把 Dinic 背到"闭眼可写"，再用最大流-最小割模型解决"方格取数"一类问题。提示：先想源汇怎么设、割的含义是什么。
↑ 目录第 3 章 数论与组合数学
本章目标：系统掌握竞赛数论的核心工具：质数筛、辗转相除、扩展欧几里得、快速幂与乘法逆元，并会用它们算组合数。
3.1 质数筛：埃氏筛与欧拉筛
判断单个数质数试除到 sqrt(n) 即可；但要求"n 以内所有质数"时必须用筛。埃氏筛的思路：从 2 开始，把每个质数的倍数全部划掉，剩下的就是质数。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<bool> is(n + 1, true);
is[0] = is[1] = false;
for (int i = 2; i * i <= n; i++) // 只需筛到 sqrt(n)
if (is[i])
for (int j = i * i; j <= n; j += i)
is[j] = false; // 划掉 i 的倍数
for (int i = 2; i <= n; i++)
if (is[i]) cout << i << " ";
cout << endl;
return 0;
}输入：30
输出：2 3 5 7 11 13 17 19 23 293.2 扩展欧几里得：解不定方程与求逆元
辗转相除 gcd(a,b) 之外，扩展欧几里得还能顺带求出一组整数解 ax + by = gcd(a,b)。它和快速幂一起，是模运算世界的两大基石：
#include <bits/stdc++.h>
using namespace std;
// 返回 gcd(a,b)，并求出一组 ax + by = gcd(a,b) 的整数解
long long exgcd(long long a, long long b,
long long &x, long long &y) {
if (b == 0) { x = 1; y = 0; return a; }
long long g = exgcd(b, a % b, y, x);
y -= a / b * x;
return g;
}
long long qpow(long long a, long long b, long long mod) {
long long res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int main() {
long long x, y;
long long g = exgcd(3, 7, x, y); // 求 3 在模 7 下的逆元
cout << "gcd(3,7) = " << g << endl;
cout << "3 在模 7 下的逆元 = " << (x % 7 + 7) % 7 << endl;
cout << "2^10 mod 1e9+7 = " << qpow(2, 10, 1000000007) << endl;
return 0;
}gcd(3,7) = 1
3 在模 7 下的逆元 = 5
2^10 mod 1e9+7 = 1024逆元是模运算里的"除法"：模数 p 是质数时，a 的逆元也可以用费马小定理 a^(p-2) mod p 求，即 qpow(a, p-2, p)。exgcd 与快速幂两条路都要会。
3.3 组合数取模：C(n, m) 怎么快速求
要求 C(n, m) mod p（p 为大质数，如 1e9+7）时，先预处理阶乘 fac[i] 与阶乘逆元 ifac[i]，则 C(n,m) = fac[n] * ifac[m] * ifac[n-m]。预处理用递推 ifac[n] = qpow(fac[n], p-2, p)，再倒推。核心代码：
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long qpow(long long a, long long b, long long mod) {
long long res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int main() {
int n = 10; // 需要算到 10!
vector<long long> fac(n + 1), ifac(n + 1);
fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD;
ifac[n] = qpow(fac[n], MOD - 2, MOD); // 费马小定理求逆元
for (int i = n; i >= 1; i--) ifac[i - 1] = ifac[i] * i % MOD;
auto C = [&](int m, int k) { // C(m, k)
if (k < 0 || k > m) return 0LL;
return fac[m] * ifac[k] % MOD * ifac[m - k] % MOD;
};
cout << "C(10,3) = " << C(10, 3) << endl;
cout << "C(10,5) = " << C(10, 5) << endl;
return 0;
}C(10,3) = 120
C(10,5) = 252基础练习：用埃氏筛输出 100 以内质数并统计个数；用 exgcd 求 5 在模 12 下的逆元。
挑战练习：用快速幂写"矩阵快速幂"，并求斐波那契数列第 1e9 项（提示：转移矩阵 [[1,1],[1,0]] 的 n 次方）。
↑ 目录第 4 章 数据结构进阶：线段树、树状数组、平衡树
本章目标：掌握树状数组与线段树这两件"区间操作利器"，理解它们把 O(n) 变成 O(log n) 的原理，认识平衡树的应用场景。
4.1 树状数组：lowbit 与单点改、区间和
树状数组用一段数组巧妙地维护前缀信息。lowbit(i) = i & -i 是它的灵魂——单点加时向上跳，查前缀和时向下跳，都是 O(log n)：
#include <bits/stdc++.h>
using namespace std;
int c[100005], n;
void add(int i, int x) { // 单点加：a[i] += x
for (; i <= n; i += i & -i) c[i] += x;
}
int query(int i) { // 前缀和：a[1] + ... + a[i]
int s = 0;
for (; i > 0; i -= i & -i) s += c[i];
return s;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) { int x; cin >> x; add(i, x); }
cout << "前3项和 = " << query(3) << endl;
add(2, 5); // a[2] 加上 5
cout << "a[2]加5后前4项和 = " << query(4) << endl;
return 0;
}输入：
5
3 1 4 1 5
输出：
前3项和 = 8
a[2]加5后前4项和 = 144.2 树状数组经典应用：逆序对
逆序对（i < j 且 a[i] > a[j]）用树状数组有经典 O(n log n) 解法：从左到右扫描，每个数进来前先问"已经插入了多少比它大的数"，这就是它贡献的逆序对：
#include <bits/stdc++.h>
using namespace std;
int c[100005], n;
void add(int i, int x) { for (; i <= n; i += i & -i) c[i] += x; }
int query(int i) { int s = 0; for (; i > 0; i -= i & -i) s += c[i]; return s; }
int main() {
cin >> n;
long long inv = 0;
for (int i = 1; i <= n; i++) {
int x;
cin >> x; // 值域较小时可直接当下标
inv += query(n) - query(x); // 已插入且大于 x 的个数
add(x, 1); // x 出现一次，登记
}
cout << "逆序对数 = " << inv << endl;
return 0;
}输入：
5
3 1 4 1 5
输出：逆序对数 = 3若值域很大（比如 10⁹），先离散化（排序后映射成 1~n）再用树状数组，思路完全一样。
4.3 线段树：区间修改 + 区间查询 + 懒标记
树状数组做不了"区间整体加一个数再查区间和"，这时上线段树。线段树把数组递归地分成两半，每个节点管一段区间。懒标记（lazy）是核心技巧：区间加时不立刻更新到底，先记在节点上，用到时才"下传"：
#include <bits/stdc++.h>
using namespace std;
long long sum[400005], lazy[400005]; // 4 倍空间
int n;
void build(int o, int l, int r, vector<int> &a) {
if (l == r) { sum[o] = a[l]; return; }
int mid = (l + r) / 2;
build(o * 2, l, mid, a);
build(o * 2 + 1, mid + 1, r, a);
sum[o] = sum[o * 2] + sum[o * 2 + 1];
}
void push(int o, int l, int r) { // 懒标记下传
if (lazy[o] && l != r) {
int mid = (l + r) / 2;
sum[o * 2] += lazy[o] * (mid - l + 1);
sum[o * 2 + 1] += lazy[o] * (r - mid);
lazy[o * 2] += lazy[o];
lazy[o * 2 + 1] += lazy[o];
}
lazy[o] = 0;
}
void add(int o, int l, int r, int ql, int qr, int v) {
if (ql <= l && r <= qr) { // 完全覆盖：记录懒标记即可
sum[o] += (long long)v * (r - l + 1);
lazy[o] += v;
return;
}
push(o, l, r);
int mid = (l + r) / 2;
if (ql <= mid) add(o * 2, l, mid, ql, qr, v);
if (qr > mid) add(o * 2 + 1, mid + 1, r, ql, qr, v);
sum[o] = sum[o * 2] + sum[o * 2 + 1];
}
long long ask(int o, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return sum[o];
push(o, l, r);
int mid = (l + r) / 2;
long long res = 0;
if (ql <= mid) res += ask(o * 2, l, mid, ql, qr);
if (qr > mid) res += ask(o * 2 + 1, mid + 1, r, ql, qr);
return res;
}
int main() {
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n, a);
cout << "区间[1,5]和 = " << ask(1, 1, n, 1, 5) << endl;
add(1, 1, n, 2, 4, 2); // 把 [2,4] 每个 +2
cout << "区间[2,4]+2后[1,5]和 = " << ask(1, 1, n, 1, 5) << endl;
return 0;
}输入：
5
1 2 3 4 5
输出：
区间[1,5]和 = 15
区间[2,4]+2后[1,5]和 = 214.4 平衡树：什么时候真的需要
需要"动态插入删除 + 查第 k 小 + 查前驱后继"时，普通的 set/multiset（内部红黑树）够用就不用自己写；只有需要"查排名"或用自定义分裂合并（文艺平衡树）时才写 Treap/Splay。竞赛原则：能用 STL 就不手写，手写只背最稳的一份模板。
基础练习：用树状数组求区间和，并比较 n=10⁵ 时与暴力 O(n²) 的差距。
挑战练习：写线段树求"区间最大值 + 单点修改"；再思考：为什么要开 4 倍而不是 2 倍空间？提示：递归线段树不是满二叉树。
↑ 目录第 5 章 字符串算法：KMP、Trie、哈希
本章目标：掌握 KMP 的模式匹配、Trie 的前缀统计与字符串哈希的 O(1) 子串比较，搭建字符串处理工具箱。
5.1 KMP：让模式串"滑着走"
朴素匹配失配时只前进一格，是 O(nm)。KMP 的聪明之处：失配时利用已经匹配的部分，让模式串跳到下一个可能的位置。next 数组记录"前缀的公共前后缀长度"：
#include <bits/stdc++.h>
using namespace std;
int main() {
string s, p;
cin >> s >> p; // s 长文本，p 模式串
vector<int> nxt(p.size(), 0);
for (int i = 1, j = 0; i < (int)p.size(); i++) {
while (j > 0 && p[i] != p[j]) j = nxt[j - 1];
if (p[i] == p[j]) j++;
nxt[i] = j;
}
cout << "next数组: ";
for (int v : nxt) cout << v << " ";
cout << endl << "匹配位置: ";
bool found = false;
for (int i = 0, j = 0; i < (int)s.size(); i++) {
while (j > 0 && s[i] != p[j]) j = nxt[j - 1];
if (s[i] == p[j]) j++;
if (j == (int)p.size()) {
cout << i - (int)p.size() + 1 << " "; // 0 起始下标
found = true;
j = nxt[j - 1];
}
}
if (!found) cout << "无";
cout << endl;
return 0;
}输入：
abababa
aba
输出：
next数组: 0 0 1
匹配位置: 0 2 45.2 Trie：一棵能"数前缀"的树
Trie（字典树）把单词的每个字母变成树的一条边，公共前缀共享节点。查询前缀"覆盖了多少单词"只需走到该前缀对应节点，再统计子树里有多少完整单词：
#include <bits/stdc++.h>
using namespace std;
int ch[100000][26], cnt[100000], tot = 0; // ch[u][k]: 节点 u 走 k 边到哪
void insert(string s) {
int u = 0;
for (char c : s) {
int k = c - 'a';
if (!ch[u][k]) ch[u][k] = ++tot; // 没有就新建节点
u = ch[u][k];
}
cnt[u]++; // 标记这是一个单词结尾
}
int dfs(int u) { // 子树内完整单词总数
int res = cnt[u];
for (int k = 0; k < 26; k++)
if (ch[u][k]) res += dfs(ch[u][k]);
return res;
}
int prefix(string s) { // 以 s 为前缀的单词数
int u = 0;
for (char c : s) {
int k = c - 'a';
if (!ch[u][k]) return 0;
u = ch[u][k];
}
return dfs(u);
}
int main() {
vector<string> words = {"app", "apple", "apply", "application", "code"};
for (auto w : words) insert(w);
cout << "前缀 app 覆盖 " << prefix("app") << " 个单词" << endl;
cout << "前缀 appl 覆盖 " << prefix("appl") << " 个单词" << endl;
cout << "前缀 code 覆盖 " << prefix("code") << " 个单词" << endl;
return 0;
}前缀 app 覆盖 4 个单词
前缀 appl 覆盖 3 个单词
前缀 code 覆盖 1 个单词5.3 字符串哈希：把"比子串"变成"比整数"
把字符串看成一个 B 进制大整数再取模，两个子串相等当且仅当哈希值相等，于是 O(1) 就能比较任意两个子串。这是字符串题里极其常用的"偷懒而强大"的工具：
#include <bits/stdc++.h>
using namespace std;
int main() {
string s = "abcabc";
const long long B = 131, M = 1000000007; // B 进制 + 大质数
vector<long long> h(s.size() + 1), pw(s.size() + 1, 1);
for (int i = 0; i < (int)s.size(); i++) {
h[i + 1] = (h[i] * B + s[i]) % M; // 前缀哈希
pw[i + 1] = pw[i] * B % M;
}
auto get = [&](int l, int r) { // 子串 [l, r) 的哈希
return (h[r] - h[l] * pw[r - l] % M + M) % M;
};
cout << "子串[0,3)与[3,6) ";
cout << (get(0, 3) == get(3, 6) ? "哈希相等" : "不相等") << endl;
cout << "子串[0,2)与[2,4) ";
cout << (get(0, 2) == get(2, 4) ? "哈希相等" : "不相等") << endl;
return 0;
}子串[0,3)与[3,6) 哈希相等
子串[0,2)与[2,4) 不相等基础练习：用 KMP 输出模式串在文本中所有出现位置；用哈希判断一个字符串是否回文。
挑战练习：用 Trie 统计一篇英文里出现最多的前 k 个前缀；再想：字符串哈希的 h[l..r] 公式为什么是"减乘"而不是"减"？提示：对齐位数。
↑ 目录第 6 章 计算几何与思维杂题
本章目标：掌握叉积这一计算几何的"瑞士军刀"，理解线段相交判定，训练面对陌生题目的思维方法。
6.1 叉积：判断方向的神器
叉积 a × b = a.x*b.y - a.y*b.x。它的符号告诉你 b 相对 a 的旋转方向：正为逆时针、负为顺时针、0 为共线。几乎所有计算几何题（点在直线哪侧、线段相交、凸包、多边形面积）都建立在它之上：
#include <bits/stdc++.h>
using namespace std;
struct Point { double x, y; };
double cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
int main() {
Point a{1, 0}, b{0, 1};
double v = cross(a, b);
cout << "叉积 = " << v << endl;
cout << (v > 0 ? "b 在 a 的逆时针方向" : "b 在 a 的顺时针方向")
<< endl;
return 0;
}叉积 = 1
b 在 a 的逆时针方向6.2 线段相交判定
判断线段 AB 与 CD 是否相交：对每条线段，看另一个线段的两个端点是否在它的两侧（叉积异号）。两侧都用叉积检验，若都"跨立"则相交：
#include <bits/stdc++.h>
using namespace std;
struct Point { double x, y; };
// 向量 ab 与 ac 的叉积：判断 c 在 ab 的哪一侧
double cross(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool inter(Point a, Point b, Point c, Point d) {
double d1 = cross(c, d, a), d2 = cross(c, d, b); // a、b 在 CD 两侧?
double d3 = cross(a, b, c), d4 = cross(a, b, d); // c、d 在 AB 两侧?
return d1 * d2 < 0 && d3 * d4 < 0; // 都跨立则相交
}
int main() {
Point a{0, 0}, b{2, 2}, c{0, 2}, d{2, 0};
cout << "线段(0,0)-(2,2) 与 (0,2)-(2,0) ";
cout << (inter(a, b, c, d) ? "相交" : "不相交") << endl;
Point e{0, 0}, f{1, 1}, g{2, 2}, h{3, 3};
cout << "线段(0,0)-(1,1) 与 (2,2)-(3,3) ";
cout << (inter(e, f, g, h) ? "相交" : "不相交") << endl;
return 0;
}线段(0,0)-(2,2) 与 (0,2)-(2,0) 相交
线段(0,0)-(1,1) 与 (2,2)-(3,3) 不相交6.3 思维杂题：面对陌生题怎么想
省选最常考的其实不是冷门算法，而是把陌生问题转化成熟悉模型的能力。训练要点：
- 先暴力：任何题先写能拿部分分的暴力，保证不零分，再想优化。
- 构造与特例：小数据手算、画图，找规律与反例。
- 复杂度即线索：数据范围暗示算法——n ≤ 20 想状压，n ≤ 500 想 Floyd/O(n³)，n ≤ 10⁵ 想 O(n log n)。
- 二分答案：求"最大值最小/最小值最大"时，先想能否二分后判定。
基础练习：用叉积判断三点顺时针还是逆时针排列；写一个判断点是否在三角形内的小程序。
挑战练习：完成一道"最大值最小"的二分答案题，并用对拍程序验证与暴力的结果一致。提示：对拍 = 随机小数据同时跑两份代码对比输出。
↑ 目录第 7 章 省选专题与历年真题
本章目标：按省选热门专题（博弈论、概率期望、分治进阶）建立模型库，训练"读题-建模-选算法-写码"的完整流程。
本章以每周 1~2 道省选真题任务代替常规基础/挑战练习——省选题没有"套路练习"，刷真题并复盘才是通往省选的正路。
7.1 博弈论入门：巴什博弈
博弈题的答案往往是一句简洁的必胜/必败判定。最基础的巴什博弈：n 个石子，每次取 1~m 个，取到最后一个的赢。结论：n % (m+1) != 0 先手必胜——因为先手总能留给对方 (m+1) 的整数倍，对方取 k 个，先手就取 (m+1-k) 个，把局面循环推回自己手里：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m; // n 个石子，每次取 1~m 个
if (n % (m + 1) != 0)
cout << "先手必胜" << endl;
else
cout << "先手必败" << endl;
return 0;
}输入：10 3
输出：先手必胜
输入：8 3
输出：先手必败7.2 概率期望：从计数到加权平均
期望 = Σ（取值 × 概率）。竞赛里的期望题常用期望 DP：dp[i] 表示"从状态 i 到终点的期望步数"，按"下一步所有可能 × 各自概率"转移。注意期望 DP 常需要逆推（从终点往起点推），转移里出现自己时要用移项解方程。
7.3 真题拆解：一套完整的解题流程
省选真题不会明说"这题考线段树"，它需要你从问题里识别模型。每道题固定走这套流程：
1. 读题 3 遍，圈出数据范围与特殊性质（有无负权/是否有序/是否取模）
2. 先想暴力解法，再想正解，两者都保证能拿分
3. 估算复杂度：n≤10^8 想 O(n)，10^5 想 O(n log n)，500 想 O(n^3)
4. 写完先测样例，再构造极端数据自测，最后对拍暴力
5. 留 30 分钟检查：文件名、数组大小、类型、调试输出、特殊情况任务：每周完成 1~2 道省选真题（前 3 章优先），每道写清"我识别到了什么模型、卡在哪一步"，周末集中讲评与变式训练。
↑ 目录第 8 章 集训与赛前冲刺
本章目标：用正确的方式度过赛前 8 周：专题补漏、全真模拟、模板与心态双准备，把训练水平稳定转化为赛场得分。
本章是赛前冲刺章，以每周全真模拟 + 错题复盘代替常规练习——连续 6 场模拟的分差收敛，就是最好的"练习"。
8.1 专题补漏：用错题本驱动冲刺
冲刺期的题海要"以我为主"。每周先做 1 场模拟暴露问题，再把错题按专题归类：是 DP 转移错、边界漏、还是读题失误？针对薄弱专题集中刷 10~20 题，而不是每天无差别刷套题。重写错题比做新题更有效——同一道题隔三天不看答案重写一遍，才叫真会。
8.2 全真模拟：把"会做"训练成"做对"
模拟必须严格：同样时长、同样环境、不许中途查资料、用 freopen 读文件。每场模拟后做三件事：估分 → 对照实际得分找差距 → 分析失分原因（不会/粗心/时间不够）。连续 6 场模拟的分差收敛了，考场心态就稳了。
8.3 模板清单：赛前最后一晚的定心丸
必背模板清单（考前默写一遍）
图论 Dijkstra / SPFA / Kruskal / 并查集
数据结构 树状数组 / 线段树(懒标记) / 单调栈
字符串 KMP / 哈希 / Trie
数论 exgcd / 快速幂 / 逆元 / 欧拉筛
网络 Dinic 最大流（背最稳版本）
工具 __int128 / freopen / 对拍脚本结课目标：完成赛前 6 场全真模拟，达成个人目标分数拆解；赛后复盘归档进个人错题本。
学制安排
结构 长期体系（8 章专题）+ 考前 8 周集训冲刺
班型 精英小班 / 一对一
周期 全年滚动招生，按选手水平进入长期体系或直接进入考前集训
频次 长期体系每周 1 次正课（约 60+ 次课，覆盖 8 章）；
考前 8 周每周 2 场全真模拟 + 错题复盘
时长 每次 120 分钟
配套 省选级题库 + 定期模拟 + 赛后复盘课程特色
- 专题体系化：按省选考点逐专题击破，不留知识盲区。
- 省选级题库：配套题目对标省选与 NOI 难度，远超普通网题。
- 代码即讲义：每个算法给完整可运行代码与真实结果，选手照例可自测。
- 以赛代练：定期模拟 + 深度复盘 + 错题重写，把"会做"变成"做对"。
常见问题
- 水平不够可以上吗？ 报名需通过入学测评，确保课程难度与选手匹配，避免浪费时间。
- 线上还是线下？ 两种形式都有，外地选手可全程线上，配套答疑群。
- 能保证出成绩吗？ 不能承诺奖项，但会给选手清晰的成长路径与全力支持。
- 练习如何提交批改？ 代码或题解发送到邮箱 lackychen@foxmail.com，老师逐题批改并点评算法实现与优化空间。
- 上课跟不上怎么办？ 课后可约一对一补漏，针对卡住的专题单独讲解，再进班跟进。
