题目列表

把二维偏序上的最大收益路径 DP 拆成按列扫描，再用两层单调凸包分别处理历史列转移和当前列内的纵向转移。

把字符串复制成两倍长度后，用最小表示法比较两个候选循环位移并整段淘汰较差起点，在线性时间求出字典序最小表示的起点。

把每种颜色的首末出现位置看成区间，用栈扫描检查区间是否只存在包含关系；最大栈深就是最少轮数。

把“灯亮”和“可达”分开维护，从起点做 BFS；每次开灯后，新亮房间若挨着访问区域就立刻变成可达。

把“初始朝上”和“初始朝右”两种可能同时打包成一个六维状态，用 BFS 求一套公共指令的最短长度。

用 9 位掩码维护每格候选数字，结合数独约束与大小关系反复传播，再按候选最少的格子搜索。

二分最大位移后，把每个区间转成带最早可接点和最晚失效点的任务，按失效点最小优先贪心推进覆盖前缀。

枚举罪犯和星期几，在线性扫描证词时判断每个人是否必须恒真或恒假，再检查能否凑出恰好 N 个说谎者。

先在外层 DFS 枚举单顺、双顺、三顺的拆法，再对剩余牌型做记忆化搜索，精确求出最少出牌次数。

每次贪心选择当前能让最多乘客少 1 分钟的那段路，把它的行驶时间减 1；这次收益由提前效果能传播到的连续区间内下车人数决定。

把树按深度分层后，按层搜索每轮在当前还会感染的点里切掉一个子树，最大化保住的人数。

把输入串看成 BWT 的最后一列，排序得到第一列，再用同字符同出现次序建立 LF 映射，从 p 逆推原串。

按冒号切成 8 组后分别去前导零，再找最前面的最长连续 0000 段，用一次 :: 替换即可。

把 a 看成带最早开始时间的单位作业，用大根堆贪心生成最优等待时间，再把大等待与小 b 配对得到最小总代价。

把横纵坐标按 n 分成完整块和残块，利用模 n 余数的一一配对，常数时间统计整块与右下角残块贡献。

按固定元素是否出现过来统计不同元素个数之和，把每个长度的贡献化成两段等比数列求和。

把 x 分解成质因子后，每个指数里完整的 3 个一组都能提出到根号外，因此答案是各质因子 p 的 floor(e/3) 次幂之积。

证明每杯水在第一次烧开前最多只值得被预热到 50 度，于是总温度增量是 100 加上其余 n-1 杯各 50。

先判图中是否有孤立点；若没有，就对每个连通块的生成树二染色，直接构造两个互不重叠的覆盖方案。

在模板范围内搜索，并记录每个模格子第一次对应的绝对坐标；若同一模格子被不同绝对坐标到达，就能无限走远。

把机器人所在格点和朝向一起作为状态做 BFS，并预处理中心能否站在某个格点。

把每次插入的 1..x 压成一个块，只维护块前缀删除量；第 z 个元素和最大值都转成块级查询。

阈值 n 固定时顺着日志模拟能 AC 的题数，它随 n 单调不增，因此二分出所有满足 count(n)=k 的整数区间。

把问题拆成沿三条边分别递归找邻居：父内能直接找到就替换末位，否则沿同向边递归向父三角形外查。

二分最大速度，给定速度后顺着维护每个地点可行签收时间区间的下界，线性判断是否能按时送完。

固定 m 时最优加数只会是前缀全加 1、后缀全加 m，再把每个位置对所有 m 的正增量独立求和。

把三元组化成同颜色同奇偶的端点对，再按颜色和奇偶分组维护四个历史统计量线性求和。

按距离排序后做站点贪心：若前方有更便宜站就只买到够到它，否则当前站加满并去可达范围内最低价站。

用栈维护循环嵌套、死循环深度和当前有效幂次，线性扫描判断语法并求真实复杂度。

固定差值 q，把四元组化成左右两类值对，再用前缀累计和后缀累计统计四种位置贡献。

先由最终连续感染段反推全局最多传播了多少晚，再把每段连续 1 按单个初始感染点最多覆盖的长度分组计数。

用双指针维护一个覆盖全部画家编号的最短区间；右端扩张凑齐种类，左端尽量收缩。

把横切和竖切代价分别降序排序，每次优先切当前代价更大的那一刀，让大的代价尽量在乘数更小的时候付出。

把一种性别记成 +1、另一种记成 -1，问题就转成最长和为 0 的子数组；记录每个前缀和第一次出现的位置即可。

先求出第 i 段长度前缀和为 (i+1)(2i+1)，二分定位 k 落在哪一段，再按段内位置分段计算数值。

先用现有动物的按位或找出已出现过的二进制位，再把仍会引入新饲料的位置并成危险位，最后按自由位数量直接计数。

把每个武将所在行的次大默契值看成他起手后能保住的最强搭档，再取所有次大值的最大者；同时用高边构成匹配证明小涵一定能赢。

把每一对会说话的同学映射到唯一的一条横缝或竖缝，分别统计每条缝的贡献次数后，各自取前 K 条和前 L 条即可。

把数字 1..n 看成可重复使用的物品，按数字大小做组合计数版完全背包，用 dp[sum][cnt] 统计和与份数。

固定一个点后枚举它与谁配对，这条线会把圆拆成左右两个互不相交的子问题，于是得到标准 Catalan 递推。

把操作过程抽象成还未入栈数量和当前栈大小，用记忆化搜索统计合法 push/pop 序列。

把红筹和黑筹分别看成左括号与右括号，用前缀差值 dp[i][bal] 统计合法前缀数量，再用高精度加法保存第 n 个 Catalan 数。

先把每种特产独立看成隔板法分配，再对空同学集合做容斥，枚举有多少人没分到东西并扣掉这些不合法方案。

把空行、空列、缺失颜色都当成坏事件做三重容斥，固定保留行列和可用颜色数后，每个剩余格子独立贡献 avail 种选择。

先写出原题的 O(nk) 计数 DP，再把状态改写成第二类 Stirling 数，最后用满射计数的容斥公式在线性预处理后求出 S(n,n-k)。

先算每种做法任选或不选的总方案数，再按食材枚举严格多数者，用差值 DP 统计坏方案并从总数中扣掉。

把原式改写成 |(a+bi)(p-qi)+(c+di)(r+si)|^2，在高斯整数环里用扩展欧几里得求 gcd 和贝祖系数。

把 ax≡1(mod b) 改写成 ax+by=1，用扩展欧几里得求出一组解，其中 x 在模 b 意义下的最小正值就是答案。

设 f[i] 表示杀死一只 i 号怪兽的最小体力，满足 f[i]=min(K_i, S_i+Σf[spawn])。先把法术攻击代价当作初值，再从已确定更小代价的子怪兽反向更新父怪兽。

对每个城市分别维护“机器人最早能到城门的时间”和“所有前置发生器最晚被摧毁的时间”，城市真正被摧毁的时间是这两者的最大值，再用 Dijkstra 式过程按时间推进。

把每个关键交点拆成“横线状态”和“竖线状态”两个点；同一条线上的相邻关键点连边，换乘站内部连一条代价为 1 的边，再在这张图上跑最短路。

这是无权图单源最短路。先从 1 号点做 BFS，得到每个点的最短层数，再统计最远距离、最小编号和该距离出现次数。

牧场总数只有 52 个，把大小写字母映射成编号后直接 Floyd 求全源最短路，再在 A..Y 中找离 Z 最近的那头牛。

标准正权无向图单源最短路，直接从起点 s 跑一次 Dijkstra，输出到终点 t 的距离即可。

路线被强制经过 1 号牧场，所以先从 1 号点跑一次 Dijkstra，任意询问答案都是 dist[p] + dist[q]。

商人的总路程就是从首都出发后，相邻两站之间树上距离的总和；用倍增 LCA 快速求两点距离，再顺着给定路线累加即可。

一组员工都能被同一人管理，等价于这个人是他们的公共祖先；先求这组点的 LCA，再在根到该 LCA 的路径上取最大编号即可。

在无向图上跑一遍 Tarjan，若某个儿子 v 满足 low[v] >= dfn[u]，就说明删掉 u 会让这棵子树断开；根节点还要单独判断子树个数。

把无向图做一遍 Tarjan，若树边 u-v 满足 low[v] > dfn[u]，说明 v 子树回不到 u 及其祖先，这条边就是桥。

先求从 1 号景点出发能到达的全部景点；在这些点上按边的较低端高度降序、边长升序做 Kruskal，可以在保证可达景点数最大的前提下，把总滑行距离压到最小。