适用语言：C++17/20，Python 3.12。
感谢GPT5.5和奥特曼，让我能用拙略的语言编写出它。

前言

一场程序设计竞赛像一季结构紧凑的番剧。第一集给设定，第二集埋冲突，中段展开规则，最后把所有伏笔收束到一个可以判定的结局。题面里的城市、魔法、比赛、摊位、打字机、电话网络，都只是叙事外壳；真正决定 AC 的，是你能否从这些外壳中取出变量、状态、转移、约束和证明。

本书不把算法写成咒语表。模板当然重要，但模板只负责“会写”；比赛要求的是“知道什么时候写、为什么这样写、边界怎么守住”。因此每个重要专题都按同一条链条展开：

题面信号 -> 模型选择 -> 状态或数据结构 -> 正确性理由 -> 复杂度 -> 代码落点 -> 自测

如果只记住“这题是 DP”，那还没有开始解题。真正的解题从下一句开始：为什么这个问题的未来只需要这些状态？为什么少一个维度会错？为什么这个贪心不会把后路砍掉？为什么这个图的点不是原来的点，而是事件、坐标或集合？

本书的目标不是把读者训练成背板选手，也不是许诺 AK。GDCPC 和大多数 ACM 赛制一样，都非常难全题通过，除非是小学学算法学到大学、题面扫一眼就能把模型翻出来的异常个体，否则“几小时下班”更像段子，不是训练目标。本书只讨论两件事：巩固已有能力，发展下一层能力。看到长题面不慌，看到 special judge 不虚，看到小参数能立刻闻到状态压缩的味道，看到字符串前后缀能想到 Border，看到“最早发生”能想到优先队列事件图。所谓速通，不是跳过理解，也不是幻想清空整张卷，而是学完能下场做题，不至于一题都拆不开；它追求的是把理解压缩成稳定动作。

ACM 赛制是冷酷的。题目不是按步骤给分，对就是对，错一个条件就是全错；样例通过不代表证明成立，思路接近也不会折算成分数。因此本书会反复强调 checker、对拍、自测和边界。它们不是附属环节，而是把“我觉得对”推进到“可以提交”的最后一道门。

当题面开始叽里咕噜，第一反应不要是翻模板。先把呼吸压下来，像芝麻凛一个人扎营那样，把地钉一根一根打进土里：变量是什么，操作改变了什么，目标函数在比较什么，约束里哪个数小到可以枚举，哪个数大到必须预处理。你只要按这个顺序走，混乱就会退后一步。题面仍然长，但它不再是一团雾，而是一条可以走的山路。

本书分三条线。学习线负责建立算法骨架：二分、贪心、DP、图论、字符串、数论、几何、剪枝、对拍、自测。回顾线负责把 2021-2025 的 GDCPC 题目拆成可记忆的模型，不把题目当答案索引，而把它们当训练样本。展望线负责组织三套模拟卷和近年命题思路，让备考不是盲刷，而是有节奏地补缺口。

GDCPC 是本书的主样本，不是本书的知识边界。竞赛方法可以从 ACM/CPC 拓展到 OI 和 OJ：ACM 强调限时协作、一次提交必须完全正确；OI 更强调部分分、子任务和长时间推敲；OJ 日常训练则强调可重复提交和长期积累。本书以 ACM 的严格正确性为底线，同时让算法知识能迁移到 OI/OJ 的日常训练中。

技术内容以 C++17/20 与 Python 3.12 为目标。难题讲到赛题边界为止，不把一本 GDCPC 手册扩写成算法百科；简单题会适当外扩，因为签到题是手感的来源。手感不稳的人上了赛场，很容易从天界优等生一路堕落成珈百璃，开场二十分钟就烂在样例前。

写算法手册不必把每一页都写成实验报告。严谨是骨架，阅读感是呼吸；偶尔有一句旁白拐到奇怪的地方，只要不妨碍定义、证明、复杂度和代码，它反而能让人从紧绷里松一口气。

开卷：读题的秩序

比赛中真正危险的不是不会，而是混乱。不会的题可以暂时放下，混乱会污染所有题。遇到长题面，按下面六步读。

第一步，删背景。城市、餐厅、魔法学院、端午大集、打字机，这些词通常不直接进入代码。它们负责让题面像故事，不负责让程序运行。

第二步，圈对象。对象可能是点、边、字符串、提交、区间、格子、事件、货币、牌堆。对象决定数组维度，也决定你是否需要建图。

第三步，列操作。操作是“翻转一行”“选择一个提交结果”“沿边传能”“剪开多边形”“把一个位置改成某字符”。算法建模几乎都从操作开始，因为状态转移本质上就是操作的影子。

第四步，写目标。最大值、最小值、计数、期望、任意合法方案，这五类目标对应完全不同的证明方式。最大最小常见二分、DP、贪心；计数常见组合、DP、容斥；期望要找状态或尾和；任意合法方案必须写 checker。

第五步，标约束。n<=15、m<=4、字符串总长 3e6、询问 1e5、坐标 1e9，这些数字比题目标题更诚实。小参数是状态压缩的邀请函，大输入是预处理和离线的警报器。

第六步，落代码。写出第一层循环之前，必须知道状态含义和循环方向。DP 的循环方向错了，就像把登山路线反着走；Tarjan 的父边处理错了，重边会把桥判歪；构造题不写 checker，样例再好看也只是没有旁证的自信。

速通的正名

“速通”不是把所有知识压成三页纸，也不是把比赛想象成一路无伤的剧情。算法学习里的速通，意思是先把足够多的基本动作训练到能用：读到 n<=15 时知道可以想状态压缩，读到“任意合法方案”时知道要写不变量和 checker，读到“最早到达/最早触发”时知道要考虑优先队列，读到“本质不同”时知道要问等价类和去重。它像凛酱一个人露营前收拾装备，不需要把整个户外用品店搬走，但火源、帐篷、灯和路线必须在包里。

速通后的最低标准不是 AK，而是下场不失语。你应当能在开场二十分钟内给每道题写一个入口词：模拟、二分、背包、状态压缩、构造、桥、Trie、几何、期望，或者暂时未知。入口词不等于题解，却能阻止大脑在题面里空转。之后再按风险排序：能写的先写，能对拍的对拍，special judge 先写 checker，难题先留下模型句。所谓“学完能去做题”，说的正是这一层能力。

第一小时

第一小时决定整场比赛的精神秩序。开场读题时不要急着打开 IDE 写第一道看起来像签到的题。先读全题，给每题写规模、目标、入口词和风险。规模负责告诉你复杂度边界，目标负责告诉你证明类型，入口词负责告诉你从哪个算法门进去，风险负责告诉你是否容易 WA。一个队伍或一个人，只要第一小时没有乱，后面即使遇到压轴，也还有退路。

如果一题读起来很像剧情简介，先问它的对象是什么。对象可以是人、队伍、题目、点、格子、字符串、区间，也可以是一次事件。再问操作改变了什么。翻转、提交、移动、合并、选择、刷新、传能，都必须能落成变量变化。最后问目标比较什么。最大收益、最小时间、方案数、期望值、任意合法输出，对应的是完全不同的程序结构。这个过程朴素得像太平收拾小埋留下的零食袋，但没有它，房间迟早会乱到无从下脚。

第一小时还要接受一个现实：有些题暂时不会做。不会做不是失败，误判才是失败。压轴题读不懂，可以留下“疑似期望 + 组合概率”或“疑似离线图 + 桥”这样的入口句；中档题能写，就先把 AC 拿稳。ACM 赛制不会给半对的代码发温柔奖，OI/OJ 训练也不会因为你“感觉很接近”自动补上边界。让代码从接近正确走到真正正确，靠的是证明、对拍和自测。

1. 真题考点地图

地图不是题单。题单告诉你有多少题，地图告诉你在雾里先往哪里走。读 GDCPC 的年份变化，最重要的不是背“某年出了某算法”，而是看命题人怎样把同一批能力换壳：有时把数学定义压成可计算函数，有时把字符串相等关系藏进故事，有时让图的点不再是点，而是事件、状态、区间或组件。

1.1 年份的气质

2021 年偏重数学定义的压缩。二分、数论表示、数位计数、博弈、图最短路、区间数据结构和几何题共同指向一件事：题面先给定义，选手再把定义改写成 count、check、transition 或 query。这一年的训练价值在于让人学会“不被定义吓住”。定义如果能比较，就可能二分；如果能递推，就可能预处理、DP 或矩阵快速幂；如果它描述局面胜负，就进入博弈。

2022 年强调等价、字符串和递推。拼图的旋转翻转、字符串的公共前后缀、连通块压缩、矩阵快速幂，都在问同一个问题：哪些对象虽然外表不同，却应当在代码里合并？Burnside 不必一开始学成群论讲义，但要懂“本质相同”如何变成“不变方案数”；Trie、KMP 和反串 Trie 也不是工具箱摆件，而是把相等关系变成路径和数组。

2023 年适合训练长题面的剥离。基站、市场、旅游、经典问题和计算几何看似故事差异很大，真正落入代码后往往很短：区间约束、交易状态、操作顺序、特殊完全图 MST、凸多边形直径。读这一年要练一种本领：背景越热闹，模型句越要短。题面可以像京子一样把场子搅起来，解题的人要像结衣一样把它按回秩序里。

2024 年的关键词是结构。Border、DFS 序、电话 Trie、桥、差分约束、倍数图，这些题的难点不是写很多代码，而是认出结构。结构题的残酷之处在于：认出来以前，题面像墙；认出来以后，墙上其实有门。它要求你知道每个结构回答什么问题。KMP 回答前后缀相等，Trie 回答前缀包含，Tarjan 桥回答删边连通性，差分约束回答一组不等式是否存在势能。

2025 年是综合建模样本。矩阵翻转、位运算构造、排列维护、数位贪心、网格构造、背包、子序列计数、事件图、字符串周期和窄网格 DP 同时出现。它最像一场正式训练：开头要稳住实现，中段要吃下 DP 和构造，后段要处理图事件、周期和小宽度状态。列数小、题数小、网格宽度小都不是装饰，而是命题人放在门口的钥匙。

ZJ2026 的题面更接近展望样本。图上构造、区间桥、期望、区间计数、交互、前缀修改、动态矩阵、隐式图 BFS、LIS/LDS 偏序，显示出更强的离线、随机过程和隐式状态意识。它不要求本书把所有高级算法铺开，但提醒读者：省赛训练不能只停在模板层，至少要能判断一题的入口是期望、离线图、搜索剪枝还是偏序 DP。

1.2 能力层级

第一层是比赛生存能力。快速 IO、排序、二分、前缀和、哈希表、取模、long long，这些内容不够华丽，却决定你会不会在简单题上流血。BFS、Dijkstra、并查集、Fenwick 和线段树也是同一层：它们是图和动态查询的基本骨架。没有这一层，后面的 DP、字符串和构造会像还没调音就上台的乐队，声音再大也不稳。

第二层是中档题能力。前缀 DP、背包 DP、状态压缩、计数去重、KMP/Z 函数、Trie、字符串哈希、Tarjan、组合数、矩阵快速幂和期望，是省赛中最常把人拉开的位置。这一层不能只背模板，因为题目很少把“我是背包”写在脸上。它通常会先讲封榜、货币、打字机、电话网络或魔法，然后在某个小参数、互斥选择、前后缀关系里露出模型。

第三层是后半场发展能力。构造、贪心证明、special judge、计算几何、离线分治、回滚并查集、搜索剪枝和 IDA* 不一定每场都完整用上，却决定你能不能在陌生题前保持判断力。这里的学习边界要清楚：难题按比赛设计讲到可识别、可复盘、可训练即可，不把一本手册写成百科；但 checker、对拍和自测必须深入，因为它们直接关系到 ACM 赛制里“错一个条件就是全错”的现实。

1.3 从题面到入口词

读题时先给每题写入口词。n<=20 通常指向状态压缩或搜索，m<=4 指向轮廓或窄网格，q 很大指向预处理或离线，输出任意合法方案指向构造和 checker，最早触发指向优先队列事件图，前后缀和周期指向 KMP/Z/Trie，本质相同指向等价类计数，凸多边形和最远距离指向叉积与旋转卡壳。

入口词不是答案。它只是让你不在题面里原地打转。真正解题还要继续追问：这个状态为什么够用？这个枚举后剩下部分是否独立？这个贪心有没有交换论证？这个构造的不变量是什么？这个输出如何用 checker 验证？当你能连续回答这些问题，题面就从“看不懂的一整页”变成了一段可以执行的程序。

2. 赛前速通路线

原则：先保证“主线任务”可通关，再挑战隐藏关。这里的速通不是三天练成神，也不是三小时下班；它只负责把已经学过或即将学会的内容整理成可执行顺序，让人至少能读题、拆题、写出可验证的代码。主线任务是基础实现、图论、DP、字符串、构造；隐藏关是离线图、期望、几何、复杂构造。

2.1 三天速通：补出下场基线

第 1 天处理基础与实现稳定性。目标不是“看完很多东西”，而是把比赛中最容易手滑的动作练到自动化：快速 IO、排序、二分、前缀和，随后接上 BFS、Dijkstra、并查集和 Fenwick。字符串只要求先掌握 KMP 前缀函数，能手算 pi 数组，能写出 Border 链。当天题目以 2025 A/D/F/H、2024 G/I、2023 A 为主。做题时每道题只追求一件事：把题面限制落到第一层循环。

第 2 天进入中档模型。背包 DP、状态压缩和字符串去重计数要连在一起学，因为它们都在回答“历史能否被压成少数变量”。构造题检查器和 Tarjan 桥也放在这一天：前者训练输出合法性，后者训练图结构。题目以 2025 B/E/G/J、2024 C/F/H、2023 B/L 为主。不要一边写构造一边祈祷评测机温柔，输出条件要逐条验，像薇奈特在放学后收拾一屋子混乱。

第 3 天补强后半场能力。期望、组合数、矩阵快速幂、计算几何基础、搜索剪枝和小数据对拍都不要求一口气学成大师，但要建立入口意识。看到随机过程能想到尾和或状态方程，看到凸多边形能想到叉积和旋转卡壳，看到搜索能想到上界剪枝和暴力验证。练习题以 2025 C/K/L、2024 A/B/J、2023 M 为主。三天速通的结尾不是“我学完了”，而是“我知道每类题第一步该写什么”。

2.2 两周训练

两周训练不按“今天看几个算法”计算，而按“今天能不能产出可提交代码”计算。前两天只做基础代码板，C++ 和 Python 各写一份，从输入、排序、二分、前缀和、Fenwick、并查集到 Dijkstra。写完后用小样例、随机样例和极端样例跑一遍，模板不是收藏品，必须能编译、能运行、能复用。

第 3 到第 4 天攻图论。BFS 训练状态去重，Dijkstra 训练优先队列和距离松弛，并查集训练连通性，Tarjan 训练 tin/low 和父边编号。至少做 5 道真题或改题，其中必须包含一题重边图和一题隐式图。图论最怕把题面对象原封不动当图点，训练时每道题都要写一句“点是什么，边是什么”。

第 5 到第 6 天攻 DP。前缀 DP、背包、状态压缩、区间 DP 各做一到两题。每题必须写状态含义、初值、转移顺序和答案位置；少写任何一项，都视为没有完成复盘。DP 不是把数组开出来就结束，它像一份旅途存档，存多了浪费，存少了回不了家。

第 7 天做第一次阶段训练，时间压到 3 小时。目标不是做最多题，而是检查前六天的基础是否能在限时下启动。训练结束后立刻复盘第一道 WA、第一道卡住的题和第一道没敢提交的题。很多人平时会，比赛不会，差的正是这一段现场秩序。

第 8 到第 9 天攻字符串。KMP、Z、Trie、哈希、Border 要连在一起学，因为它们都在回答“相等关系如何快速判断”。每做一道字符串题，都要先写相等关系：是前缀等于后缀，还是两个位置与全串前缀相等，还是多串公共前缀，还是任意子串相等。程序不会读心，阿尼亚可以，字符串算法不行。

第 10 天攻数学。组合数、期望、矩阵快速幂和数论观察各做一题。数学题必须先打小表，再写性质，再写公式。公式未经小数据检验，不许直接提交。第 11 天专门做构造和 special judge，至少给一道构造题写 checker；第 12 天补几何和扫描线，保证叉积、平方距离、线段关系和旋转卡壳不手生。

第 13 天做 5 小时完整模拟。开场读全题，中段抢确定性题，后段选一题最有希望的难题推进。第 14 天只做错题归档：把模板、反例、checker、对拍脚本和模型句整理到个人库里。训练的终点不是“我看过”，而是下一次遇到同类题时，手能自己摸到门把手。

3. 基础代码板

3.1 C++17 基础头

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i128 = __int128_t;

const ll INF64 = (1LL << 62);
const int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    return 0;
}

3.2 Python 基础头

import sys
from collections import deque, defaultdict
from heapq import heappush, heappop

input = sys.stdin.buffer.readline
INF = 10**30
MOD = 998244353

3.3 Fenwick Tree

C++：

struct Fenwick {
    int n;
    vector<long long> bit;

    Fenwick(int n = 0) { init(n); }

    void init(int n_) {
        n = n_;
        bit.assign(n + 1, 0);
    }

    void add(int idx, long long val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += val;
    }

    long long sum(int idx) const {
        long long res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }

    long long range_sum(int l, int r) const {
        if (l > r) return 0;
        return sum(r) - sum(l - 1);
    }

    int kth(long long k) const {
        int idx = 0;
        int step = 1;
        while ((step << 1) <= n) step <<= 1;
        for (; step; step >>= 1) {
            int nxt = idx + step;
            if (nxt <= n && bit[nxt] < k) {
                idx = nxt;
                k -= bit[nxt];
            }
        }
        return idx + 1;
    }
};

Python：

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, idx, val):
        while idx <= self.n:
            self.bit[idx] += val
            idx += idx & -idx

    def sum(self, idx):
        res = 0
        while idx > 0:
            res += self.bit[idx]
            idx -= idx & -idx
        return res

    def range_sum(self, left, right):
        if left > right:
            return 0
        return self.sum(right) - self.sum(left - 1)

    def kth(self, k):
        idx = 0
        step = 1
        while step * 2 <= self.n:
            step *= 2
        while step:
            nxt = idx + step
            if nxt <= self.n and self.bit[nxt] < k:
                idx = nxt
                k -= self.bit[nxt]
            step //= 2
        return idx + 1

3.4 并查集

C++：

struct DSU {
    vector<int> parent, size;

    DSU(int n = 0) { init(n); }

    void init(int n) {
        parent.resize(n + 1);
        size.assign(n + 1, 1);
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a;
        size[a] += size[b];
        return true;
    }
};

Python：

class DSU:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, x):
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        return True

3.5 Dijkstra

C++：

vector<long long> dijkstra(int n, int s, const vector<vector<pair<int,int>>> &g) {
    vector<long long> dist(n + 1, INF64);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    dist[s] = 0;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d != dist[u]) continue;
        for (auto [v, w] : g[u]) {
            long long nd = d + w;
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.push({nd, v});
            }
        }
    }
    return dist;
}

Python：

def dijkstra(n, s, graph):
    dist = [INF] * (n + 1)
    dist[s] = 0
    pq = [(0, s)]
    while pq:
        d, u = heappop(pq)
        if d != dist[u]:
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heappush(pq, (nd, v))
    return dist

3.6 Tarjan 桥

C++：

struct BridgeFinder {
    int n, timer;
    vector<vector<pair<int,int>>> g;
    vector<int> dfn, low, is_bridge;

    BridgeFinder(int n, int m) : n(n), timer(0), g(n + 1), dfn(n + 1), low(n + 1), is_bridge(m) {}

    void add_edge(int id, int u, int v) {
        g[u].push_back({v, id});
        g[v].push_back({u, id});
    }

    void dfs(int u, int pe) {
        dfn[u] = low[u] = ++timer;
        for (auto [v, id] : g[u]) {
            if (id == pe) continue;
            if (!dfn[v]) {
                dfs(v, id);
                low[u] = min(low[u], low[v]);
                if (low[v] > dfn[u]) is_bridge[id] = 1;
            } else {
                low[u] = min(low[u], dfn[v]);
            }
        }
    }

    vector<int> solve() {
        for (int i = 1; i <= n; ++i) {
            if (!dfn[i]) dfs(i, -1);
        }
        return is_bridge;
    }
};

Python：

def find_bridges(n, edges):
    graph = [[] for _ in range(n + 1)]
    for idx, (u, v) in enumerate(edges):
        graph[u].append((v, idx))
        graph[v].append((u, idx))

    dfn = [0] * (n + 1)
    low = [0] * (n + 1)
    is_bridge = [False] * len(edges)
    timer = 0

    def dfs(u, parent_edge):
        nonlocal timer
        timer += 1
        dfn[u] = low[u] = timer
        for v, idx in graph[u]:
            if idx == parent_edge:
                continue
            if dfn[v] == 0:
                dfs(v, idx)
                low[u] = min(low[u], low[v])
                if low[v] > dfn[u]:
                    is_bridge[idx] = True
            else:
                low[u] = min(low[u], dfn[v])

    for i in range(1, n + 1):
        if dfn[i] == 0:
            dfs(i, -1)
    return is_bridge

3.7 KMP 前缀函数

C++：

vector<int> prefix_function(const string &s) {
    int n = (int)s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) ++j;
        pi[i] = j;
    }
    return pi;
}

Python：

def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi

3.8 组合数

C++：

const long long MOD = 998244353;

long long mod_pow(long long a, long long e) {
    long long r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

struct Comb {
    vector<long long> fact, inv_fact;

    Comb(int n) : fact(n + 1), inv_fact(n + 1) {
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i % MOD;
        inv_fact[n] = mod_pow(fact[n], MOD - 2);
        for (int i = n; i >= 1; --i) inv_fact[i - 1] = inv_fact[i] * i % MOD;
    }

    long long C(int n, int k) const {
        if (k < 0 || k > n) return 0;
        return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
    }
};

Python：

def build_comb(n, mod):
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % mod

    inv_fact = [1] * (n + 1)
    inv_fact[n] = pow(fact[n], mod - 2, mod)
    for i in range(n, 0, -1):
        inv_fact[i - 1] = inv_fact[i] * i % mod

    def comb(N, K):
        if K < 0 or K > N:
            return 0
        return fact[N] * inv_fact[K] % mod * inv_fact[N - K] % mod

    return comb

4. 核心专题讲义

4.1 复杂度判断

复杂度判断是读题后的第一步。GDCPC 很多题会把故事写得很长，但输入规模通常直接暴露算法边界。读题时先找主规模 n,m,q,T，再找是否存在小参数，例如列数、颜色数、题数、bit 位数、网格宽度，最后确认多组数据下是否有 sum n、sum m 这样的总和限制。主规模决定不能做什么，小参数决定可以枚举什么，总和限制决定多测能否总线性处理。

规模	可用复杂度	首选模型
n <= 20	O(2^n n)	状态压缩、搜索
n <= 100	O(n^3)	区间 DP、Floyd、组合 DP
n <= 5000	O(n^2)	二维 DP、枚举优化
n <= 2e5	O(n log n)	排序、树状数组、线段树、Dijkstra
n <= 1e6	O(n)	前缀和、KMP、单调栈、双指针
q >= 1e6	O(1) 或 O(log n)	预处理、离线、二分

判断时按固定顺序走：先找最大输入规模，再找小参数，然后看多测是否有总和限制；若题目是 special judge，要立刻准备 checker；若坐标、乘积、方案数或路径代价可能很大，要在写数组前决定使用 long long 还是 __int128。这个顺序看似朴素，却能避免大量赛场事故。

常见误判有四种。T 很大但 sum n 有限制时，总线性算法仍可通过；单个 q 很大时，每问 O(n) 通常直接死亡，必须预处理或离线；存在小参数时，不要按主规模暴力，应优先压小参数；值域很大但实际数量很少时，应使用哈希、排序和离散化，而不是开值域数组。

真题中的规模信号很直接。2025 A 的列数小，所以枚举列翻转后让行独立求最优；2025 F 的题数 n<=15，所以每题生成选项组再合并；2025 L 的网格宽度 m<=4，这是轮廓 DP 或窄图建模的邀请；2024 J 的 n 极大，说明不能建图，只能找数论结构。

规模判断错了，后面所有努力都会变形。最常见的惨案不是算法完全不会，而是把 O(n^2) 写进 2e5，把每问线性写进百万询问，把值域数组开到 1e9。那种瞬间很像第一次站上大舞台却忘了接音箱，手指已经动了，声音没有出来，评测机只会冷静地给出 TLE 或 MLE。

4.2 二分与答案单调性

二分的适用条件只有一个核心：存在单调的判断函数 check(x)。题目可以问最小成本、最大阈值、第 k 大或最短时间，但代码里都必须落成一句话：当答案候选为 x 时，是否可行。若可行集合是一段连续区间，二分才成立；若可行性忽真忽假，二分代码写得再漂亮也只是萨塔妮亚式邪恶计划，气势很足，落点很歪。

C++ 最小可行值：

long long binary_first_true(long long lo, long long hi) {
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (check(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Python：

def binary_first_true(lo, hi):
    while lo < hi:
        mid = (lo + hi) // 2
        if check(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

二分题的关键不在二分代码，而在 check。

check(x) 必须返回清晰的布尔含义，并且可行集合连续。单次检查的复杂度要足够低，否则二分只会把超时包装得更有层次。边界值也要提前处理，尤其是乘法、平方、坐标差和方案计数。

常见模型：

模型	x 含义	check(x)
最小最大值	最大代价上限	能否在限制内完成
第 k 大/小	候选答案	统计不小于/不大于 x 的个数
最小资源	资源数量	是否满足所有需求
时间最短	时间上限	是否能到达或完成

第 k 大计数框架：

def kth_largest(lo, hi, k):
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if count_ge(mid) >= k:
            lo = mid
        else:
            hi = mid - 1
    return lo

训练二分时不要只背模板。整数二分要区分求最小可行值还是最大可行值，因此 mid=(lo+hi)//2 与 mid=(lo+hi+1)//2 的方向不同；实数二分要控制迭代次数或误差。每做一道二分题，都要先写出单调性证明，再写代码。证明只有一句也可以，但必须存在。

4.3 贪心与构造

构造题必须同时交代构造过程、不变量、无解判定和输出合法性检查。不变量是构造过程中始终为真的条件，例如前缀和集合中不存在相差 s 的两项，当前图中路径边不相交，当前染色不改变固定格，当前排列局部关系满足目标条件。没有不变量的构造只是猜答案，猜对样例不代表能过评测。

构造题不是“凭感觉召唤答案”，而是给系统写一套不会崩的设定集。每一步操作必须维护设定，最后输出才有合法性。若题目允许任意合法输出，checker 就应该像放学后默默收拾残局的人，把输出数量、值域、固定条件和目标条件逐条验过去；它不评价你的构造美不美，只确认它有没有说谎。

前缀和构造检查：

def valid_no_subarray_sum(seq, s):
    seen = {0}
    pref = 0
    for x in seq:
        pref += x
        if pref - s in seen:
            return False
        seen.add(pref)
    return True

构造题的解法不是“猜输出”，而是“设计一个不会破坏条件的生成过程”。

标准证明模板：

定义不变量 I。
初始时 I 成立。
每一步操作后 I 仍成立。
循环结束时，由 I 推出答案满足题目要求。
若存在无解分支，证明任何方案都会违反必要条件。

构造题常从五个入口进入。子段和条件通常转成前缀和差，例如禁止子段和为 s，等价于禁止两个前缀和相差 s。网格局部连通只看上下左右，大网格经常能压成每列状态。图路径的不相交通常与桥、边双或流有关。位运算构造要看整体位模式，不能逐位乱造，因为表达式会对所有位同时生效。操作顺序题则要通过交换论证确定哪些操作可以提前，哪些操作必须靠后；如果操作之间有依赖，先找拓扑序、贪心优先级或交换论证。

输出合法性 checker：

def check_fixed_cells(original, answer):
    n = len(original)
    m = len(original[0])
    for i in range(n):
        for j in range(m):
            if original[i][j] != 0 and original[i][j] != answer[i][j]:
                return False
    return True

真题中，2025 B 是位运算构造，核心是按 bit 模式分类；2025 E 是网格染色，核心是减少连通块且不改固定格；2024 F 是边不相交路径，需要先理解桥和边双；2023 H/J 是典型 special judge，输出合法性比样例一致更重要。训练构造题时，每题至少写一个 checker，不只验证样例，并且必须能用一句话说出不变量。

4.4 动态规划

DP 的核心不是数组，而是“遗忘的艺术”。状态保存已经处理过的部分中仍会影响未来的信息；初值描述空前缀、空集合或起点；转移说明如何从旧状态走向新状态；顺序保证转移来源已经计算；答案则从某个终点状态或一组合法状态中取出。少存一维，未来会找不到路；多存十维，内存会先替你宣布旅行结束。真正好的 DP 状态像末日旅途里的地图，纸面不大，却足够指明下一段路。

前缀 DP

不同子序列计数的标准去重思想：

new = 1 + total_before
add = new - last[char]
total += add
last[char] = new

带距离限制时，把 total_before 换成允许连接的最远前缀。

Python：

def count_distinct_loose_subseq(s, k, mod=998244353):
    n = len(s)
    total = [0] * (n + 1)
    last = [0] * 26
    for i, ch in enumerate(s, 1):
        prev = i - k - 1
        base = 1
        if prev >= 0:
            base = (base + total[prev]) % mod
        c = ord(ch) - 97
        add = (base - last[c]) % mod
        total[i] = (total[i - 1] + add) % mod
        last[c] = base
    return total[n]

为什么要用 last[char]：

同一个字符作为结尾时，新出现的位置会覆盖旧位置能形成的同名序列。last[c] 保存上一次字符 c 已经贡献过的“新增来源”。再次遇到 c 时必须减掉，否则同一个字符序列会被重复计算。

这类 DP 的边界要提前定死。空序列是否计入答案会改变初值；取模减法必须归正；带距离限制时，能连接的前缀不是 i-1，而是 i-k-1。2025 H 松散子序列正是这一模型的代表：前缀 DP 负责累计，last 负责去重，距离限制负责把可接前缀向左推。2025 G 货币系统虽然外表不像子序列计数，但训练价值相似：把查询压成可预处理的前缀函数，而不是每次从头模拟。

背包 DP

多重选择背包：每组物品选一个或不选。

def multi_choice_min_cost(n, groups, start_state):
    INF = 10**30
    dp = [[INF] * (n + 1) for _ in range(n + 1)]
    solved, post, cost = start_state
    dp[solved][post] = cost
    for opts in groups:
        ndp = [row[:] for row in dp]
        for i in range(n + 1):
            for j in range(n + 1):
                cur = dp[i][j]
                if cur == INF:
                    continue
                for di, dj, w in opts:
                    ni, nj = i + di, j + dj
                    if ni <= n and nj <= n:
                        ndp[ni][nj] = min(ndp[ni][nj], cur + w)
        dp = ndp
    return dp

多重选择背包适用于“每个对象产生若干互斥选项”的题。

建模时先把每个对象拆成选项组，再把每个选项写成状态增量和代价。每组只合并一次，答案在所有合法状态中取最优。2025 F 排名预测中，每道题的选项是“不通过”或“某次封榜提交作为首次 AC”。状态保存已通过题数、封榜后通过题数和最小罚时，最后扫描排名严格高于己方的状态，取最少封榜后通过题数。错误边界集中在罚时规则：已 AC 题的后续提交不影响罚时，同一分钟提交按输入顺序处理，“过几题”统计的是题数，不是 AC 提交次数。

状态压缩 DP

状态 mask 表示集合；转移添加一个未选元素。

def shortest_visit_all(cost):
    n = len(cost)
    INF = 10**30
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0
    for mask in range(1 << n):
        for u in range(n):
            cur = dp[mask][u]
            if cur == INF:
                continue
            for v in range(n):
                if (mask >> v) & 1:
                    continue
                nxt = mask | (1 << v)
                dp[nxt][v] = min(dp[nxt][v], cur + cost[u][v])
    return min(dp[-1])

状态压缩题的入口是小参数。

mask 可以表示选中集合、翻转状态、轮廓连通状态，也可以和 last 一起表示“已经访问的集合与当前末尾”。2025 A 矩阵游戏中，mask 表示列翻转；固定列后，每一行只需比较翻或不翻，总复杂度为 O(2^m * n * m)。2025 L 路线选择中，宽度 m<=4 意味着截面状态很少，可以按行推进，维护经过情况、连通性或端点信息。训练状态压缩时，必须熟悉枚举 mask、枚举子集、用 lowbit 做增量计算，并且要判断 Python 是否能承受当前 2^m 级别。

区间 DP

按长度递增。

vector<vector<long long>> dp(n, vector<long long>(n));
for (int len = 1; len <= n; ++len) {
    for (int l = 0; l + len - 1 < n; ++l) {
        int r = l + len - 1;
        for (int mid = l; mid < r; ++mid) {
            dp[l][r] = max(dp[l][r], dp[l][mid] + dp[mid + 1][r]);
        }
    }
}

区间 DP 适合端点配对、括号结构、区间合并、链式选择。

标准转移：

dp[l][r] = max/min over mid: dp[l][mid] + dp[mid+1][r] + cost

或：

固定 l 与某个 k 配对，再合并左右区间

ZJ2026 D 的区间选择题可作为区间计数训练：端点两两不同、存在嵌套链或同向链，本质是区间偏序与组合 DP。区间 DP 的边界主要有四个：必须按长度递增，空区间是否有值要提前定义，方案数要处理取模，O(n^3) 通常只适合 n≈100 的规模。

期望 DP

期望题常用尾和公式：

E[X] = sum_{t>=0} P(X > t)

尾和公式的使用条件是 X 为非负整数随机变量，并且能够统计每个时刻仍未完成的概率。ZJ2026 C 回文串文回中，随机选择位置可以改写成随机排列所有位置；回文条件按对称位置成对分析，每一对在前 t 个位置被选中的情况决定是否已经满足。概率用组合数表达，除法用模逆元，不使用浮点数处理模意义期望。

4.5 图论

图论题不应从模板名字开始，而应从“点是什么、边是什么、边权是什么”开始。黄昏执行任务前会先确认身份、路线和目标，图论建模也是同一件事。若边无权，BFS 是第一选择；若边权只有 0 和 1，使用 0-1 BFS；若边权非负，Dijkstra 成立；若只维护连通性，使用并查集或 Tarjan；若图有依赖顺序，考虑拓扑排序；若目标是连接所有点且代价最小，进入 Kruskal；若题目要求边不相交路径、匹配或割，再考虑流模型。

边不相交路径在无向图中常与边双连通分量等价：两点存在两条边不相交路径，意味着它们之间没有必须经过的桥。构造路径时可以利用 DFS 树和返祖边，也可以在规模允许时转成流。事件图则是另一种常见隐式图：点首次触发后产生新事件，事件按时间排序，状态第一次生效后不再重复扩展。

图论建模时，点可能是原图节点、网格位置、字符串状态、时间事件、三维坐标或子集状态；边可能是输入边、一次操作、一次转移、一次传送或一次事件传播。边权决定算法：无权用 BFS，0/1 权用 0-1 BFS，非负权用 Dijkstra，有依赖用拓扑排序，只问连通性则用并查集或 Tarjan。2025 J 解谜比赛是事件图，解锁点产生带时间的能量事件，用优先队列处理；2024 F 图是边不相交路径，核心是桥和边双；2023 L 经典问题是特殊完全图 MST，不能真建完全图；ZJ2026 L 的三维障碍物传送则把可站立坐标变成状态点。

事件图框架：

def event_process(initial_events, expand):
    pq = initial_events[:]
    from heapq import heapify, heappop, heappush
    heapify(pq)
    done = set()
    while pq:
        time, state = heappop(pq)
        if state in done:
            continue
        done.add(state)
        for nt, ns in expand(time, state):
            if ns not in done:
                heappush(pq, (nt, ns))
    return done

图题的边界很少温柔。重边不能随意去掉，Tarjan 在非连通图中要从每个点启动，Dijkstra 不能处理负边，隐式图必须哈希 visited。这些不是细枝末节，而是提交后 WA/RE/TLE 的常见来源。

4.6 字符串

字符串题的核心是“相等关系如何快速判断”。不要指望像阿尼亚一样读出字符串心声，程序只能靠结构。KMP 前缀函数回答 Border 和周期，Z 函数回答每个位置和全串前缀的 LCP，Trie 处理多字符串前缀和字典序选择，字符串哈希用于快速比较任意子串，Manacher 处理回文半径。

周期判定：

def min_period(s):
    pi = prefix_function(s)
    n = len(s)
    p = n - pi[-1]
    return p if n % p == 0 else n

Border 链：

def borders(s):
    pi = prefix_function(s)
    res = []
    x = pi[-1]
    while x:
        res.append(x)
        x = pi[x - 1]
    return res

字符串题的核心是“相等关系如何快速判断”。

问题	工具
前缀与后缀	KMP prefix function
每个位置和全串前缀 LCP	Z function
多字符串前缀	Trie
任意子串比较	Hash / SA
回文	Manacher
周期	KMP / Z

KMP 的两个基本用途是求 Border 链和求最小周期。2024 B 腊肠披萨的题面核心是最长公共前后缀，Border 不是“最长相同子串”，必须同时是前缀和后缀。2025 K 打字机的打印轨迹是正向再反向的折返周期，需要先转化为周期或镜像相等，再考虑每个前缀的最短模板。训练时要能手算 pi 数组，会从 pi[n-1] 得到周期，会枚举 Border 链，也要知道什么时候字符串哈希比 KMP 更适合。

4.7 数论与组合

数论与组合不靠灵感硬顶，靠结论落地。gcd(a,b)=gcd(b,a%b) 是最大公约数的计算入口；逆元存在条件是 gcd(a,mod)=1，质数模下常用 a^(mod-2)；组合数通常 O(n) 预处理后 O(1) 查询；矩阵快速幂用于固定维线性递推；Burnside 用于旋转、翻转、本质不同染色这类等价类计数。

欧拉函数筛：

vector<int> phi(int n) {
    vector<int> p, is(n + 1), phi(n + 1);
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!is[i]) {
            p.push_back(i);
            phi[i] = i - 1;
        }
        for (int prime : p) {
            if (1LL * i * prime > n) break;
            is[i * prime] = 1;
            if (i % prime == 0) {
                phi[i * prime] = phi[i] * prime;
                break;
            } else {
                phi[i * prime] = phi[i] * (prime - 1);
            }
        }
    }
    return phi;
}

数论题的第一步是小样例。

数论题的第一步是小样例。看 gcd 最大值时，通常要观察区间长度和倍数；看到递推时，问它能否矩阵化；看到本质不同，问是否有旋转或翻转群作用；看到模数，先判断是否为质数，是否可用逆元；看到值域，判断能否筛、分块或整除分块。别像青山小姐一样只留下谜语，公式必须被小数据验证。

Burnside 最小学习量：

本质不同方案数 = 所有群作用下不变方案数的平均值

Burnside 的最小学习量足够处理旋转相同、翻转相同、环形排列和多边形边状态。赛题通常不会要求完整群论叙述，但会要求你知道“本质相同”不是直接除以操作数，而是统计每个操作下保持不变的方案。

矩阵快速幂适用：

dp[t+1] = A * dp[t]
dp[k] = A^k * dp[0]

2022 K 斐波那契中，路径长度很大，收益又与 Fibonacci 权值相关，典型入口是把递推和图邻接矩阵结合。组合数题要保证预处理上限覆盖最大 n；模意义下除法必须转逆元；mod 不是质数时不能随便套费马小定理。

4.8 计算几何

计算几何要先把对象保持在整数世界里。点和向量、叉积和点积、方向判断和线段相交是基础；凸包、旋转卡壳和扫描线则是 GDCPC 边界内最值得掌握的三个工具。

C++ 点结构：

struct Point {
    long long x, y;
    Point operator - (const Point &o) const { return {x - o.x, y - o.y}; }
};

long long cross(Point a, Point b) {
    return a.x * b.y - a.y * b.x;
}

long long dot(Point a, Point b) {
    return a.x * b.x + a.y * b.y;
}

几何题的策略是尽量离散化、排序化、单调化。

几何题的策略是尽量离散化、排序化、单调化。水平/竖直线段交点通常用扫描线加 Fenwick 或平衡树；凸多边形直径用旋转卡壳；方向比较用叉积；距离最值用平方距离避免浮点误差。2024 A 田字格是水平线段和竖直线段的结构题，入口是扫描线统计交点或关系；2023 M 计算几何是凸多边形切分，入口是凸性和旋转卡壳。坐标到 1e9 时，叉积用 long long 或 __int128，比较距离用平方，浮点输出保留足够精度。GDCPC 备考不需要系统学习半平面交和三维几何，但叉积、线段相交、凸包、旋转卡壳必须会。

4.9 剪枝

剪枝条件必须是充分条件：被剪掉的分支不可能产生合法解或更优解。

常用剪枝包括可行性剪枝、上界剪枝、下界剪枝、重复状态剪枝和对称性剪枝。可行性剪枝用于当前状态已经违反限制；上界剪枝用于当前收益加上最大可能收益仍不超过最优解；下界剪枝用于当前代价加上最小可能代价已经不优；重复状态剪枝在同状态下保留最优代价；对称性剪枝只保留等价分支中的一个代表。

剪枝是在搜索树里跳过确定没有奖励的支线。不能因为“看起来不顺眼”就剪，必须能证明该支线不会通向合法解或更优解。否则剪枝会从优化变成自毁，表面上少搜了很多，实际上把答案也一起丢进了纸箱。

0/1 搜索上界剪枝：

def branch_bound(value, weight, limit):
    n = len(value)
    suffix = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix[i] = suffix[i + 1] + value[i]

    best = 0

    def dfs(i, w, v):
        nonlocal best
        if w > limit:
            return
        if v + suffix[i] <= best:
            return
        if i == n:
            best = max(best, v)
            return
        dfs(i + 1, w + weight[i], v + value[i])
        dfs(i + 1, w, v)

    dfs(0, 0, 0)
    return best

剪枝不是替代正解的借口。它适合小规模题、构造题、暴力对拍和搜索型模拟，也适合在推规律时缩小枚举范围。剪枝一旦进入正式解法，就必须给出充分性证明。广井前辈可以生活混乱，搜索树不行。

正确剪枝的证明格式：

当前状态 S。
定义上界/下界 B(S)。
若 B(S) 不可能优于当前答案，则 S 的所有后继都不可能优于当前答案。
因此剪掉 S 不影响最优解。

4.10 对拍

对拍是训练和赛前调试中最稳定的查错方法。它不证明算法正确，但能高效发现状态遗漏、边界错误、贪心反例和构造非法输出。

对拍由四个角色构成。brute 是暴力解，只处理小规模，逻辑尽量贴近题意定义；solve 是你准备提交的算法；gen 负责生成随机或枚举小数据；compare 负责比较结果，普通题直接比答案，构造题调用 checker。四者分工明确，调错时才不会互相污染。

不同题型的暴力写法也有章法。排列、交换和切分题可以枚举所有排列或所有操作位置；DP 与计数题可以 DFS 枚举所有方案；图论题用小图 Floyd、BFS 或枚举边集；字符串题枚举子串、子序列或位置集合；几何题把坐标压到很小，暴力枚举点、线段和切分方式。暴力解不追求快，只追求忠于定义。它像平时不起眼的记录本，赛场外却能把正解里最隐蔽的谎话翻出来。

有些题不适合直接比较输出。special judge 的输出不唯一，只能用 checker；浮点题需要误差比较；期望题的小规模验证应当精确枚举，不能用随机模拟近似；交互题则要改写成离线判定器。

Python 单文件对拍

import random

def brute(a):
    n = len(a)
    best = -10**30
    for l in range(n):
        s = 0
        for r in range(l, n):
            s += a[r]
            best = max(best, s)
    return best

def solve(a):
    best = -10**30
    cur = 0
    for x in a:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

def gen_case():
    n = random.randint(1, 8)
    return [random.randint(-5, 5) for _ in range(n)]

for seed in range(10000):
    random.seed(seed)
    data = gen_case()
    a = brute(data)
    b = solve(data)
    if a != b:
        print("Wrong answer")
        print("seed =", seed)
        print("data =", data)
        print("brute =", a)
        print("solve =", b)
        break
else:
    print("Accepted by stress test")

这段代码用最大子段和演示：暴力是 O(n^2)，正解是 Kadane。对拍时只生成小 n，因为暴力只负责“可靠”，不负责“快”。

C++ 双程序对拍

常规流程：

gen.exe > input.txt
brute.exe < input.txt > brute.txt
main.exe < input.txt > main.txt
比较 brute.txt 和 main.txt

PowerShell：

for (i = 1;i -le 10000; i++) {
    .\gen.exei > input.txt
    .\brute.exe < input.txt > brute.txt
    .\main.exe < input.txt > main.txt
    fc brute.txt main.txt
    if (LASTEXITCODE -ne 0) {
        Write-Host "Wrong at seedi"
        break
    }
}

C++ 生成器：

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char **argv) {
    int seed = argc > 1 ? atoi(argv[1]) : 1;
    mt19937 rng(seed);

    int n = uniform_int_distribution<int>(1, 8)(rng);
    cout << n << '\n';
    for (int i = 0; i < n; ++i) {
        int x = uniform_int_distribution<int>(-5, 5)(rng);
        cout << x << (i + 1 == n ? '\n' : ' ');
    }
    return 0;
}

暴力解设计

暴力解要慢但可信。写法越接近题意越好。

子序列计数暴力：

def brute_distinct_loose_subseq(s, k):
    n = len(s)
    seen = set()

    def dfs(pos, last, cur):
        if pos == n:
            if cur:
                seen.add(cur)
            return
        dfs(pos + 1, last, cur)
        if last == -1 or pos - last > k:
            dfs(pos + 1, pos, cur + s[pos])

    dfs(0, -1, "")
    return len(seen)

对拍 2025 H 时，令 n<=12，把正解结果与该暴力比较。若小数据都过，再考虑大规模复杂度。

构造题 checker

构造题输出不唯一，不能比较输出文本。

禁止子段和 checker：

def check_no_subarray_sum(ans, a, b, n, s):
    if len(ans) != n:
        return False
    pref = 0
    seen = {0}
    for x in ans:
        if x != a and x != b:
            return False
        pref += x
        if pref - s in seen:
            return False
        seen.add(pref)
    return True

固定格网格染色 checker：

def check_grid_fixed(original, ans):
    if len(original) != len(ans):
        return False
    for row0, row1 in zip(original, ans):
        if len(row0) != len(row1):
            return False
        for x, y in zip(row0, row1):
            if x != 0 and x != y:
                return False
            if y <= 0:
                return False
    return True

数据生成策略

生成器必须覆盖反常数据。最小规模如 n=1、空边、单点，极端值如 0、1、最大值和负数，重复结构如全相等和大量重复，单调结构如递增递减，图结构如链、环、完全图、森林和重边，字符串结构如全同、全不同、周期串和回文串，事件题还要覆盖同一时间多事件、永不触发和初始触发。随机生成不是只生成“看起来正常”的数据。很多 bug 只会在全 0、重边、同时间、负权、空集合这种反派角色登场时暴露。

失败定位

对拍失败后：

1. 固定 seed。
2. 打印输入。
3. 确认暴力解正确。
4. 缩小数据。
5. 打印中间状态。
6. 抽取失败模式。
7. 加入回归测试。

回归测试记录：

case:
input:
expected:
bug:
fix:

4.11 提交前自测

提交前自测的目标是在 3-5 分钟内排除低级错误。它不是完整证明，而是最终安全检查。

最小自测集

任何题至少测：

1. 样例。
2. 最小规模。
3. 最大规模的缩小版。
4. 全相同。
5. 严格递增/递减。
6. 随机小数据。
7. 题型特殊边界。

按题型扩展：

题型	必测
图论	非连通、重边、自环、链、环
DP	空状态、只有一个元素、全不可行
字符串	全同、全不同、周期串、无匹配
数学	0、1、质数、合数、模边界
构造	checker 跑输出
几何	共线、重合、极大坐标
浮点	整数答案、小数答案、误差边界

C++ 自测工具

本地调试宏：

#ifdef LOCAL
#define debug(x) cerr << #x << " = " << (x) << '\n'
#else
#define debug(x) ((void)0)
#endif

边界断言：

assert(1 <= idx && idx <= n);

提交前要关闭大量 cerr、文件重定向和固定随机输出。assert 可以辅助本地定位，但不能让程序正确性依赖 assert；正式提交时，核心逻辑必须在没有断言的情况下仍然成立。不要等加艾露查岗时才发现珈百璃还在游戏里，提交前就把调试痕迹清掉。

Python 自测工具

基础读入：

import sys
input = sys.stdin.buffer.readline

递归题：

sys.setrecursionlimit(1_000_000)

大量输出：

out = []
for ans in answers:
    out.append(str(ans))
sys.stdout.write("\n".join(out))

Python 提交前尤其要检查输入和对象开销。大输入使用 sys.stdin.buffer.readline，大循环避免切片和重复复制大列表，字典 key 必须可哈希，递归题必须设置安全的递归深度。若复杂度已经贴近上限，不要硬用 Python 赌评测机心情。

Special Judge 自测

流程：

生成输入
运行程序得到输出
checker(input, output)

checker 至少检查输出数量、值域、固定条件和目标条件。若程序输出无解，小数据下还要用暴力确认确实无解。special judge 题最怕“输出格式看起来像样例”，但少了某个硬条件。

常见事故表

事故	原因	自测
样例过，提交 WA	漏边界	最小、全同、极端
RE	数组越界或递归爆栈	assert、小最大测试
TLE	复杂度误判	放大数据
MLE	DP 数组过大	估算内存
PE	输出缺行	检查输出数量
浮点 WA	精度不足	输出 12 位以上
构造 WA	输出不合法	checker

内存估算

C++：

int: 4 bytes
long long: 8 bytes
double: 8 bytes
1e6 long long ≈ 8 MB
1e7 int ≈ 40 MB

Python 对象开销大，不能按 C++ 数组估算。大规模数字列表尽量避免多份复制；必要时改用 C++。

提交前 60 秒清单

最后 60 秒只做低风险检查，不做大重构。确认多测已处理、数组已清空、下标体系统一；确认 long long、mod 和 INF 没有选错；确认 Dijkstra 没有负边，Tarjan 已处理重边；确认构造输出经过 checker；若使用 Python，再看一眼输入速度、递归深度和复杂度余量。

记忆锚点：提交前自测不是水群前的仪式感，是最后一次确认机体没有少装零件。

5. 样章：从真题到算法

本章不按“知识点标签”讲题，而按真实解题路径讲：为什么这样建模，代码写在哪里，边界如何自测。

5.1 2025 A 矩阵游戏：从行列翻转到状态压缩

矩阵游戏的题面给出的信号很集中：元素只有 0/1，操作是整行翻转和整列翻转，列数很小而行数可能很大，每个格子的贡献还可能有正有负。这四件事合在一起，几乎是在提醒你把翻转写成异或，并把列翻转压成一个 mask。

翻转在二进制里就是异或。设第 i 行是否翻转为 r_i，第 j 列是否翻转为 c_j，原值为 a_ij，最终值为：

b_ij = a_ij xor r_i xor c_j

所有列翻转状态合起来就是一个 mask。如果固定了 mask，每一行之间不再互相影响：第 i 行只剩两个选择，翻或不翻。于是问题变成：

枚举列 mask
  每行独立取 max(不翻贡献, 翻转贡献)

正确性来自枚举与独立性。任意合法方案都有一个列翻转集合 mask；固定 mask 后，行翻转只影响本行，不再影响其他行；于是每行独立取最大值不会破坏别的选择。枚举全部 mask 后，最优方案必然被覆盖。

C++：

long long solve_matrix_game(int n, int m, long long A, long long B, const vector<string> &grid) {
    vector<vector<long long>> w(n, vector<long long>(m));
    vector<long long> row_sum(n, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            w[i][j] = A * (i + 1) + B * (j + 1);
            row_sum[i] += w[i][j];
        }
    }

    long long ans = LLONG_MIN;
    for (int mask = 0; mask < (1 << m); ++mask) {
        long long total = 0;
        for (int i = 0; i < n; ++i) {
            long long keep = 0;
            for (int j = 0; j < m; ++j) {
                int bit = grid[i][j] - '0';
                bit ^= (mask >> j) & 1;
                if (bit) keep += w[i][j];
            }
            total += max(keep, row_sum[i] - keep);
        }
        ans = max(ans, total);
    }
    return ans;
}

本题的边界很短，但都要命。权值可能为负，答案初值不能设为 0；A*i+B*j 和总和使用 64 位；如果列数不是小参数，这套枚举列状态的解法就会失效。

小规模暴力对拍：

def brute_matrix_game(n, m, A, B, grid):
    ans = -10**30
    for rm in range(1 << n):
        for cm in range(1 << m):
            cur = 0
            for i in range(n):
                for j in range(m):
                    bit = int(grid[i][j])
                    bit ^= (rm >> i) & 1
                    bit ^= (cm >> j) & 1
                    if bit:
                        cur += A * (i + 1) + B * (j + 1)
            ans = max(ans, cur)
    return ans

5.2 2025 F 排名预测：从封榜提交到多重选择背包

排名预测的题面同时给出规则和规模：ICPC 排名先比题数，再比罚时；封榜后提交结果未知；题数 n<=15；目标是求最少封榜后通过多少题才能排名严格更高。这里真正的小参数是题数，每一道题都可以被拆成一个互斥选项组。

一个未在封榜前 AC 的题有多个互斥未来：不过，或第 1 次封榜提交 AC，或第 2 次封榜提交 AC。每道题形成一个选项组。把所有题的选项组合起来，就是多重选择背包。

状态：

dp[solved][post] = 达到 solved 题，封榜后 AC post 题时的最小罚时

为什么状态里不需要记录每道题：每道题只处理一次；已处理题对未来的影响只剩总题数、封榜后题数和罚时。相同 (solved, post) 下，罚时越小越优。

Python 3.12：

INF = 10**30

def merge_problem_options(n, base_solved, base_penalty, groups):
    dp = [[INF] * (n + 1) for _ in range(n + 1)]
    dp[base_solved][0] = base_penalty

    for opts in groups:
        ndp = [row[:] for row in dp]
        for solved in range(n + 1):
            for post in range(n + 1):
                cur = dp[solved][post]
                if cur == INF:
                    continue
                for add_solved, add_post, add_penalty in opts:
                    ns = solved + add_solved
                    np = post + add_post
                    if ns <= n and np <= n:
                        ndp[ns][np] = min(ndp[ns][np], cur + add_penalty)
        dp = ndp
    return dp

答案扫描：

def min_post_ac_to_beat(dp, our_solved, our_penalty):
    n = len(dp) - 1
    ans = n + 1
    for solved in range(n + 1):
        for post in range(n + 1):
            penalty = dp[solved][post]
            if penalty >= INF:
                continue
            if solved > our_solved or (solved == our_solved and penalty < our_penalty):
                ans = min(ans, post)
    return -1 if ans == n + 1 else ans

罚时题的边界必须严格尊重赛制。已 AC 题的后续提交不影响首次 AC；同一分钟提交按输入顺序处理；未 AC 题的错误提交会影响之后 AC 的罚时；“封榜后过几题”统计的是题数，不是提交次数。

这题不是“背包题长得像背包题”，而是把每题未来可能结果压成选项组。很多中档 DP 都是这样：剧情复杂，但每集处理完，只留下几个会影响结局的变量。

5.3 2025 H 松散子序列：为什么 last 去重不可少

松散子序列的题面有两个核心限制：它要求本质不同子序列，又要求相邻选中位置在原串中至少隔开 k 个位置。字符集只有小写字母，答案对模数取值。去重和距离限制必须同时进入状态，否则不是重复计数，就是把不合法的相邻位置接上。

普通子序列计数会重复。例如 aa 的非空子序列按位置有两个 "a"，但本质不同只有一个 "a"。因此必须去重。

设：

total[i] = 前 i 个字符能形成的本质不同非空松散子序列数
last[c] = 上一次以字符 c 结尾时已经贡献过的来源数量

处理第 i 个字符时，它可以单独成序列，也可以接在某个合法旧序列后面。由于相邻位置要相隔超过 k，旧序列最后位置必须在 i-k-1 之前：

base = 1 + total[i-k-1]
add = base - last[c]
last[c] = base

Python：

def count_distinct_loose_subseq(s, k, mod=998244353):
    n = len(s)
    total = [0] * (n + 1)
    last = [0] * 26
    for i, ch in enumerate(s, 1):
        prev = i - k - 1
        base = 1
        if prev >= 0:
            base = (base + total[prev]) % mod
        c = ord(ch) - ord('a')
        add = (base - last[c]) % mod
        total[i] = (total[i - 1] + add) % mod
        last[c] = base
    return total[n]

正确性来自“新增序列的结尾”。处理当前位置时，所有新增序列都以当前字符结尾；base 枚举全部可接来源，并包含单字符序列。同一结尾字符的旧位置已经产生过一批同名序列，新位置会覆盖这批贡献，因此用 last[c] 记录上次覆盖量，再从当前 base 中减掉即可。

暴力对拍：

def brute_distinct_loose_subseq(s, k):
    n = len(s)
    seen = set()
    def dfs(pos, last_pos, cur):
        if pos == n:
            if cur:
                seen.add(cur)
            return
        dfs(pos + 1, last_pos, cur)
        if last_pos == -1 or pos - last_pos > k:
            dfs(pos + 1, pos, cur + s[pos])
    dfs(0, -1, "")
    return len(seen)

训练时令 n<=12 随机生成字符串，对拍 1000 组。DP 题不是写完就信，存档点系统也要验档。

5.4 2025 J 解谜比赛：事件图不是普通最短路，但长得像

解谜比赛的题面有明显的事件系统味道：每个点有阈值，点解锁后沿出边延迟传能，强制刷新器会在指定时间改变阈值，最后要求每个点的最早解锁时间。这不是普通 Dijkstra，因为边不是“走过去就到达”，而是能量累计到阈值后才触发。

这不是普通 Dijkstra，因为边不是走过去就到达。点需要收到足够多能量才会触发。但它仍然有 Dijkstra 的骨架：事件按时间从小到大处理，某个点第一次解锁就是最早时间。

事件模型：

事件 = (时间, 类型, 点)
类型：解锁候选 / 能量到达

处理逻辑：

push 初始解锁候选
push 刷新器解锁候选
while pq:
    取最早事件
    若能量到达：累计能量，达到阈值则 push 解锁候选
    若解锁候选：若未解锁，标记时间并沿出边产生能量到达

Python 骨架：

from heapq import heappush, heappop

def event_unlock(n, need, graph, forced):
    got = [0] * (n + 1)
    ans = [-1] * (n + 1)
    pq = []

    for u in range(1, n + 1):
        if need[u] == 0:
            heappush(pq, (0, 0, u))

    for t, nodes in forced:
        for u in nodes:
            heappush(pq, (t, 0, u))

    while pq:
        time, typ, u = heappop(pq)
        if typ == 1:
            if ans[u] != -1:
                continue
            got[u] += 1
            if got[u] >= need[u]:
                heappush(pq, (time, 0, u))
            continue

        if ans[u] != -1:
            continue
        ans[u] = time
        for v, w in graph[u]:
            if ans[v] == -1:
                heappush(pq, (time + w, 1, v))
    return ans[1:]

这段是事件图骨架。真实题解要按题面精确处理刷新器对阈值的修改。

事件图的边界是时间顺序和一次性。点只能解锁一次；多个事件同一时间进入优先队列不破坏正确性；刷新器管控点的总数量可能很大，必须按总输入规模存储；永不解锁的点输出 -1。这类题像阿尼亚的秘密行动：每个事件都很热闹，但记录本上只认最早那一次。

5.5 构造题：checker 比样例更可靠

构造题输出不唯一。样例只是一条合法路线，不是唯一剧情线。

以禁止子段和为 s 的序列构造为例：

构造 c[i] in {a,b}
不存在 l,r 使 sum(c[l..r]) = s

转化：

sum(l..r)=s <=> prefix[r]-prefix[l-1]=s

新增前缀和 np 时，只要历史前缀和集合中存在 np-s，就产生非法子段。

checker：

def check_no_subarray_sum(ans, a, b, n, s):
    if len(ans) != n:
        return False
    pref = 0
    seen = {0}
    for x in ans:
        if x != a and x != b:
            return False
        pref += x
        if pref - s in seen:
            return False
        seen.add(pref)
    return True

若程序输出无解，小数据用暴力确认：

def brute_exists(a, b, n, s):
    ans = []
    def dfs(pos):
        if pos == n:
            return check_no_subarray_sum(ans, a, b, n, s)
        for x in (a, b):
            ans.append(x)
            if dfs(pos + 1):
                return True
            ans.pop()
        return False
    return dfs(0)

构造题的证明和 checker 是两把刀。证明负责说服人，checker 负责殴打代码。

5.6 2024 B 腊肠披萨：前缀、后缀与 Border 的正名

腊肠披萨给了很多字符串，总长度达到百万级，核心对象是最长公共前后缀，答案是所有有序字符串对的贡献和。规模已经说明不能逐对比较，O(L^2) 会直接退场；定义则说明不能把它当普通 LCP 或最长公共子串。

这类题最容易误读。“最长公共前后缀”不是两个字符串的最长公共子串，也不是最长公共前缀。它要求一个字符串同时满足：

t 是 s_i 的前缀
t 是 s_j 的后缀

单对字符串可以用 KMP 检验。把 a 的前缀和 b 的后缀接在一起看，常用写法是：

a + "#" + b

该串的最后一个前缀函数值，就是 a 的最长前缀与 b 的后缀的匹配长度。分隔符必须不在原字符集内，否则会把两边误接起来。

def prefix_function(s: str) -> list[int]:
    pi = [0] * len(s)
    for i in range(1, len(s)):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi

def lcps_len(a: str, b: str) -> int:
    t = a + "#" + b
    return prefix_function(t)[-1]

这段代码是显微镜，不是整题正解。它负责确认定义，适合做暴力对拍。真正面对总长 3e6 时，必须把“很多前缀”和“很多后缀”统一处理：前缀进入 Trie，后缀通过反串或自动机查询，贡献按最大匹配长度统计。此时你不再逐对看字符串，而是让所有字符串在一棵结构里相遇。

多串题的基本压缩是把每个前缀看成 Trie 上的节点。若某个节点深度为 d，它代表一个长度为 d 的前缀。一个字符串 s_j 的后缀若走到这个节点，说明所有经过该节点的字符串 s_i 都至少有一个长度为 d 的公共前后缀。为了得到“最长”，需要让更深节点覆盖更浅节点；这就是为什么这题不适合只统计“出现过多少次”，而要处理最大深度。

Trie 代码骨架：

struct Trie {
    struct Node {
        int nxt[26];
        int depth;
        int pass;
        Node() : depth(0), pass(0) {
            fill(nxt, nxt + 26, -1);
        }
    };

    vector<Node> tr;

    Trie() { tr.push_back(Node()); }

    int insert_prefixes(const string &s) {
        int u = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (tr[u].nxt[c] == -1) {
                tr[u].nxt[c] = (int)tr.size();
                tr.push_back(Node());
                tr.back().depth = tr[u].depth + 1;
            }
            u = tr[u].nxt[c];
            tr[u].pass++;
        }
        return u;
    }
};

真题落代码时要注意三件事。

第一，LCPS(s_i,s_i) 也可能被计入，必须看清题面是否排除 i=j。样例若把自身也计入，整串长度会贡献 C^{|s_i|}；漏掉这一项，答案会像阿卡林一样悄悄消失。

第二，空串的贡献要按题面公式处理。如果贡献是 C^len，空匹配贡献 1；如果贡献是 len^C，空匹配贡献 0。样例里的空项往往就是用来抓这个边界的。

第三，模数 P 小于 2^30，乘法用 64 位安全，但累加时仍要及时取模。

用于对拍的暴力：

def brute_lcps_sum(words, c, mod):
    ans = 0
    for a in words:
        for b in words:
            d = lcps_len(a, b)
            ans = (ans + pow(c, d, mod)) % mod
    return ans

训练方式：先用暴力把定义钉牢，再写 Trie/自动机方向的正解。字符串题一旦定义错，后面代码越优化，错得越有速度。

5.7 2024 F 图：边不相交路径与桥

这道题给的是无向图，要求输出若干条边不相交路径，输入允许重边、不允许自环，并且是 special judge。四个条件合在一起，真正的入口就是桥、边双和输出验证。

“边不相交”这四个字的第一反应应当是桥和边双连通。若一条边是桥，任何跨过它的两点路径都必须经过它；若删去所有桥后两个点仍在同一块中，它们之间至少有两条边不相交路径。这个结论是无向图中 Menger 定理在边连通场景下的常用竞赛版本。

判断桥必须使用边编号。重边是这题给出的明确信号，也是 Tarjan 最常见的坑。若 DFS 时只写 if (v == parent) continue，两条平行边会被你合并成一条，桥判断立刻失真。

struct Edge {
    int to;
    int id;
};

void tarjan_bridge(int u, int parent_edge,
                   const vector<vector<Edge>> &g,
                   vector<int> &dfn,
                   vector<int> &low,
                   vector<int> &bridge,
                   int &timer) {
    dfn[u] = low[u] = ++timer;
    for (auto e : g[u]) {
        int v = e.to;
        if (e.id == parent_edge) continue;
        if (!dfn[v]) {
            tarjan_bridge(v, e.id, g, dfn, low, bridge, timer);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) bridge[e.id] = 1;
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

删桥后的连通块可以用 DFS 染色：

void paint_component(int u, int color,
                     const vector<vector<Edge>> &g,
                     const vector<int> &bridge,
                     vector<int> &comp) {
    comp[u] = color;
    for (auto e : g[u]) {
        if (bridge[e.id]) continue;
        if (!comp[e.to]) paint_component(e.to, color, g, bridge, comp);
    }
}

special judge 的题还要会验证输出。路径 checker 的最小标准：

def check_edge_disjoint_paths(n, edge_list, s, t, paths):
    edge_id = {}
    for idx, (u, v) in enumerate(edge_list):
        if u > v:
            u, v = v, u
        edge_id.setdefault((u, v), []).append(idx)

    used = set()
    for path in paths:
        if not path or path[0] != s or path[-1] != t:
            return False
        for a, b in zip(path, path[1:]):
            x, y = (a, b) if a < b else (b, a)
            if (x, y) not in edge_id:
                return False
            chosen = None
            while edge_id[(x, y)]:
                cand = edge_id[(x, y)].pop()
                if cand not in used:
                    chosen = cand
                    break
            if chosen is None:
                return False
            used.add(chosen)
    return True

这段 checker 特意保留重边。若输入有三条 1-4，输出三条只含 1 4 的路径可以合法；边不相交指边编号不同，不是端点对不同。这里要像夏音照顾小依、虹夏照顾乐队一样细，少照顾一次，代码就会摔。

完整构造通常分两步。先在某个无桥连通块中找候选点对，再在 DFS 树和返祖边上恢复多条路径。若赛时无法立即写出完整构造，也要先写判断和 checker；special judge 题最怕“我觉得这样输出应该行”。构造题没有“应该”，只有条件逐条成立。

5.8 2023 L 经典问题：完全图不一定要建出来

经典问题看似给了一张完全图，但点数 n 可达 1e9，只有 m 条边被三元组特殊指定，普通边权是 |x-y|，目标是 MST。这样的规模已经把显式建完全图排除掉，真正的模型是一条数轴加少量特殊边。

看到完全图不要急着建边。这里真正的图不是 n(n-1)/2 条边，而是一条数轴加少量特殊边。普通边权 |x-y| 有强结构：从 x 到 y 沿着相邻点走，代价也是 y-x。因此很多普通长边不会比一串相邻边更有用。特殊边打破了这条数轴的局部结构，算法的任务就是在“数轴骨架”和“特殊捷径/障碍”之间做 Kruskal。

最朴素的思想是把所有相邻边和特殊边丢进 Kruskal。但 n 太大，不能枚举 1..n-1。压缩的关键是：只有特殊边端点附近的相邻关系可能影响选择；远离特殊端点的一整段连续普通边可以合并成一条“区间代价”。这类题的训练价值就在这里：不是见到 MST 就排序所有边，而是先问哪些边可能进入最小生成树。

用于小规模对拍的完整 Kruskal：

class DSU:
    def __init__(self, n):
        self.fa = list(range(n))
    def find(self, x):
        while self.fa[x] != x:
            self.fa[x] = self.fa[self.fa[x]]
            x = self.fa[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        self.fa[rb] = ra
        return True

def brute_mst_complete(n, special):
    mp = {(u, v): w for u, v, w in special}
    edges = []
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            edges.append((mp.get((i, j), j - i), i - 1, j - 1))
    edges.sort()
    dsu = DSU(n)
    ans = 0
    for w, u, v in edges:
        if dsu.union(u, v):
            ans += w
    return ans

这个暴力只用于 n<=60 对拍。正解写法应当围绕候选边压缩：所有特殊边必须保留，特殊端点及其相邻坐标进入压缩点，压缩点之间用坐标差表示连续普通边，没有任何特殊端点覆盖的长区间则把普通链代价直接累加。

C++ 中候选坐标的收集方式：

vector<long long> xs;
auto add_coord = [&](long long x, long long n) {
    if (1 <= x && x <= n) xs.push_back(x);
};

for (auto [u, v, w] : special_edges) {
    for (long long d = -1; d <= 1; ++d) {
        add_coord(u + d, n);
        add_coord(v + d, n);
    }
}
add_coord(1, n);
add_coord(n, n);

sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());

把坐标压缩后，普通边不再是一条条原始边，而是相邻压缩坐标之间的区间连接，权值是坐标差。特殊边按压缩后的端点加入。然后运行 Kruskal。

struct E {
    long long w;
    int u, v;
    bool operator < (const E &other) const {
        return w < other.w;
    }
};

这份写法的边界在“特殊边覆盖相邻点”。若 (x,x+1) 被特殊权值覆盖，普通权值 1 不再存在；候选边生成时不能把它又当成普通相邻边塞回去。样例第一组正是这种陷阱：(1,2) 和 (2,3) 被高权值覆盖，真正便宜的连接可能绕开它们。

本题的思想比代码更重要：完全图只是叙述，数轴结构才是模型。遇到 n 巨大而特殊信息很少的图题，先找“默认结构”和“异常结构”。默认结构能公式化，异常结构才进数据结构。

5.9 2023 M 计算几何：凸多边形的直径

计算几何这一题的关键信号是：顶点按逆时针给出，多边形凸，要用两点连线切成两个面积为正的小多边形，目标涉及两个小多边形直径平方和。凸性把“任意两点距离最大”压到顶点对，逆时针顺序给了旋转卡壳的基础。

几何题先保整数。直径的平方可以用坐标差平方表示，不需要开根号。凸多边形的直径一定由一对顶点取得；这个结论让问题从“多边形内部任意两点”落回到顶点对。

点结构：

struct Point {
    long long x, y;
};

Point operator - (Point a, Point b) {
    return {a.x - b.x, a.y - b.y};
}

long long cross(Point a, Point b) {
    return a.x * b.y - a.y * b.x;
}

long long dist2(Point a, Point b) {
    long long dx = a.x - b.x;
    long long dy = a.y - b.y;
    return dx * dx + dy * dy;
}

凸多边形直径用旋转卡壳。直觉是：当一条边沿多边形转动时，与它最远的点不会反向跳回去，只会单调前进。这个“单调”就是几何题最宝贵的秩序，像枫前辈带登山队，大家一段一段往前走，不会突然传送回山脚。

long long convex_diameter2(const vector<Point> &p) {
    int n = (int)p.size();
    if (n == 1) return 0;
    if (n == 2) return dist2(p[0], p[1]);

    int j = 1;
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        int ni = (i + 1) % n;
        while (true) {
            int nj = (j + 1) % n;
            long long cur = llabs(cross(p[ni] - p[i], p[j] - p[i]));
            long long nxt = llabs(cross(p[ni] - p[i], p[nj] - p[i]));
            if (nxt > cur) j = nj;
            else break;
        }
        ans = max(ans, dist2(p[i], p[j]));
        ans = max(ans, dist2(p[ni], p[j]));
    }
    return ans;
}

真题要枚举切割用的两点。若两点相邻，切不开面积为正的两个多边形；若所有点共线也不合法，但题面保证原凸多边形面积为正。枚举一条对角线后，两侧各是一段环形顶点序列，分别求直径，取平方和最小。

小规模验证可以用朴素直径：

def diameter2_bruteforce(poly):
    ans = 0
    for i, (x1, y1) in enumerate(poly):
        for x2, y2 in poly[i + 1:]:
            ans = max(ans, (x1 - x2) ** 2 + (y1 - y2) ** 2)
    return ans

几何题的边界必须保守。坐标到 1e9，距离平方到 1e18，C++ 用 long long；若叉积表达式还要参与更大乘法，改用 __int128。输入可能有三点共线，旋转卡壳中 > 与 >= 的选择会影响是否跳过同面积点，但直径最大值不能漏。判断“面积为正”时用叉积或顶点数量，不要用浮点面积。Python 适合写对拍和暴力，正式大数据几何建议使用 C++。几何代码要像智乃拉咖啡一样稳，不能靠“差不多”调味。

几何不是玄学。它只是把“大小关系”藏进叉积，把“最远”藏进单调。把这两件事找出来，题面就不再像一张看不懂的地图。

6. 五年真题训练索引

本章的表格只负责定位，表格后面的讲读负责训练。使用这一章时不要把题目记成“某某题等于某算法”，而要记成一个更短的动作链：

题面限制 -> 可计算对象 -> 循环顺序/数据结构 -> 边界样例 -> 真题代码落点

如果一个变量在推导里没有进入状态，也没有进入转移，它就是“阿卡林变量”：名字还在，存在感已经没了。删掉它，模型会更清楚。

6.1 入门档

题目	核心
2023 A 算法竞赛	日期/计数模拟
2025 D 生成魔咒	数位贪心
ZJ2026 H ucup-team7610	字符串格式
ZJ2026 I 飞行艇	排序贪心
2024 G Menji 和 gcd	数论观察

入门题不等于“随便写”。这类题的价值在于训练把自然语言规则拆成函数。日期题要先确定计数单位，字符串格式题要先确定合法字符和输出格式，数位贪心题要先确定每一位决策对后续是否独立。小埋在外面是完美女高中生，回家后才变成干物妹；签到题也常常是样例温顺、边界发癫，不能只看外表。

日期/计数模拟的代码应当把“是否为目标日”单独写成函数，而不是把一堆判断塞进主循环。这样做不是形式主义，而是为了在赛场上快速检查闰年、月份长度、左右端点是否包含。

def is_leap(y: int) -> bool:
    return y % 400 == 0 or (y % 4 == 0 and y % 100 != 0)

def month_days(y: int, m: int) -> int:
    md = [31, 28 + is_leap(y), 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    return md[m - 1]

def count_days(y1, m1, d1, y2, m2, d2, ok):
    ans = 0
    y, m, d = y1, m1, d1
    while (y, m, d) <= (y2, m2, d2):
        ans += ok(y, m, d)
        d += 1
        if d > month_days(y, m):
            d = 1
            m += 1
        if m == 13:
            m = 1
            y += 1
    return ans

排序贪心题的第一行通常不是排序，而是写出交换论证：若两个相邻对象 x,y 的顺序可以比较，且 x,y 换成 y,x 不会更优，则排序关键字成立。落代码时只保留比较器需要的信息，不要把题面所有字段都背进结构体。可靠姐姐型写法是“先把对象收拾干净，再让主循环只做一件事”。

struct Item {
    long long key;
    long long cost;
};

long long greedy_order(vector<Item> a) {
    sort(a.begin(), a.end(), [](const Item &x, const Item &y) {
        return x.key < y.key;
    });
    long long cur = 0, ans = 0;
    for (auto &e : a) {
        cur += e.cost;
        ans = max(ans, cur - e.key);
    }
    return ans;
}

数论观察题要先枚举小数据。gcd、倍数、整除、奇偶这些词出现时，先用暴力生成 1..30 的表，比盯着题面硬想更稳。炮姐的硬币飞出去前已经确定轨道；数论题的性质通常也藏在小表里，只是需要你把它打出来。

6.2 中档档

题目	核心
2025 A 矩阵游戏	状态压缩 + 行独立
2025 F 排名预测	多重选择背包
2025 H 松散子序列	前缀 DP + 去重
2024 C DFS 序	树上贪心
2024 B 腊肠披萨	Border / KMP
2023 B 基站建设	约束转化 + 贪心/数据结构
2023 L 经典问题	MST 建模
2022 E 黑白大陆	连通块/网格

中档题的共同点是“题面还有现实含义，但代码已经必须抽象”。训练时应按模型分类。

状态压缩题的信号是小参数。2025 A 的列数小，所以列翻转可以枚举；2025 F 的题数小，所以每题的未来结果可以合并成背包；窄网格题的宽度小，所以截面状态可以保存。这里的关键不是“看到小就二进制”，而是固定小参数后，其余部分是否独立。2025 A 固定列 mask 后，每一行像芝麻凛独自露营：互不打扰，每行只需要选翻或不翻。

for (int mask = 0; mask < (1 << m); ++mask) {
    long long total = 0;
    for (int i = 0; i < n; ++i) {
        long long keep = 0;
        for (int j = 0; j < m; ++j) {
            int bit = a[i][j] ^ ((mask >> j) & 1);
            if (bit) keep += w[i][j];
        }
        total += max(keep, row_sum[i] - keep);
    }
    ans = max(ans, total);
}

背包题的建模边界是“每组只能选一个”。排名预测中，一道题的封榜后结果有若干可能：不过、某次提交通过、另一时刻通过。这些可能互斥，所以它不是普通 0/1 背包，而是多重选择背包。代码中外层循环题目，内层用新表 ndp，避免同一题被选多次。

INF = 10**30

def group_knapsack(n, groups, base_solved=0, base_penalty=0):
    dp = [[INF] * (n + 1) for _ in range(n + 1)]
    dp[base_solved][0] = base_penalty
    for opts in groups:
        ndp = [[INF] * (n + 1) for _ in range(n + 1)]
        for solved in range(n + 1):
            for post in range(n + 1):
                cur = dp[solved][post]
                if cur == INF:
                    continue
                for add_solved, add_post, add_penalty in opts:
                    ns, np = solved + add_solved, post + add_post
                    if ns <= n and np <= n:
                        ndp[ns][np] = min(ndp[ns][np], cur + add_penalty)
        dp = ndp
    return dp

字符串 Border 题的代码落点是 pi 数组。2024 B 和 2022 I 都不该用“找相同子串”的直觉处理；Border 必须同时是前缀和后缀。最长 Border 是 pi[n-1]，次长 Border 是 pi[pi[n-1]-1]，这条链就是题目的骨架。

def prefix_function(s: str) -> list[int]:
    pi = [0] * len(s)
    for i in range(1, len(s)):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi

def border_chain(s: str) -> list[int]:
    pi = prefix_function(s)
    res = []
    x = pi[-1] if s else 0
    while x:
        res.append(x)
        x = pi[x - 1]
    return res

网格连通题的边界是“颜色组件”，不是单个格子。2022 E 黑白大陆这类题先 BFS 压缩连通块，再在组件图上想操作次数。若直接对格子操作，状态规模和证明都会混乱。

from collections import deque

def components(grid):
    n, m = len(grid), len(grid[0])
    comp = [[-1] * m for _ in range(n)]
    colors = []
    cid = 0
    for i in range(n):
        for j in range(m):
            if comp[i][j] != -1:
                continue
            colors.append(grid[i][j])
            comp[i][j] = cid
            q = deque([(i, j)])
            while q:
                x, y = q.popleft()
                for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < n and 0 <= ny < m and comp[nx][ny] == -1 and grid[nx][ny] == grid[i][j]:
                        comp[nx][ny] = cid
                        q.append((nx, ny))
            cid += 1
    return comp, colors

6.3 困难档

题目	核心
2025 C 切牌	排列结构 + 动态维护
2025 J 解谜比赛	事件图 + 优先队列
2025 K 打字机	字符串周期
2025 L 路线选择	窄网格 DP
2024 F 图	边不相交路径构造
2024 J 另一个计数问题	数论图计数
2023 M 计算几何	凸多边形直径
ZJ2026 B 拜云台	区间桥 + 离线图
ZJ2026 C 回文串文回	期望 + 组合
ZJ2026 M Rounddog	LIS/LDS 偏序

困难题通常不是“会不会模板”，而是“能不能承认题面对象不该原样进代码”。2023 L 看起来是完全图 MST，若真建 O(n^2) 边就已经输在开场；2025 J 看起来是图最短路，但点的解锁依赖能量累计和刷新器，它更像事件系统；ZJ2026 C 看起来是回文字符串，核心却是随机排列与组合概率。题面像乃爱一样努力表现自己，但你不能被表演欲带跑。

事件图的落代码原则是：状态第一次确定时才扩展，所有未来影响进优先队列。若一个点能量增加但未达阈值，只更新累计值，不扩展出边；若刷新器把阈值改小，检查是否立刻触发。代码结构上至少要有三类容器：energy 保存当前能量，need 保存阈值，done 保存是否已经解锁。

from heapq import heappush, heappop

def unlock_times(n, need, graph, refresh_events):
    energy = [0] * n
    done = [False] * n
    ans = [-1] * n
    pq = []

    def try_unlock(t, u):
        if not done[u] and energy[u] >= need[u]:
            heappush(pq, (t, 0, u))

    for u in range(n):
        try_unlock(0, u)
    for t, u, new_need in refresh_events:
        heappush(pq, (t, 1, (u, new_need)))

    while pq:
        t, typ, data = heappop(pq)
        if typ == 1:
            u, new_need = data
            need[u] = min(need[u], new_need)
            try_unlock(t, u)
            continue
        u = data
        if done[u] or energy[u] < need[u]:
            continue
        done[u] = True
        ans[u] = t
        for v, add, delay in graph[u]:
            energy[v] += add
            try_unlock(t + delay, v)
    return ans

上面是事件图骨架，不是对某一真题的完整替代品。完整实现要按题面处理“刷新器管控多个点”“同一时刻多个能量事件”“阈值为 0 的初始点”等细节。边界检查必须包含：初始可解锁、永远不可解锁、同一秒多事件、重边、多刷新器管同一点。

边不相交路径题的模型是桥。无向图中，若 s,t 之间存在两条边不相交路径，则它们在删去所有桥后的同一连通块中。2024 F 的难点不止判断，还要输出路径；但判断部分必须先干净，否则构造会像小依做手工一样认真但到处漏胶。

struct Edge { int to, id; };

void dfs_bridge(int u, int pe, const vector<vector<Edge>> &g,
                vector<int> &tin, vector<int> &low, vector<int> &is_bridge, int &timer) {
    tin[u] = low[u] = ++timer;
    for (auto e : g[u]) {
        if (e.id == pe) continue;
        int v = e.to;
        if (!tin[v]) {
            dfs_bridge(v, e.id, g, tin, low, is_bridge, timer);
            low[u] = min(low[u], low[v]);
            if (low[v] > tin[u]) is_bridge[e.id] = 1;
        } else {
            low[u] = min(low[u], tin[v]);
        }
    }
}

这段代码的边界是重边。不能用 parent vertex 跳过父边，否则两点之间的平行边会被误判成桥；必须用边编号 id。这正是真题到代码最容易摔的地方。

期望题的落点是尾和公式或状态方程。ZJ2026 C 的随机过程可以理解为“随机排列所有位置，看到第几步回文条件满足”。如果某个对称位置对本来就相等，它不制造限制；如果不等，则至少要在这一对中改到足够位置。代码通常不会模拟随机，而是用组合数计算 P(T > t) 或 P(T <= t)。

E[T] = sum_{t>=0} P(T > t)

这个公式的边界是 T 必须是非负整数随机变量。模意义下做期望时，不使用浮点数，所有除法都转成逆元。

6.4 专项对照

专项	真题
构造	2025 B/E，2024 F/H，2023 H/J，ZJ2026 A/G
DP	2025 F/H/L，2023 F/I，ZJ2026 C/D/F/M
字符串	2025 H/K，2024 B/D，2023 E，2022 C/I
图论	2025 J，2024 F/J，2023 L，2022 G/L，ZJ2026 B/L
数学	2024 G/I/J，2022 A/B/K/M，2021 B/E/F
几何	2024 A，2023 M，2021 A/I/K

专项训练的顺序建议如下。

构造题先写不变量，再写输出，再写 checker。不变量是“输出过程中始终保持的真话”，例如前缀和不出现 forbidden difference、已染色格不改变、路径端点正确。checker 不需要懂你的构造过程，只需要懂题意。宫姐做点心会先看配方，构造题也一样：不变量就是配方。

DP 题先问三件事：阶段是什么，状态保存什么，转移从哪里来。若状态里放了过多历史，就要找等价压缩；若状态里少了关键限制，就会 WA。2025 H 的 last[c] 不是装饰，而是去掉重复子序列的唯一凭证。

字符串题先问“相等关系在哪里”。前后缀用 KMP，前缀相似用 Trie/Z，任意子串相等用 hash，回文用 Manacher。不要用肉眼比较字符串，赛场上肉眼属于不稳定外设。

图论题先重命名点和边。原题里的“题目、摊位、刷新器、电话、道路”未必就是图点；一次操作、一次传播、一次选择才可能是边。若命题人给了长设定，先像初春查情报一样把对象表列出来。

数学题先写小表，再写性质，再写公式。公式写出来后必须用暴力对拍小范围。食蜂可以心理掌握，你不行；不要相信没被小数据殴打过的公式。

几何题优先保持整数运算。叉积、点积、平方距离能解决的，不要提前上浮点。浮点数一旦进入比较，就要处理误差，这会把本来清爽的题写成泥潭。

7. 五年真题考法回顾

回顾不是给题目贴标签。标签只能告诉你“这里可能有 DP”，不能告诉你“为什么这个状态够用”。本章按年份看命题重心，更重要的是看每一年如何逼迫选手从故事中取出模型。

7.1 2021：数学定义压成可计算函数

2021 的底色是数学建模。题面往往先给一个定义，再问最大、最小、计数或查询。此时第一步不是找模板，而是把定义改写成一个函数。若函数单调，二分；若函数有递推，预处理或矩阵；若函数依赖图路径，进入最短路；若函数描述局面胜负，进入博弈状态。

题目	考法入口	落代码的第一步
A An Easy Problem	K-th 值	写 count(x)=有多少 i*j>=x
B Byfibonacci	Fibonacci 表示	预处理 Fibonacci，枚举/DP 表示状态
E EXcellent Number	数位计数	定义 pos, tight, mod, has
G Good Game, GG	博弈	找每个数的 Grundy/奇偶贡献
H History	图最短路 + 变权	先确定走第几条边时代价如何变化
K Kera’s line segment	区间数据结构	把线段坐标压到可维护范围

以 A 为例，题目问第 K 大的 i*j。不要枚举乘积。对一个候选值 x，能贡献的格点数是：

count(x) = sum_{i=1..n} max(0, m - ceil(x/i) + 1)

若 count(x) >= K，说明第 K 大至少为 x；否则小于 x。这就得到二分答案。代码核心只有两个函数：count_ge(x) 和二分框架。

long long count_ge(long long n, long long m, long long x) {
    long long cnt = 0;
    for (long long i = 1; i <= n; ++i) {
        long long need = (x + i - 1) / i;
        if (need <= m) cnt += m - need + 1;
    }
    return cnt;
}

long long kth_product(long long n, long long m, long long k) {
    long long lo = 1, hi = n * m, ans = 1;
    while (lo <= hi) {
        long long mid = (lo + hi) / 2;
        if (count_ge(n, m, mid) >= k) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return ans;
}

这里的边界是乘积上界和计数上界。n,m 到 1e6 时，n*m 和 cnt 都需要 64 位。若 n 更大，还要做整除分块优化；但在这类赛题边界内，先写清楚单调性更重要。

2021 年给出的训练启示是：数学定义不是拿来膜拜的，是拿来改写的。把定义改成 check、count、transition，题就有了门。

7.2 2022：等价、字符串与递推的三条线

2022 的题目更像三条线并行推进：一条是等价类计数，一条是字符串结构，一条是递推和图过程。它要求选手理解“看起来不同的对象是否本质相同”。拼图的旋转翻转相同，字符串的前后缀相同，矩阵快速幂里的下一步状态相同，本质上都在追问同一件事：哪些信息需要保留，哪些信息可以合并。

题目	考法入口	落代码的第一步
A 拼图	Burnside	写出旋转/翻转下不变的边状态数量
C 魔法师	LCP/LCS	建 Trie 与反串 Trie
E 黑白大陆	连通块	BFS 压缩颜色组件
I Rock&String	Border	预处理 KMP/哈希支撑子串查询
K 斐波那契	矩阵快速幂	设计固定维转移矩阵

Burnside 不要背成一句玄学公式。它的意思是：如果若干操作会把对象看成一样，那么本质不同数量等于“每个操作下保持不变的对象数量”的平均值。

answer = (fix(g1)+fix(g2)+...+fix(gk)) / k

拼图题中，操作是多边形的旋转与翻转；边状态有空、凸、凹，同时相邻边不能同时凸或同时凹。落代码时先写一个线性/环形 DP 计算固定周期下的合法染色数，再把它代入群作用。赛题边界内不需要把群论学成专著，只要会把“旋转了看不出区别”翻译成“不变方案数”。

字符串配对题的核心是把前缀和后缀分开处理。前缀用原串 Trie，后缀用反串 Trie。若题目问两串最长公共后缀，把两个串反过来就是最长公共前缀。这个反转动作简单，却是从题面到代码的桥。

def lcp(a: str, b: str) -> int:
    i = 0
    while i < len(a) and i < len(b) and a[i] == b[i]:
        i += 1
    return i

def lcs(a: str, b: str) -> int:
    return lcp(a[::-1], b[::-1])

上面仍是暴力定义。正解把所有串放进 Trie，让公共前缀通过公共祖先、计数或排序相邻关系求出。训练时先写暴力，因为暴力会告诉你定义有没有读错。

2022 年最重要的训练边界：Burnside 学到旋转翻转即可，矩阵快速幂学到固定维线性递推即可，字符串学到 Trie/KMP/哈希即可。不要把主线时间送给与赛题距离太远的高级理论。

7.3 2023：长叙事里的短模型

2023 很适合训练“读题时不被背景绑架”。基站、市场、新居、旅游、经典问题、计算几何，看起来像不同世界观，代码里却会收束成区间、交易状态、相邻贡献、MST 和凸多边形直径。岁纳京子可以负责把气氛搅热，解题时你要做船见结衣：冷静，把捣乱的设定按回模型里。

题目	考法入口	落代码的第一步
B 基站建设	覆盖需求	把“服务范围”改写成区间约束
C 市场交易	买卖次数	定义持有/不持有状态或贪心差分
E 新怀质问	字符串选择	Trie/排序维护 LCP
H 流画溢彩	操作顺序构造	写交换论证和输出 checker
K 独立钻石	小棋盘搜索	状态压缩 + 可行性剪枝
L 经典问题	特殊完全图 MST	找默认边权结构，不建完全图
M 计算几何	凸多边形直径	旋转卡壳求直径

这一年最该记住的不是某道题的题解，而是“现实包装下必有一个短模型”。比如经典问题中，完全图只是表象，普通边权 |x-y| 让点天然排在数轴上；特殊三元组才是异常。于是建模动作是分离默认结构和异常结构。默认结构用公式或压缩边表示，异常结构进 Kruskal。

计算几何题则提醒我们：题面说“多边形内部任意两点”，但凸多边形的直径由顶点对取得。一个几何结论把无限对象压成有限枚举，这就是几何题的算法化。落代码时先写 dist2、cross、旋转卡壳，再考虑枚举切线。若一上来就浮点面积、开根号、三角函数，代码会变成雾。

2023 年的训练任务是每天选一道长题，只做三件事：删背景，写变量表，写模型句。模型句必须短，例如：

基站建设：每个需求点对应一个区间覆盖限制，目标是最小代价满足所有限制。
经典问题：MST 在数轴默认边和少量特殊边中选择，不显式建立完全图。
计算几何：枚举对角线切分，子多边形直径用旋转卡壳维护。

能写出这样的句子，才算读懂。

7.4 2024：结构题的硬度

2024 的题量不大，但每道题都在考结构。结构题的特点是：你不知道那个结构，代码无从下手；你知道那个结构，代码突然变短。Border、DFS 序、Trie、边双、差分约束、倍数连通，都是这种结构。

题目	考法入口	落代码的第一步
A 田字格	横竖线段关系	扫描线统计结构
B 腊肠披萨	公共前后缀	前缀 Trie / KMP 定义校验
C DFS 序	子树访问顺序	计算子树贡献并排序儿子
D 拨打电话	电话网络	建 Trie，把号码前缀变成树
F 图	边不相交路径	Tarjan 桥，重边用边编号
I 不等式	差分约束	把 x-y<=c 改成有向边
J 另一个计数问题	数论图	按倍数关系分层统计

差分约束是这一年很好的“翻译训练”。每个不等式都要翻译成边：

x_v <= x_u + w  ->  u -> v, weight w
x_v >= x_u + w  ->  v -> u, weight -w

若要求是否存在解，检查负环；若要求最大/最小可行值，跑最短路或最长路，具体方向由建边方式决定。不要在代码里同时混用两套方向。差分约束一旦方向乱了，调试时像黑子空间移动失败，现场会很热闹，但答案不会好看。

边不相交路径则是图结构训练。桥是“所有通路都绕不过的边”，删掉桥后，同块中的点才有绕路余地。代码第一步永远是 Tarjan，而 Tarjan 第一条边界永远是重边。parent edge id 是这一题的护身符。

2024 年的训练要求：每学一个结构，都要写出它回答的问题。

KMP/Border：回答前缀与后缀相等关系。
Trie：回答多字符串公共前缀和前缀包含关系。
Tarjan 桥：回答删边后连通性是否改变。
差分约束：回答一组线性不等式是否存在可行势能。

结构不是模板的名字，而是问题的答案形式。

7.5 2025：综合建模的年度样本

2025 是最适合做主线训练的一年。它把状态压缩、构造、背包、字符串去重、事件图、周期、窄网格都放在一张卷子里。读这一年时会有一种后半场番剧全员登场的感觉：炮姐放电，黑子瞬移，初春查情报，小埋在家里打游戏，乃爱还在说自己可爱。热闹归热闹，代码仍要按秩序写。

题目	考法入口	落代码的第一步
A 矩阵游戏	小列数	枚举列 mask，行独立取最大
B 整数生成器	位运算构造	找目标数在二进制下的闭包规律
E 网格染色	2 行构造	固定已染色格，维护连通块不变量
F 排名预测	多重选择背包	每题生成互斥选项组
H 松散子序列	去重 DP	total 加 last[c]
J 解谜比赛	事件图	优先队列处理最早解锁
K 打字机	折返周期	把指针轨迹变成周期串
L 路线选择	窄网格	宽度小，状态记录截面

这一年的核心词是“小参数”。列数小、题数小、宽度小，都是命题人给出的钥匙。小参数不是让你随便暴力，而是让你枚举后把大部分对象解耦。矩阵游戏固定列后行独立，排名预测固定题目选项后进入背包，路线选择固定宽度后进入轮廓。建模时要反复问：

枚举这个小参数后，剩下的东西是否独立？
若不独立，还需要保留什么状态？
若状态太大，有没有等价压缩？

2025 年还强调 special judge。构造题不能只输出一个“看起来对”的答案。写 checker 的习惯要像提交样例一样自然。构造的证明负责说明不变量，checker 负责确认输出没有手滑。宫姐做点心可以紧张，checker 不能紧张。

8. GDCPC 出题思路

8.1 总体风格：故事只是门，结构才是房间

近年 GDCPC 很少直接说“给你一个 DAG 求最短路”或“给你一个字符串求 Border”。它更喜欢先摆一个生活或游戏场景：封榜、端午大集、电话网络、披萨店 Wi-Fi、魔法咒语、基站建设。题面像第一集设定，算法藏在设定之后。出题人的目标不是让你背模板，而是观察你能否完成抽象。

这种风格的稳定骨架是：

故事对象 -> 数学对象
故事动作 -> 状态转移或边
故事目标 -> 优化/计数/构造/判定
故事限制 -> 复杂度边界

如果一个题面很长，不要抱怨它长。长题面往往包含很多不进代码的信息，也包含一两个极关键的约束。读题时把它们分开：不进代码的先放一边，关键约束圈出来。比如“宽度不超过 4”比“端午大集很热闹”重要；“允许重边”比“题目叫图”重要；“输出任意方案”比样例里的那条路径重要。

8.2 高频命题入口：看到什么，该想什么

入口	题面表现	建模动作	代码落点
小参数	n<=15、m<=4、列数小	枚举小参数，检查剩余独立性	mask DP、轮廓 DP、背包
任意输出	special judge、输出任意方案	先写不变量和 checker	构造函数 + 验证函数
最早发生	解锁、传播、到达	事件按时间排序	优先队列、Dijkstra 骨架
前后缀	密码、周期、Border	判断相等关系	KMP、Z、Trie
大询问	q 大，静态数据	预处理或离线	Fenwick、分块、Tarjan、排序
等价类	旋转、翻转、本质相同	统计不变方案	Burnside、组合 DP
凸性	凸多边形、最远距离	找单调性	叉积、旋转卡壳

这张表不是答案，而是读题时的路标。路标只告诉你方向，真正能不能到，要看你是否写出状态和证明。

8.3 未来高概率内容：应当押什么，不应当赌什么

高概率内容仍是五类。

第一类是构造和 special judge。网格、序列、路径、操作顺序都适合出构造题，因为它们能给选手自由度，也能考证明能力。训练时要准备两件武器：不变量和 checker。

第二类是中档 DP。前缀 DP、背包 DP、状态压缩、计数去重会继续出现。它们难度适中，能拉开差距，又不会变成纯模板。训练重点不是多背状态，而是多问“为什么这个状态够用”。

第三类是字符串结构。Border、周期、LCP、Trie 是 GDCPC 很喜欢的字符串边界。复杂自动机出现概率较低，但 KMP/Z/Trie 的熟练度必须高。

第四类是图结构。桥、边双、SCC、事件图、隐式 BFS 都有命题空间。近年的图题越来越不直接，点可能是事件、坐标、集合或压缩块。

第五类是数学观察。gcd、组合数、递推、矩阵快速幂、等价类计数很适合中后档题。数学题的训练方法不是空想，而是小表、暴力、归纳、证明。

中概率内容包括计算几何、离线数据结构、树上复杂维护。它们会出现，但不应挤占基础主线。低概率但高杀伤的内容包括重型网络流、高阶多项式、复杂字符串自动机、复杂半平面交。知道它们存在即可；备考时间有限，不能把主线练级点拿去刷隐藏 Boss。

8.4 题面包装预测：壳会变，核不会

未来题面大概率仍会沿着本地化、比赛化、游戏化、生活化包装展开。广东城市、交通通信、市场交易、课程社团、旅游路线、账号密码、网格建筑，都天然适合作为题面外壳。

但壳不会改变核。看到交通，不一定是最短路，也可能是区间覆盖；看到比赛排名，不一定是排序，也可能是背包；看到字符串账号，不一定是模拟，也可能是 Border；看到网格，不一定是 BFS，也可能是轮廓 DP 或构造。

读题时可以默念这句：

它在讲什么不重要；它允许我改变什么，要求我优化什么，限制我多大规模，才重要。

这不是冷漠，这是算法竞赛的阅读方式。抚子可以先被露营的快乐感染，凛最终还是要把帐篷搭稳。

9. 三年模拟训练方向

三年模拟不是预测题面，而是训练节奏。真正的比赛不是十道独立题，也不是奔着 AK 去的冲刺表，而是一条时间线：开场读题，中段抢分，后半场判断取舍，最后检查输出。模拟卷要训练这条时间线。它服务于巩固和发展：巩固能做题的正确率，发展对新模型的识别能力。

9.1 模拟一：基础稳定卷

目标：把可拿分题拿稳，让中档 DP 和字符串题不再拖慢节奏。这里的“拿稳”不是假设全队一路顺风，而是在 ACM 赛制下减少错误提交，把已经能做的题真正变成 AC。

题位	考点	训练要求
A	日期/字符串格式	10 分钟内完成，函数拆清楚
B	数位贪心	写出每一位为什么可局部决策
C	排序贪心	写交换论证
D	Fenwick	明确维护前缀和、频次或第 k 个
E	KMP Border	手算样例 pi 数组
F	多重选择背包	每组只选一个，用 ndp
G	事件图	优先队列处理首次生效
H	构造	先写 checker
I	数论观察	小表到性质
J	几何扫描	整数化、排序化

这套卷的节奏应当像小埋在外面的完美形态：动作干净，不拖泥带水。前 45 分钟优先处理 A-C；第 90 分钟前至少打开 D-F 中两题；中后段用 G/H 训练图过程和构造。若 A-C 花了一个小时，说明不是算法不会，而是实现手感不稳，已经有回家变 UMR 的危险。

模拟后必须补一份记录：

A-C 总耗时：
第一道 WA 的原因：
第一道卡住的题：
是否写了 checker：
是否有一题完成对拍：

9.2 模拟二：构造与图论卷

目标：训练 special judge、桥/边双、隐式图和 MST 建模。

题位	考点	训练要求
A	简单构造	输出格式零失误
B	前缀和构造	checker 验证 forbidden subarray
C	网格构造	写连通块不变量
D	树上贪心	子树贡献和排序理由
E	隐式图 BFS	状态哈希，避免重复
F	Tarjan 桥	重边用边编号
G	边不相交路径	路径 checker
H	MST 建模	不显式建完全图
I	离线图查询	标清询问维度
J	小流/匹配	只训练赛题范围

这套卷要训练“输出不唯一时如何不慌”。先写 checker，再写构造；先写判断，再写输出。构造题不必优雅，但必须可证。若一个构造需要靠样例来确认，那它还没成型。

图题的复盘重点是点和边是否重命名。比如事件图里，原题点不一定是图点；隐式 BFS 里，一个坐标加状态才是点；MST 建模里，完全图不一定真的存在于代码中。初春查情报时会先把资料分门别类，图题也要这样。

9.3 模拟三：数学与压轴卷

目标：训练后半场判断力。不是每个压轴都要现场做完，但每个压轴都要能判断它的入口在哪里。

题位	考点	训练要求
A	数论小观察	小表验证
B	组合数	预处理上下界正确
C	矩阵快速幂	状态向量维度明确
D	Burnside	写出群作用和 fix
E	字符串周期	KMP/Z 二选一
F	期望	尾和公式或状态方程
G	LIS/LDS 偏序	坐标压缩和 rank 状态
H	窄网格 DP	宽度状态合法性
I	凸多边形几何	旋转卡壳
J	区间图离线	桥/连通性查询

这套卷不要追求全做。压轴题存在的意义之一就是制造取舍，它训练的是后半场的清醒：哪题值得继续，哪题应该放下。不会做的题要留下“入口句”，例如：

Burnside：旋转 r 步后，边状态按 gcd(n,r) 个环重复。
期望：答案写成 sum P(T>t)，概率用组合数。
轮廓 DP：按行推进，状态保存当前列的占用/连通信息。

写不出入口句，说明题没有读透；写得出入口句但不会做，说明可以赛后补。两者要分清。

9.4 模拟执行法：五小时的时间线

每套模拟建议 5 小时。不要只统计 AC 数，还要统计节奏是否崩。若训练环境是 OI 或 OJ，可以把 5 小时拆成多次专题训练，但仍要保留完整的读题、建模、实现、自测链条。

0:00-0:20  读全题，给每题写入口词
0:20-1:20  处理签到和确定性基础题
1:20-2:40  攻中档题，优先做模型清楚的
2:40-3:40  处理构造/图/DP 中最有希望的一题
3:40-4:30  冲一题难题，写出可提交或可放弃的证据
4:30-5:00  自测、修输出、提交低风险补丁

切题规则要提前写好。任意题 25 分钟没有形成模型句，切；形成模型句但 40 分钟没有代码骨架，切；代码写完样例不过且 20 分钟定位不到错，保留现场，切。赛场不是修行场，不能因为傲娇学生会式的不甘心把整场节奏拖死。OI/OJ 训练可以延长单题思考时间，但也要记录“卡住时缺的是模型、代码还是边界”，否则长时间只会变成低效熬夜。

赛后复盘按四栏：

题目：
卡点：读题 / 建模 / 代码 / 边界 / 心态
下次识别句：
补救动作：模板 / 对拍 / checker / 重写

复盘不是写忏悔录。它只负责把下一次的动作变短。

10. 训练方法与检查表

10.1 解题记录格式

每道题记录：

题目：
规模：
模型：
状态/数据结构：
复杂度：
关键证明：
错因：
可复用代码：

10.2 提交前检查

提交前检查不需要写成长篇，只要按固定顺序扫一遍。先确认输入总和限制是否读对，多测数组是否清空，下标是 0-based 还是 1-based。再确认数值范围：是否需要 long long 或 __int128，取模减法是否归正，INF 是否足够大。图题要检查重边、自环和非连通，Dijkstra 要确认没有负边，Tarjan 要确认父边用边编号。special judge 输出必须满足所有硬条件；Python 递归深度和输入速度要提前处理；浮点题输出足够精度。

10.3 日常训练标准

基础题的标准是 15 分钟内完成，不看题解，代码一次过样例。它们训练的不是智力上限，而是手感和稳定性。

中档题的标准是 60 到 90 分钟内完成，并且必须写出复杂度与证明。至少造 3 组边界样例，最好能写一个小暴力对拍。中档题是能力增长最快的区域，不要只看题解后说“我懂了”。

困难题允许读题解，但必须复现关键转化。若题目是构造或计数，补 checker 或暴力；若题目是图结构，补最小反例；若题目是几何，补整数边界。困难题的价值不在于当场 AC，而在于把那一个关键转化变成下次能识别的信号。

ACM、OI、OJ 的训练记录可以共用同一格式，但侧重点不同。ACM 记录时间线、提交前检查和队内分工；OI 记录子任务、部分分做法和正解差距；OJ 记录错因、反例和重写时间。三者最后都回到同一件事：让下一次从题面到代码的路径更短、更稳。

ACM 训练要把“错误提交”当成高成本事件。每次 WA 都要记录是读题漏条件、模型少状态、实现越界、取模错误，还是 checker 缺失。OI 训练要保留分层思维：先写暴力，拿到小规模正确性，再观察哪些子任务需要优化；这种习惯反过来能帮助 ACM 选手在难题上快速找到可验证的中间模型。OJ 日常训练最适合补模板和反例库，同一类题不要只 AC 一道就离开，而要把边界样例、对拍脚本和可复用代码一起归档。三种环境互相补强：ACM 给压力，OI 给层次，OJ 给重复。

10.4 考前保底策略

1. 前 20 分钟读全题，标记签到和熟悉模型。
2. 前 90 分钟优先处理低风险题。
3. 中场集中攻一个 DP、一个图或一个构造。
4. special judge 题优先写 checker。
5. 任何题卡 40 分钟无进展，切题。
6. 最后 30 分钟只做低风险修改。