题目列表

先预处理单行合法状态，再按行做只依赖前两行的状压 DP，求最多能放多少炮兵。

把较短维压成二进制状态，按行做三行覆盖检查的轮廓 DP，并用 `(总代价, 油库数量)` 做字典序最优。

把每一列压成二进制状态，利用马只会影响前两列的性质，做记录前两列状态和已放马数量的轮廓 DP。

先在“单次飞行不超过 D”的图上跑 Floyd 求任意两村庄间最短可达代价，再在这个距离矩阵上做状压 TSP。

把每份披萨看成一个原料子集，直接状压枚举所有 2^N 个子集并检查是否包含冲突对即可。

设 dp[u][0/1/2] 分别表示 u 放塔、被儿子覆盖、等父亲覆盖的最少塔数，用三状态树形 DP 求树上最小支配集。

设 dp[u][j] 为 u 子树选 j 个黑点的最大收益，把同色点对距离和拆成每条边两侧黑点对与白点对数量乘边权的贡献来转移。

先用并查集缩掉所有 t=2 的相等点，再只保留 t=0 的不同色森林；计数是森林染色，最小和是带点权二分染色。

设 dp[u][c] 表示 u 染成颜色 c 时整棵子树的合法方案数，再把每个儿子所有不同色状态的方案数乘起来。

先做子树内精确距离 DP，再做一次换根，把父亲方向的精确距离贡献传给儿子，最终累加 0..K 层即可。

按右端点升序贪心处理请求，只要整段畜栏最小剩余容量仍大于零就接下，并用线段树维护区间最小值。

把区间按长度排序后做双指针，在线段树上维护当前长度窗口内的最大覆盖次数，找到最小可行长度差。

把每个乘车请求看成区间装载，按终点升序且同终点按起点降序贪心接单，再用线段树维护路段最大占用。

把题意翻成区间约束后，核心只剩查询 `(Y,X)` 中间已知年份的最大降雨量，再配合年份是否完整连续做四类判定。

把每个元素看成最终都会被某个不小于它的相邻块吞并一次，它的最优贡献是左右第一个不小于它的值中的较小者，用单调递减栈即可线性求解。

先把同一坐标上的星星亮度合并，再把题目转成一维数组上固定长度窗口的最大区间和，用前缀和线性扫描即可。

用线段树维护区间里空地数与树苗数，把状态分成老树、空地、树苗三类，就能同时处理整段砍树、局部补种和树苗损失统计。

用 defaultdict 建立单词到文章编号列表的倒排索引，并在每篇文章内先去重。

把每个值左边更大元素的个数记为 $c[x]$，则做完 $k$ 轮冒泡后的逆序对数就是 $sum(max(c[x]-k,0))$，再用树状数组维护 $c[x]$ 的动态分布。

先找出本来就不必移动的最长严格递增后缀，再用树状数组统计每头前缀奶牛插入有序部分时应后移的步数。

先把所有彩珠按坐标打平成 `(位置, 颜色)` 序列并排序，再用双指针维护覆盖全部颜色的最短区间。

把所有加密操作按相反顺序依次撤销，其中分别实现栅栏密码、维吉尼亚密码和 QWE 键盘码的逆变换即可还原原文。

把平台序列建成最大笛卡尔树，递归计算每个子盆地先灌到根高度、再整体上涨的体积时间，从而求出各平台被淹没时刻。

把每种特性的前缀出现次数都减去第一种特性，转成前缀差分状态；相同状态之间的最远距离就是答案。

先在反图上从终点标记可达点，再筛出所有安全点，最后只在安全子图中做 BFS 最短路。

把合法区间改写成不存在 x_i>y_j 的冲突对，先用树状数组求每个位置的第一个冲突点，再用双指针维护最长合法区间。

按位置排序后，分别用两次单调队列维护左右 D 范围内的最大高度，再判断是否都达到当前高度的两倍。

先算原始积水，再把每个位置改低后真正受影响的左右连续区间拆开重算，从而在线性时间求最优修改。

把单个站点总代价看成绝对值和函数，先取中位数区间平台，再从左右两条单调代价序列中归并取前 k 小。

把位置、当前颜色和是否刚施法作为状态，在四维状态图上做 Dijkstra 求最小花费。

检验值 y(W) 随阈值 W 单调不增，用前缀和在 O(n+m) 内计算一次 y(W)，再二分找到最接近标准值 s 的位置。

把前 k 份订单是否可满足做成差分检查函数，再二分第一份出问题的订单编号。

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

预处理每对单词的最小合法重叠长度，再用 DFS 在每词最多使用两次的限制下搜索最长接龙。

先统计每个 t 的倍数里有多少齿轮，再用 C(cnt[t],k) 算 gcd 是 t 的倍数的方案数，最后按倍数从大到小容斥还原精确 gcd。

先算总状态数 m^n，再减去所有相邻房间宗教都不同的安全状态数 m·(m-1)^(n-1)。

把每轮操作看成当前酒量加上 b 再对 a 取模，最小正体积就是 gcd(a,b)，再用 exgcd 求 b·y-a·x=g 的最小正解。

先用 exgcd 求 ax+by=-c 的一组特解，再把通解写成 x=x0+k·b/d, y=y0-k·a/d，把矩形范围限制都转成对 k 的区间约束，最后求区间交集大小。

先用 exgcd 判断 ax+by=c 是否有整数解，再把通解写成 x=x0+k·b/d, y=y0-k·a/d，通过不等式求出正整数解对应的 k 范围。

把两只青蛙第 t 次跳跃后位置相等写成 (m-n)t≡y-x(mod L)，再用扩展欧几里得求最小非负解；若 gcd(m-n,L) 不能整除 y-x，则无解。

把状态定义成“当前所在牧场 + 已改造道路数”。走一条边时要么正常付边权，要么消耗一次改造机会把这条边代价降成 0，在状态图上跑 Dijkstra。

把状态定义成"当前所在城市 + 已用卡数"。走一条边时要么正常通过，要么额外消耗一张卡把这条边代价减半，在这个状态图上跑 Dijkstra。

按牧场过路费从小到大加入 Floyd 中转点，维护边权和最短路；每次加入新中转点后，用“边权和 + 当前允许最大点权”更新所有点对答案。

先求出一条 1 到 N 的最短路。只有这条路上的边被封闭才可能让答案变大，因此依次禁用这些边并重跑最短路取最大值。

把已有电线当成 0 权边，把距离不超过 M 的点对当成可补的新边，在这张图上跑最短路求从 1 到 N 的最小补线长度。

先 Floyd 求每个连通块内任意两点最短路，再枚举跨块连边，用两端点到各自块内最远点的距离更新合并后的最小直径。

先求出一条从 1 到 N 的最短路。只有这条路上的边加倍后才可能让答案变大，因此枚举这条路上的每条边临时加倍，再重跑 Dijkstra 取最短路增量最大值。

只需要比较两种送货顺序：PB->PA1->PA2 和 PB->PA2->PA1。图是无向图，因此求出 PB 到两点的距离和 PA1 到 PA2 的距离后即可直接取最小值。

所有奶牛都要判断能否在 M 秒内到达同一个目标点 1，所以只需从 1 号草地做一次 Dijkstra，再按奶牛编号检查距离是否不超过 M。

这题不是最短路求和，而是最小化路径上的最大边权；点数只有 300，可以直接用 Floyd 的 min-max 转移求所有点对的最小瓶颈路。

往返距离等于 i 到 x 再加 x 到 i；原图从 x 跑一次 Dijkstra，反图再从 x 跑一次 Dijkstra，就能得到所有点的来回最短路。

利用无向图距离对称性，从每个喜欢的牧场各跑一次 Dijkstra，把到所有点的距离累加后取总和最小的牧场。

路径加可以先做树上差分，再把子树和展开成 diff 的加权求和；结合 LCA、DFS 序和两棵树状数组，就能在线维护路径加与子树和查询。

两点间最优通信稳定性等于所有路径中最小边权的最大值，这正是最大生成森林上的路径最小边权；先 Kruskal 建最大生成森林，再用倍增 LCA 查询路径最小边。

对每个节点预处理根到它路径上的 depth^k 前缀和，再用 LCA 把路径拆成两段：sum(x)+sum(y)-2sum(lca)+depth(lca)^k。

把每台电脑的度数看成点权，询问就是树上两点路径点权和；预处理根到每个点的前缀和，再用 LCA 把路径拆成两段即可。

把每个兴奋值看成一个状态值，若某个兴奋值 x 能选择一个结束兴奋值为 y 的游戏，就连边 x->y；某个游戏能玩两次，当且仅当它的 e_i 能回到某个整除 w_i 的同 SCC 状态。

关键线路一定是桥；先用 Tarjan 找桥，再统计桥两侧是否都同时含有 A、B 两种服务，只要某一侧缺少其中一种服务，这条桥就是答案。

先把同高且连通的格子缩成强连通块，块间只能从高处指向低处，缩点后是一张 DAG，最少缆车数就是入度为 0 的块数与出度为 0 的块数的较大值。

Tarjan 回溯时若树边 u-v 满足 low[v] >= dfn[u]，说明 v 子树必须经过 u 才能连到外部，此时把点栈弹到 v 再加上 u，就得到一个点双连通分量。