题目列表

中序固定使每棵子树必对应一段连续区间，于是按区间长度递增做区间 DP，枚举根合成 l×r+a，并记录每个区间的最优根以还原前序遍历，O(n^3)。

通过自底向上与自顶向下的两遍树形 DP 维护节点向下最长/次长链与向上最长链，在 O(n) 时间内求出树的直径并判定所有位于最长简单路径上的节点。

经典树上最小点覆盖：设 dp[u][0/1] 表示节点 u 不放/放士兵时覆盖子树所有边的最少士兵数，通过树形 DP 自底向上转移。

每门课至多一门先修课，先修关系是森林；加虚拟根转成树后做树上分组背包，子树方案表逐孩子卷积合并，O(MN²) 求最大学分。

区间 DP 求分离合体的最大总价值：dp[l][r] 枚举切点、平手取最左保证字典序，再按分离阶段层序输出全部切点。

行间独立，逐行做两端取数的区间 DP：dp[l][r] 记剩余段取完的最优得分，轮次由段长算出，按段长递增转移后求和，O(nm^2)。

通过区间动态规划求将给定括号序列补齐为合法序列的最少添加字符数，状态转移综合两端匹配与中间分割点枚举。

环形区间 DP：把石子序列复制一份接到末尾，枚举长度 n 的窗口对应每种断环方式，f[i][j]/g[i][j] 分别表示区间 [i,j] 合并成一堆的最小/最大得分。

通过倍长断环成链将环形合并转化为区间 DP，按区间长度递推求最大能量释放

凸多边形三角剖分的最小乘积和：f[i][j] 记录连续顶点子多边形的最优值，枚举与边界边组成三角形的顶点 k 劈成两段，O(N^3) 区间 DP 直接求解。

全局偏移把全体加减工资压成 O(1)，固定值域上用树状数组按名次答第 k 大，扣薪只扫描长度恰为 k 的阈值区间批量删人。

使用分块有序表维护动态多重集合，支持插入、删除、排名与前趋后继查询。

使用离散化结合树状数组倍增（或平衡树）动态维护待匹配集合的前驱与后继

树链剖分把路径拆成 O(log n) 段 dfn 区间，每种信仰按 dfn 序建静态位置表，二分转成秩区间后用树状数组求和、线段树求最大值。

使用树链剖分将树上路径染色与颜色段查询转化为区间操作，借助线段树维护区间端点颜色与连续段数

从左到右扫描，用 covered[c] 维护位置已进入最靠右便宜咖啡店左侧的同色客栈数，答案每次累加 covered[c_j]，O(n) 时间、O(k) 空间。

把递推数列看成函数迭代，逐项模拟并用哈希集合记住出现过的值，首次撞上旧值的下标即答案，超过 2×10^6 步输出 -1。

把 Vigenère 表看成模 26 加法：解密逐位做 (密文序号 − 密钥偏移 + 26) mod 26，密钥按 i mod |k| 循环取位，明文大小写跟随密文，扫描一遍 O(|C|)。

用位掩码记录每个数字点可能落入的幻灯片，反复确定候选唯一的数字并删去该字母，若最终不能唯一对应则输出 None。

删边权和最大等价于保留边权和最小，而连通且无环的保留边正是一棵生成树，于是答案 = 总边权和 − 最小生成树边权和，用 Kruskal 加并查集 O(k log k) 求出。

枚举最远走到哪个鱼塘定下路程，把各塘递减的每分钟收益展开排序取前 k 大，O(N·S log S) 求出最大收获。

每层楼的两个按钮对应两条无权有向边，从 A 开始做 BFS，第一次到达 B 的距离就是最少按键次数。

面积即被 * 围住的 0 格个数：从最外圈的 0 格做一次多源 BFS 洪水填充，把能走到边界的 0 全标成外部，剩下未标记的 0 就是内部面积，O(nm)。

用调度场算法把中缀算式转成后缀表达式再求值，一次线性扫描即可处理括号与全部运算符

用记号类别状态机校验中缀表达式，再经调度场算法转后缀、用操作数栈求值；任一环节非法输出 NO。

把奖金更高的意见反向建边得到 DAG，用 Kahn 拓扑排序按前驱最大值递推每人最小奖金，成环则输出 Poor Xed

Kruskal 最小生成树：边按造价排序 + 并查集贪心选边，最后按 (u,v) 字典序输出。

用两个指针分别加工升序序列已生成前缀的 2x+1 与 3x+1 两族候选，队首取小接回序列、相等双消费去重，O(n) 得到第 n 个 Blah 数，多组询问逐组计算。

从 (1,1) 反向 BFS 一次得到全图距离，两次查表回答两匹马的最少步数。

最少相邻交换次数等于逆序对数，归并排序归并时统计跨段逆序对，O(n log n) 求解。

标记马的 9 个控制点后用网格路径计数 DP 统计从 A 到 B 的方案数。

旋转一次即交换相邻车厢，最少次数恰为逆序对数；离散化后用权值树状数组从左到右先查前缀和、后单点插入，O(n log n) 求出。

枚举分界 k，左侧前缀最大子段和与右侧后缀最大子段和相加，O(n)。

非递减的最终串只能是 A…AB…B 的形态，枚举分割点并用前缀和 O(1) 计算翻转代价。

二分答案：时间 T 可行等价于每个人的可达区间有公共交点，判定只需比较区间左端点最大值与右端点最小值。

3×3 小矩阵只有 3^9 种形态，把每块压缩成三进制整数用 bool 数组标记，O(1) 去重计数。

先默认全部不带走，每本书改带走只改变 d_i=a_i-b_i，问题变成从 n 个数里取至多 m 个正数使和最大。

值域只有 1~50，排序后相邻差 ≤1 等价于难度值连续不断档，答案是从区间最小难度到第一个空档的出现次数之和。

x、y 两个方向独立取最小外接矩形，边界不算罩内且角点必须为整数，恰好把每条边强制外扩 1 格。

无限循环播放只是周期重复，先用 c mod L 折回单周期，再把压缩串解析成段并用前缀和定位对应音符。

把每个红格子的镜像格子也染红，逐格检查一次即可。

模拟十进制舍入：每步把当前数舍入到 10 的幂，逢 5 进位；低位进位会改写高位，必须对当前数连锁进位。

把自西向东的闭合旅行拆成两条点不交的上升链，用双向扩位 DP O(N^3) 求最大覆盖城市数

通过拓扑排序剥除基环树外向树枝收缩至环上，再对简单环分类讨论破环为链进行动态规划，求基环树森林的最大权独立集。

将填数顺序映射为进出栈合法序列模型，转化为求第 n 项卡特兰数，通过质因数分解配合勒让德公式计算阶乘因子重数，解决模数可能为合数的问题。

将 DAG 上的多棋子移动博弈转化为独立游戏的和，拓扑排序逆序计算各节点的 SG 值，再根据各棋子位置的 SG 异或和判断胜负。

通过将去掉空格的网格展开为一维序列，证明上下左右移动均不改变逆序对数的奇偶性，转化为归并排序统计逆序对。

通过判断划分中是否包含 1 分解为两个独立子问题，建立二维 DP / 记忆化搜索状态转移 f(n, k) = f(n-1, k-1) + f(n-k, k)。

反转只影响子串内部，故新串与原串的第一处不同必在区间内：两端字符不同时答案是 [s[l]>s[r]]，相同时递归到去掉两端的子区间，按长度递推加滚动数组得到 O(n^2) 时间、O(n) 空间。

把每场战斗折算成升级/挨打的性价比，树上父亲先打的限制用并查集把子块并入父亲块，堆按性价比整块出战。

让工资最小的 k=n-x-y 人前两年连续拿 C 被开除，幸存 x+y 人年年涨薪：前 x 大乘 3^m、接下来 y 大乘 2^m，取模输出。

读入时按名字结尾字母分 26 个桶，桶内按（评分降序、同分先读入在前）排好序，询问直接取桶内第 k 个名字。

跳跃游戏式最右可达端点扫描，断档处给撑起端点的格子恰好施一次魔法补上，O(n) 求最少施法次数与最小字典序序列。

固定右端点，用两个单调栈找出极值变化点并按窗口长度差分入账，O(n×值域) 求出全部 n 个窗口值

一个格子的最终颜色由覆盖它的最后一个 t=1 操作决定，没有 t=1 时由第一个操作决定；按行和列分别用并查集求出每个操作负责的格子数，再前缀累加即可。

把追逃过程按第一次传送拆成两段：传送前 Pang 固定在 k，是一次带权最短路；传送后在某点 v 沿 v→n 的最短路走，伤害成周期为 d 的等差数列，用公式 O(1) 结算。

断点只可能落在 2n 个区间端点处；交错区间对 l_i<l_j<r_i<r_j 使 r_i 与 l_j 二选一，答案 = 2n − 该二分图的最大匹配。

不辣菜摆在某个位置的收益只由面前三位教授决定，于是贪心选收益最大的 n-a 个位置即可。

跳过一个景点只是把线路上的两段相邻距离换成一段，先用倍增 LCA 求出任意两点在树上的距离，再用总时间加减这三次变化就能 O(1) 得到每个答案。

砍掉一条边会把树分成两半，所以数对 (a,b) 被分开的充要条件就是这条边在 a 到 b 的路径上；问题变成“哪些边被全部 m 条路径跨过”，用 LCA 加树上点差分一次统计。