算法练习路径

这条路径不追求快速刷过大量题目，而是让每一组题只训练一个可以迁移的思维动作。题目名称、难度和标签通过 Codeforces 官方题目页或 API 核对；题解均为本站重新组织的解释。

01
RATING 800

把题意翻译成条件

练习奇偶判断、字符串压缩、0/1 计数、阈值扫描与简单最优性证明。目标是先把自然语言压缩成布尔表达式，再开始编码。

阅读五题详解 →
02
RATING 1100—1500

复用序列中的信息

比较固定窗口、可变窗口和排序后二分。目标是识别单调性，避免为每个区间或查询重复扫描。

阅读四题详解 →
03
RATING 1100—1500

把区间操作压缩成位置摘要

用前缀计数回答重复查询，用差分还原区间覆盖，再处理排序权重与双层离线影响。目标是分清数据轴、值域轴与操作编号轴。

阅读四题详解 →
04
RATING 900—1500

证明局部选择不会让未来变差

从最大硬币、最弱巨龙走到树木左右倾倒。目标是不再把“排序后模拟”当作证明，而是能写出交换论证、可行首步和前缀不劣性。

阅读三题详解 →
05
RATING 1400—1600

把最大化问题改写为可行性判断

在答案空间上维护最后一个可行值，练习构造单调判断、证明上下界，并在成本累加和乘法中主动防止整数溢出。

阅读三题详解 →
06
RATING 1300—1500

把不同历史压缩成状态

用恰好剪满的长度理解不可达状态，再按数值聚合处理相邻冲突。目标是先写清状态含义，再证明转移覆盖所有方案。

阅读两题详解 →

进阶衔接：474D · Flowers（1700），把最优值 DP 换成计数 DP，再用前缀和回答多次区间查询。

07
RATING 1400

把操作过程画成状态图

用 BFS 分层寻找最少操作次数，证明有限搜索边界，再通过逆向操作和交换论证得到更快的贪心解法。

阅读两种解法与证明 →
08
RATING 1900

从无权搜索进入正权最短路

用小根堆按距离扩展顶点，理解松弛、过期堆条目和 Dijkstra 的贪心不变量，同时记录父节点还原一条最短路径。

阅读完整推导与边界清单 →
09
RATING 1800

用不变量压缩资源状态

从左右预算的位移关系证明状态支配，再把最少左移建模为 0/1 最短路，用双端队列替代堆，并以四维搜索独立验证。

阅读双端队列与预算证明 →
10
RATING 1900

用生成森林组织连通性

并查集识别可保留的森林边与多余边，通过分量数证明最少改路次数，再构造每一步都合法的道路替换计划。

阅读最少改路的构造与证明 →
11
RATING 1900

把不同选择统一成生成树边

用虚拟源点把建电站和铺电线放进同一张图，再用割性质证明 Kruskal 的选择，构造最小成本供电网络。

阅读电网建模与最小生成树证明 →
12
RATING 1600

把先后关系变成有向无环图

从相邻名称的首个不同字符提取字母约束，单独识别前缀矛盾，再用 Kahn 算法构造完整字母表并通过输出长度检测有向环。

阅读字典序建图与拓扑证明 →
13
RATING 1600

把树的子结构展平成数组区间

用一次先序 DFS 记录进入位置和子树大小，证明每棵子树占据连续区间，再把二十万次局部访问查询降为 O(1)。

阅读树的展平与迭代实现 →
14
RATING 1900

反过来计算元素能支配多宽

不再为每个窗口长度重扫数组，而是用单调栈找到每个元素作为最小值的最大区间，再借答案单调性从长到短回填。

阅读边界证明与重复值处理 →
15
RATING 1700

只重算修改点到根的路径

把逐轮 OR/XOR 归约保存为完全二叉树，让每个节点记录区间摘要，并按离叶子的高度决定合并运算。

阅读树形归约与层次证明 →
16
RATING 900—1600 · THREE PROBLEMS

分清路径状态与子树汇总

用三道题连续练习树上 DFS：先把分组问题化为森林最大深度，再沿根到叶维护连续状态，最后同时计算深度与子树大小，把统计量转成可证明的贪心贡献。

阅读树上 DFS 三题详解 →
17
RATING 2000—2200 · THREE PROBLEMS

为不同查询设计区间摘要

从 339D 的单点修改继续到三种进阶节点：用懒标记承担区间加，用有序三元组合并括号，再把 GCD 与真实出现次数组合为数论摘要。

阅读线段树三题详解 →
18
RATING 1900—2500 · THREE PROBLEMS

在十进制前缀上压缩状态

用三道题逐步拆开数位 DP：先统计非零位，再加入位置强制条件与整除余数，最后用 2520 和约数 LCM 压缩“被所有非零数位整除”的历史要求。

阅读数位 DP 三题详解 →
19
RATING 1800—2000 · THREE PROBLEMS

让拓扑序承载构造、DP 与分批贪心

从 510C 的基本拓扑序继续，用三题比较零入度点的不同用途：按拓扑位置给无向边定向，在依赖边上传播最少轮数，再按执行设备形成最少调用批次。

阅读拓扑排序三题详解 →
20
RATING 1400—1800 · THREE PROBLEMS

让合并动作同时维护可复用统计量

从静态群组传播与语言桥接开始，分清连通块大小、连通块数量和全零特殊边界；再按边权离线开放树边，用两个分量大小的乘积统计新出现的合法点对。

阅读并查集三题详解 →
21
RATING 1900—2200 · THREE PROBLEMS

让栈只保留未来仍有用的边界

从括号失配位置出发，进入单调栈的两种进阶用途：合并由同一最小高度控制的连续段，再以递增、递减两组轮廓压缩隐式图上的动态规划前驱。

阅读栈与单调栈三题详解 →
22
RATING 2000 · THREE PROBLEMS

让最短距离继续回答结构与取舍问题

从 Dijkstra 的距离不变量继续向前：在等长路径中选出最轻的树边，判断哪些特殊列车可以删除，再把“先买票、后走路”改写成多源最短路。

阅读最短路进阶三题详解 →
23
RATING 1800—2100 · THREE PROBLEMS

把一个根的子树信息传播到所有根

先固定根统计子树，再分析跨过父子边时两侧贡献怎样增减；从加权距离和与涂色得分，走到需要传递父侧最优贡献的最大白子树。

阅读换根 DP 三题详解 →
24
RATING 1800—1900 · THREE PROBLEMS

用扫描与值域前缀压缩序列计数

先用前后缀频次构造点对条件，再枚举中间位置组合递减三元组，最后利用反转奇偶性省去实际修改。重点分清坐标轴、严格不等号与扫描集合。

阅读序列计数三题详解 →
25
RATING 1900—2100 · THREE PROBLEMS

把树上距离条件变成祖先与分量关系

先用父节点与 DFS 区间判断共链，再用倍增 LCA 计算临时加边后的行走长度，最后找到路径中点并统计等距点。重点区分简单路径、可重复行走与根路径。

阅读树上查询三题详解 →
26
RATING 1700—2000 · THREE PROBLEMS

把互相可达压成整体再区分源与汇

先用非递归 Kosaraju 划分强连通分量，再分别统计最低费用、未覆盖源和最小汇。重点理解边的方向，以及环究竟代表矛盾还是必须整体处理的集合。

阅读强连通分量三题详解 →
27
RATING 1800—2000 · THREE PROBLEMS

把公共前缀变成逐层决策树

从字符 Trie 上的两类胜负状态，走到动态二进制多重集合的最大异或，再用子树不同值数量判断累计异或后的 MEX。重点分清出现次数、不同值数量与懒掩码。

阅读 Trie 三题详解 →
28
RATING 2200

用窗口移动复用相邻查询的统计

当频次平方不容易合并为小摘要时，先推导单点增删公式，再通过左端分块与右端蛇形排序减少窗口移动，并用原编号还原输出。

阅读莫队推导与独立验证 →
29
RATING 2100

把子树修改与颜色集合放进同一段区间

以非递归 DFS 展平子树，用 60 位颜色集合保存可合并摘要，再证明区间覆盖标记的替换与下传，按原时间顺序处理染色和查询。

阅读动态子树染色与位集证明 →
30
RATING 2300

无法整段修改时先寻找无变化区间

区间和不能直接取模，用最大值跳过无效修改；真正变化的值至少减半，再把单点赋值补入势能，区分单次最坏与整串操作的均摊界。

阅读取模剪枝与势能证明 →
31
RATING 2000

把区间和拆成每个位的贡献

区间和不能直接异或，但每位的一的数量可以整段翻转。推导计数更新、掩码抵消与下传不变量，比较可整体更新的懒标记和取模剪枝。

阅读异或摘要与标记组合证明 →
32
RATING 2300

完整频次怎样在树上复用

众数答案不能直接相加；接管最大子树的袋子，再合并其余颜色频次，用顶点质量翻倍证明总遍历量，并区分映射查找的额外代价。

阅读频次合并与质量翻倍证明 →
33
RATING 2100

把树路径切成少量连续区间

重孩子优先编号保留子树连续性，根路径则按链头分段。用覆盖标记维护灌水与排水，证明轻边数量上界并避免长链递归栈。

阅读重链编号与路径分段证明 →
34
RATING 2000

把交替符号变成同号区间增量

先按深度奇偶变换更新，再用DFS闭区间与差分树状数组在线查询单点数值；分别核对更新端与查询端的符号，避免按先序位置猜测奇偶。

阅读符号变换与迭代 DFS 证明 →
35
RATING 2100

让每条指定边独立进入最优树

先固定一棵 MST，新增边形成唯一环；以倍增维护原树路径最大边，再用割证明替换费用最优，辨析等权替换与必选边。

阅读环替换与最优下界证明 →
36
RATING 2300

从可选边走向所有最优树的必选边

按权重冻结更轻连通块，在本组收缩图中保留平行边并找桥；分类后再合并，用非递归 DFS 避免长链栈溢出。

阅读三类边的完整证明 →
37
RATING 2100

把最多必经关口变成树的直径

删桥后压缩连通块，证明原图必经桥数等于桥树距离，再用两次 BFS 求全局最大值，保留显式 DFS 的退出时机。

阅读必经边与直径证明 →

面对新题，先问哪个问题

新增 1000E 桥树直径：承接160D 桥判定，这次将整个无向图删桥分块，证明同一对端点的必经桥对应树上唯一路径。只求全局最大值时用两次 BFS；指定点对的多次查询则可接倍增 LCA。

新增 160D MST 边分类：接续 609E 指定边费用，继续区分“至少可选”和“所有最优树都必选”。同一权重组要先判定、后合并；收缩图可能有平行边，只能跳过父边编号，不能把回到父顶点的所有边丢掉。

新增 609E 指定边的最小生成树：在电网规划 MST与倍增 LCA之间建立环替换。每条边独立询问，答案为原 MST 总费用加新边减路径最大边；用割论证最优下界，并区分“出现在某棵 MST”与“所有 MST 都必选”。

新增 383C Propagating tree：在子树区间与树状数组之间补上代数变换。沿边变号可分离为更新端与查询端的深度符号，先统一增量，再选择差分；这里没有根路径更新，不必直接照搬343D重链剖分。

新增 343D Water Tree：子树是一个 DFS 区间，根路径则拆成 O(log n) 段；重链编号同时保留两种连续性，再用赋值覆盖按顺序处理动态操作。先读620E 子树染色，再比较600E 静态袋子合并为何不能原样承担在线修改。

新增 600E 子树众数：从子树 DFS进入完整频次袋子，按子树顶点数选择大袋，再把轻袋合并成本收费到顶点。与620E 在线子树染色和86D 莫队比较静态结构、在线更新与离线窗口三种复用方式。

新增 242E 区间异或：把和拆成 20 个位的贡献，再用异或合成待下传的翻转。与覆盖标记的替换、取模更新的剪枝对照，先证明修改能作用于摘要，再决定能否使用懒标记。

区间修改支线从线段树三题与子树染色进入 438D 区间取模：摘要无法直接整体变换时，最大值识别无变化区间，减半性质则限制真正修改的总次数。

新增Trie 三题：先在 455B A Lot of Games 的字符 Trie 上计算两类终局，再用 706D Vasiliy’s Multiset 维护动态最大异或，最后在 842D Vitya and Strange Lesson 中用子树容量寻找累计异或后的 MEX。三份完整 C++17 均经过独立模型核验。

字符串匹配三题则从另一种“前缀”出发：先用 126B 理解失败链接与内部出现，再用 432D 沿边界树汇总计数，最后用 471D 把整体平移转成差分匹配。

这是一条知识依赖路线，不是难度严格递增的榜单。遇到题目时，先检查结构，再选择工具；下面每一行都需要验证右侧条件。

先问自己 候选工具 必须成立的条件
某条边是否在所有 MST 中都出现 等权分组 + 收缩图找桥 并查集只包含严格更轻边；临时图保留平行边，整组判定后再合并
一条边必须保留时，原 MST 怎样调整 环替换 + 倍增路径最大值 每次只强制一条边；先固定一棵 MST，再证明替换的上下界
匹配失败后，已知相等部分能否保留 前缀函数 / KMP 回退状态必须是已匹配前缀的边界，文本扫描只向前
大量对象是否共享字符或二进制前缀 Trie 先明确节点保存出现次数、不同值数还是 DP 状态；逐位贪心需证明高位优先
大量区间查询能否共享摘要 前缀和 / 差分 运算支持相应的累计与还原，注意在线和离线之别
能否随着右端点移动而只向前调整左端点 双指针 可行性或窗口代价具有所需单调性
猜一个答案后，能否快速判断可行 答案二分 判断结果在搜索区间中只有一次真假分界
未来只需要知道哪个状态 动态规划 状态信息足够，并且依赖有可处理的计算顺序
每次操作代价相同，目标是否为最少步数 BFS 状态规模可控；若裁剪搜索范围，需证明不会丢最优解
边有不同的非负代价，目标是否为总代价最小 Dijkstra 不含负权边；堆中旧记录需要识别
正确建模后，边权是否仅为 0 或 1 0-1 BFS 0 权入队首、1 权入队尾；仍需严格松弛
逐条加边，只需判断哪些顶点已经连通 并查集 普通并查集维护合并，不直接支持任意删边
要用最小总代价连接所有顶点 最小生成树 图需连通；虚拟选择可先转化为普通边
输入给出“谁必须先于谁”的约束 拓扑排序 有向图必须无环；还要先处理建图阶段的局部矛盾
有向环代表必须整体处理的一组点 强连通分量与缩点 必须是双向可达；源、汇要按实际业务选择
多个零入度点同时可选，选择顺序是否影响代价 拓扑 DP / 分批贪心 先明确状态转移或批次费用，不能只求任意拓扑序
合并两个集合后能否直接更新答案 并查集 + 分量统计 统计量必须能由两个根的信息和合并事件推出；在线删边通常不适用
查询阈值递增时，可用关系是否只增不减 排序 + 离线并查集 允许重排询问并保存原下标；相同阈值要处理完所有合法边
查询只关心整棵子树 DFS 序与子树区间 访问必须完整处理子树后才返回；固定孩子顺序
子树修改沿每条边改变正负 深度符号 + 差分树状数组 树与根固定，符号能分离；当前查询只求单点值
询问大量两点距离、祖先跳跃或路径中点 倍增与 LCA 树结构固定；明确边数、深度和跳跃层数
条件只由当前根路径决定 DFS 路径状态 状态随边向下更新；已经非法的前缀才能安全剪枝
答案同时依赖节点位置和后代数量 深度 + 子树大小 向下记录深度，逆序或回溯汇总子树统计
每个元素能作为最值影响多大范围 单调栈 栈内候选需满足单调性；明确等值元素的边界归属
单点变化后是否只需重算有限层摘要 线段树 节点摘要可由两个孩子合并；明确结合顺序与单位元
一次修改完整覆盖许多连续位置 懒标记线段树 修改能直接作用于节点摘要，并可组合为待下传标记
位运算修改之后仍要查询普通区间和 按位计数 + 懒标记 数值位宽有界；更新可逐位作用，标记按实际变换组合
区间答案是否依赖左右先后顺序 有序区间摘要 合并需满足结合律，但未必满足交换律；查询不能颠倒片段
数值上界很大，限制能否随十进制前缀更新 数位 DP 状态需概括已选前缀；用 tight 约束当前位，并明确前导零语义
查询可重排且边界单点增删便宜 莫队与分块排序 静态数组、保存原编号；不能直接处理依赖前一答案的查询
能否放心舍弃其他选择 贪心 有交换论证、支配关系等正确性依据

图论路线可以连续阅读 520B：状态图与逆向贪心、20C：Dijkstra 与路径还原 和 1063B：位移守恒与 0-1 BFS，比较单位边权、一般非负边权与 0/1 边权怎样改变扩展顺序；掌握距离之后，再用 545E、449B、938D 最短路进阶三题 训练树边选择、特殊边去冗余与多源建模。树结构则由 树上 DFS 三题 的深度、路径和子树贡献，进入 1092F、1187E、1324F 换根 DP 三题，学习把一个根的结果传播到所有根。动态规划方向还可由 状态设计与方案还原 衔接 Flowers 的计数与区间查询，再通过 1036C、628D、55D 数位 DP 三题 练习把巨大值域改写为逐位构造。

每道题怎样复盘

动态子树支线由 1006E DFS 序和线段树三题汇入 620E 子树染色：先证明结构展平，再设计集合摘要和覆盖标记，避免把颜色数量直接相加。

离线区间支线由树状数组与序列计数接到 86D 莫队算法：前者复用动态前缀，后者复用当前窗口，重点比较摘要合并和边界增删的适用条件。

有向图遇到环时，可接着读 427C、999E、949C 强连通分量三题：把互相可达的点压成 DAG，再比较分量内统计、未覆盖源和后继封闭的汇分量。

树上查询支线从 1006E 子树区间 接到 1328E、1304E、519E 三题，依次练习祖先判断、精确步数和等距点计数；先证明条件转换，再选择是否需要 LCA。

序列计数支线从 前缀和与差分 进入 459D、61E、911D 树状数组与逆序奇偶三题：把静态前缀升级为动态前缀，再分清哪些信息只在初始化时需要、哪些信息必须持续维护。

字符串与位运算支线先用前缀函数三题理解失配后的信息复用，再进入 455B、706D、842D Trie 三题：比较字符前缀和二进制高位前缀，并分清多重集合计数与不同值计数。

连通性分支从 25D：并查集与最少改路 开始，再到 1245D：虚拟源点与最小生成树。有向图分支先读 510C：字典序约束与拓扑排序，再用 1385E、1572A、909E 三题 比较定向构造、拓扑 DP 与分批贪心。树结构先用 115A、580C、1336A 三题 分清深度、路径状态和子树汇总，再进入 1006E：先序 DFS 与子树区间。数组结构分支先读 547B：单调栈与支配区间，再用 5C、1313C2、1407D 三题 比较失配边界、区间贡献与双单调栈 DP；需要在线修改时进入 339D：交替位运算线段树，最后通过 52C、380C、474F 三题 比较懒标记、非交换合并与复合数论摘要。

  1. 用一句话描述输入、目标与约束；
  2. 写出方法成立所依赖的条件；
  3. 主动测试最小值、临界值和重复值；
  4. 解释时间复杂度，而不只背结论；
  5. 修改一个条件，判断原方法是否仍然成立。

来源与更新原则

后续扩展会优先补充同一知识点的对照题，而不是无结构地增加列表。

avatar
eulersail
在技术、阅读与声音之间持续建立连接
文章
106
标签
177
分类
8
GitHub
公告
把零散经验整理成可以再次使用的知识
最新文章
配对置换检验 从符号翻转到精确 p 值
PPO 原理 从概率比到裁剪梯度
辛普森悖论 从分组反转到标准化比较
主动学习 从不确定性采样到标注预算
配对 Bootstrap 从模型差值到置信区间
分类
标签
0-1 BFS Actor-Critic BatchNorm Bootstrap CNN Codeforces Cohen kappa DFS序 DQN Dijkstra Docker Embedding GAE Git KMP Kosaraju Kruskal LCA Matplotlib NumPy PPO Python Q-learning RAG RAGFlow REINFORCE RRF SQL SQLite TCP/IP Transformer Trie Visual Studio 一致性 上下文工程 主动学习 主题发展 主题变形 二分查找 二分答案
归档
网站资讯
文章数目 :
106
本站总字数 :
323.3k
本站访客数 :
1852
本站总访问量 :
2041
最后更新时间 :