题目列表

把展开过程倒过来看：区间能折成一个字母当且仅当存在规则 c→xy 与分裂点把区间切两半；按区间长度递推的区间 DP，复杂度 O(L^3)。

先断环成链并复制数组，再设 dp[l][r] 表示一段珠子聚合后的最大能量，枚举最后一次合并的断点。

在有向无环图上逆向定义到达终点的剩余期望长度，利用全期望公式与拓扑序通过记忆化搜索在 O(n+m) 内求解。

把环复制成 2n 长数组，先教会链上的区间 DP（枚举最后一次合并的断点），再枚举所有长度为 n 的起点，同时维护最小与最大合并代价。

把已关灯集合压成包含起点的连续区间 [l,r]，用 f[l][r][0/1] 记录停在区间左/右端的最小耗电，区间 DP 一步扩展到相邻端点，O(n^2) 求解。

两种解法并列：线段树优化建图 + Tarjan 缩点把区间连边压到 O(log n)，在 DAG 上传播可达区间端点；以及不建图的 O(n) 双向扫描，靠「引爆集合是连续区间」和「右向射程在向左闭包时仍有效」直接求端点。

行只能单调向下，所以逐行决策；再证明走完一行后最优解必停在该行线段的端点，把每行状态压缩成左、右两个，得到 O(n) 线性 DP。

把「任意两点有两条边不相交路线」化归为「没有桥」，删桥缩成边双得到桥树，答案就是桥树叶子数的一半向上取整。

把每场游戏的两种可用赛车建模成 2-SAT 布尔变量，用「禁 A / 禁 B」两种情形覆盖 x 地图的三种取值，2^d 次 Tarjan 判定。

把删点后 S 是否分裂翻译成圆方树上的路径必经点，再用圆点前缀和与虚树环巡游 O(|S|log n) 回答每次询问

圆方树 + 赋权 + 树上路径贡献计数：方点权=BCC大小，圆点-1，树DP统计每点被(s,f)路径经过次数

封锁一个点后，真正新增损失来自它把图切成的多个连通块；用 Tarjan 求割点时顺手统计每个被切下来的子树大小，就能在线性时间算出每个点造成的访问损失。

把每个组看成一条连续链，按实力值递增处理；有多条链可接时接最短的，链比人多时冻结最长的，断档时整段冻结，答案取所有链长的最小值。

买下一个间谍就能免费得到他整条下游，于是真正要选的是「从哪些人进入」；互相可达的人缩成强连通分量只买最便宜的一个，缩点后 DAG 里只有入度为 0 的分量无人能揭发、必须直接收买。

正难则反：把「最小删边代价」翻成「最大保留边权和」，按边权降序并用并查集，两端块都含敌城时才必须删这条边。

Kruskal 求 MST 后枚举非树边换树边，倍增 LCA 同时维护路径最大与严格次大边权。

求 s 到 t 路径上最大边权的最小值（瓶颈路），可用 Kruskal、瓶颈 Dijkstra 或二分答案求解。

把直接买建成虚拟源点边，把优惠价建成礼物间边，转化为最小生成树。

多次询问无向图中点对的最大瓶颈路：Kruskal 建最大生成森林，倍增 LCA 上跳时维护路径最小边权，O(log n) 回答每个询问。

把打井建成虚拟水源点到田地的边、铺管建成田地之间的边，问题化为 n+1 点图上的最小生成树，Kruskal 求解。

以最小步长为模建立余数图，Dijkstra 求每类余数最早可达楼层。

把下界约束建成 0/1 边，SCC 判严格环后在缩点 DAG 上求最长路。

两遍 Kruskal：第一遍先加水泥路求鹅卵石路下界 need 并标记被迫边，第二遍放回被迫边、补鹅卵石路到 k 条、水泥路填满，得恰好含 k 条免费路的生成树。

Dijkstra 同时维护每点严格不同的最短与次短距离。

Floyd 同时维护最短距离和路径数，再按经过节点的路径比例计算重要度。

按时间增量加入 Floyd 中间点，在线回答当前已重建村庄间最短路。

Floyd 后枚举传送门端点，逐点对比较原路和两个传送方向。

把三类作物数量关系统一成差分约束边，全点入队跑 SPFA 判负环，有负环即矛盾。

对配方超边做 Dijkstra 式松弛，再按最小成本递增顺序统计最优方案数。

BFS 分层并在最短层边上累加方案数，支持重边。

把 x_c-x_c'<=y 转成 c' 到 c 的边，初值取 0 全部入队跑 SPFA 做松弛；无负环即有可行解。

把免费次数作为分层状态，在 n(k+1) 个状态上运行 Dijkstra。

对十个数字求变换传递闭包，再把每一位的可达数字数相乘。

用队列优化的 Bellman-Ford（SPFA）求非负权有向图单源最短路，只在距离被改小时重新入队。

以 map 精确分组差异核心、双 Trie DFS 激活和祖先链求和为主解，并对照 AC、二维扫描线与确定性线性做法。

用 heapq 实现带过期状态判断的 Dijkstra，求非负权有向图单源最短路。

先按后缀表达式建树并求当前值，再从根向下传播“能否影响根”的标记，这样每个翻转询问都能 O(1) 回答。

用树状数组维护 0..600 的成绩频率，并通过第 k 小查询在线求当前获奖分数线。

把网格看成图，扫描时每遇到未访问的细胞数字就用四方向 BFS 淹掉整个连通块并把答案加一。

同一连通块内所有格子的答案都等于块的大小，对每个未访问格子 BFS 一次并写回答案，询问 O(1)。

扫描网格，每遇到未访问水格就用八方向 BFS 淹掉整个连通块并把答案加一。

反向建图并按编号从大到小搜索，首次访问时写入该点可达的最大编号。

先把每个点的邻接表按升序排序，再用逆序压栈实现非递归 DFS，用队列实现 BFS。

反转只影响子串内部，故新串与原串的第一处不同必在区间内：两端字符不同时答案是 [s[l]>s[r]]，相同时递归到去掉两端的子区间，按长度递推加滚动数组得到 O(n^2) 时间、O(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 加树上点差分一次统计。

把“同一局域网”正确理解为互相可达即强连通，用迭代 Tarjan 缩点，把分量内部边权变 0，再跑堆优化 Dijkstra 求最短路。

把小岛转成 x 轴上的覆盖区间，按右端点排序，遇到未被覆盖的区间就把雷达放在它的右端点。

1. 前缀比较具有二分性 (左对右错) 2. 字符串哈希具有结合律 3. fhq-treap 中序就是字符串原来的序列 4. 利用fhq-treap 的logn 分裂合并的性质维护 动态插入与删除 与 结合律

把每个位置需要的翻转次数写成除数前缀异或，按下标递增唯一决定每个操作是否选择。

枚举最大值后，把其余 k-1 个数转成最大异或值，用二进制 Trie 在线查询前 k-1 个异或和。

按 mex 值贡献:分类，把条件转化为区间必须包含所有小于 x 的位置且避开所有 x 的位置。

把物品按组分类，每组最多选一件，外层遍历组、内层倒序枚举容量、最内层遍历组内物品做 01 转移，保证同组互斥。

筛出≤n的所有素数，再做0/1背包计数取max：dp[j]=max(dp[j], dp[j-p]+1)，求最多项数。

附件挂主件，对每个主件枚举附件组合(最多2^2种)，转成0/1背包做倒序转移。