题目列表

把魔杖状态压成「距上次释放的秒数 -> 最大生命值」，再用 cd 单调性二分答案，每次 O(n^2) DP 判可行。

把行、列的整体加减记成整数 r、c，限制化为 r_x+c_y=c 的差值等式，用带权并查集维护点值差并在同集合时判矛盾。

把每块圆盘看成「木桩×圆盘种类」的带权点，相交或相切即连边，触底盘与触顶盘分别当源点和汇点，跑一遍点权 Dijkstra 求最小花费。

把三种记忆化成 x_v≤x_u+w 的差分约束边，加超级源点后用 SPFA 判负环：无负环则输出 Yes，有负环则输出 No。

每条路径的耗时是拥堵系数 a 的直线，期望最短路即这些直线的下包络在 [0,1] 上的积分；用凹函数中点弦值判定递归细分，分段梯形积分。

把 f[i]=min(K_i, S_i+Σf[son]) 看成超图上的最短路：全部先取法术代价 K_i，再沿反向边把「变便宜了多少」SPFA 式地推给会产生它的怪兽，收敛到最低不动点。

把边按边权升序排序后逐边做 DP 松弛，f[a][v][k] 表示从 a 出发走恰好 k 条非降权边到 v 的最小和，最后对 k 取前缀最小、询问 O(1)。

把线路 i 的位置 j 看成相位固定的班次，等车时刻为 d+((j-d) mod t_i)，在站台图上按“早到不劣”跑 Dijkstra，边权松弛时实时算、不显式建图。

01 分数规划把平均权值最小化转成判负环，边权改成 w-λ 后多源 SPFA 二分出答案，无环单独判。

用 min-plus 矩阵幂预处理好「最多 2^k 条边的最短路」，再按位从高到低贪心逼近最小负环边数，O(n^3 log n)。

把模式串建成 AC 自动机，对每个非终止态列出 E[u]=1+(1/26)ΣE[δ(u,c)] 的线性方程组，模 1e9+7 高斯消元解出根的期望步数。

询问 [i,j] 的奇偶性等于前缀异或 S_{i-1} xor S_j，定出全部 x_i 等价于把 n+1 个前缀点连通，答案是该完全图的最小生成树。

四次 Dijkstra 求出两组最短路的四个距离数组，筛出同时落在两条最短路上的点与边，答案即公共最短路 DAG 上的最长节点链。

把每个点拆成最短路与严格次短路两个状态跑 Dijkstra，最短路退位时条数一起搬走，答案取最短路条数加次短路恰好多 1 的条数。

边权为 u·k1+v·k2 的 MST 只依赖 (Σu,Σv)，把全部生成树点投影到左下凸壳，用「沿弦法向做 MST」的分治补全凸壳后每次询问二分定位。

答案等于所有使「只留权值能被 d 整除的边后图连通」的 d 的最小公倍数，枚举 d 用并查集判连通即可。

目标串 t=s+'*'，每次操作只能选一个字符，故选择次数固定为 |t|，只需最小化滑行次数：按目标串分层做多源最短路，答案 = |t| + 最少滑行数。

把无限链看成禁止串 AC 自动机上的双无限路径，缩点成 DAG 后按「环 SCC 起、有限路径、环 SCC 收」数路径，遇多环或非简单环环节则判无穷。

把愉悦度化为 P 之和除以 MST 权值减树路径最大边，用 Kruskal 升序合并、并查集顺带维护分量最大 P，一次扫描覆盖所有点对。

把 S 的全部前缀视为 trie 上的结点得集合 P，好串即 P·P；用 AC 自动机 fail 树的子树大小扣掉同一串的重复切分，答案从 |P|² 中扣除。

无限棋盘上按 n 个向量走最短步数，BFS 只保留贴着起终点连线走廊（宽度为单步最大长度）的点，状态数降为 O((|dx|+|dy|)·√D)。

把树边按权值升序做 Kruskal，每次合并两块补 sx*sy-1 条权 w+1 的非树边，累加得最小完全图边权和。

把「相邻两数差不为 1」记成断点并补上虚拟的 n+1，断点数就是可采纳下界，用迭代加深 IDA* 逐层加深求最少前缀翻转次数。

反对称串由前 m 位 T 唯一确定；把 p 与 ~reverse(p) 一起建成 AC 自动机，用 2^n 掩码逐位 DP，跨中点的命中留到末尾结算。

把串看成 trie 状态，纠缠即 Myhill-Nerode 右语言等价，用并查集合并状态并沿 10 条出边做同余闭包，查询时每步跳到代表元。

每天的字符串集合是前缀封闭的，恰为一棵 Trie 的结点集；编辑距离就是树上距离。三天答案化为子树大小、换根距离和与一次 LCA 配对 DP。

把环展成 s+s 并按相邻相同的断点切段；段内长为 m 的子串只有首尾可能冲突，用 KMP 的 border 链一次扣掉全部坏长度，得到 O(n)。

禁止子串建 AC 自动机得到 DFA，删掉危险状态后在安全状态间建重数转移矩阵，矩阵快速幂求长度 n 的合法串数。

利用循环左移与异或可交换，把对手的每个出手时刻化成常数 C_i，问题变为选 y 使 min_i(y^C_i) 最大，用 01 字典树自底向上 DP 求值与方案数。

编码是一个字母对合映射；子串 U 能编码成 T 当且仅当二者模式同构且诱导双射满足对合律，用换比较规则的 KMP 找同构窗口再逐字母验对合。

给两棵树设计可加的 64 位树哈希，换根 DP 求出 A 的 n 种根哈希存入集合，再逐个删掉 B 的叶子用 O(1) 撤销算出剩余哈希查表，取编号最小的叶子。

把二维第 k 大按最高位贪心拆成逐位计数，用可持久化 01-Trie 上的前缀版本差得到区间按位个数，n 个 X 的指针整排一起下钻。

把集合建成字典树，树上求 f[v]=儿子答案之积+[v 是词尾]，排序后用相邻最长公共前缀代替建树，答案即 f[根] 对 9191 取模。

把权值换成序号后每结点 4 位压成 64 位状态，在 M 种交换构成的排列图上 BFS，首次生成合法大根堆排列的层数即最少交换次数。

把 F 的计数按 |S|≤|T| 与 |S|>|T| 两类拆开，用 Manacher 差分预处理回文前缀/后缀计数，再用哈希二分求 LCP，单次询问 O(log n)。

由满分/零分人数反推候选答案串的出现次数，p=q=0 时在禁止集合上用前缀计数贪心构造字典序最小的可用串。

把每个字符换成到上一次出现位置的距离，按窗口长度裁剪后做广义 KMP，O(n+m) 数出 s 中与 t 同构的子串。

把一种含义看成若干互不重叠的 t 匹配，用前缀函数求出 t 在 s 中的全部结束位置，再按最右匹配分类做线性 DP 统计。

带负权边的有向图求 1 到 n 最短路：SPFA 只把距离刚被改小的点入队做松弛，队列空即最优；距离必须开 64 位，答案可达 -2e13。

把 KMP 的 fail 数组看成以空前缀为根的树，长度 i 的前缀出现次数正好是节点 i 的子树大小，累加全部偶数长度的子树大小即可。

把问题退化成 6×6 方格切割：6*6、5*5、4*4 各占一箱、3*3 每四个一箱，再用查表算出剩余 2*2 槽位，最后按总面积补 1*1。

双模滚动哈希把每个长度为 m 的子串压成一个整数，排序后计数互不相同的哈希值个数。

逐位贪心试字符，配一趟按最后逗号位置递推的可达性判定，每个位置只留左端最小数即可判定能否补全。

状压 DP：dp[S][p] 记已取集合与停留格的最大得分，转移为走相邻未取格或在边缘格离开方格重新入口，取数得分按 k×value 累加。

先从 n 反向 BFS 求各点到 n 的最短边数，再从 1 出发按层在出边里取最小颜色并只保留走完剩余最短路的点，得到字典序最小的颜色序列。

把积水高度写成逃逸水位减地形高度，逃逸水位是从格子走到外围的 minimax 路径，用多源 Dijkstra 从边界一次算完。

从左往右扫描表达式，左括号入栈、右括号弹出配对；中途栈空或收尾栈非空都判 NO。

把 20%/30%/50% 放大成整数权重 2/3/5，直接算 (2A+3B+5C)/10；三项成绩都是 10 的倍数，整除成立，全程整数运算避开浮点误差。

把圆圈按报数方向摊成队列：报数就是队首出队，没数到排回队尾，数到就淘汰，新队首即下一轮起点。

盘子相同就按非增序列去重，答案即 M 拆成不超过 N 个部分的拆分数；按「是否有空盘」分类递推打表，每组询问 O(1)。

把每组文字段与数列看成字母到数字的部分单射，两组相容就连边，答案化为 40 点相容图上的最大团，用位掩码加分支限界求解。

先用度数全偶筛掉奇点，再用并查集检查所有有边的点是否连成一片，$O(N+M)$ 判定无向图欧拉回路的存在性。

读懂题面的异或求和程序后，用 Floyd 在 O(n³) 内求出全部点对最短路，不可达保持 10¹⁶，逐对把 Dis(i,j)+f 异或进 S。

无向连通图求 1 到 n 的最短路：链式前向星存双向边，小根堆优化 Dijkstra 出堆即定稿，距离用 long long 扛住 2e14 量级。

按定义直接三重循环：C[i][j] 是 A 第 i 行与 B 第 j 列的点积，枚举 i、j、t 累加，时间 O(nmk)。

外卖路线的取舍决策最大净赚：区间记忆化搜索 best(l,r,side,passed)，每步决定当前端客户送/放弃并走向下一端，移动成本随未决客户数增长，O(n^2)。

无人机沿路线配送使总代价最小：按位置排序后区间 DP（l,r,端点）逐位扩展，扩展代价=未送客户的 d 和×距离/v，全程整数分子避免浮点误差，滚动数组 O(n^2)。

首次经过即送达使已送客户构成含起点的连续区间，区间 DP 记录区间两端与人在哪端，走路代价乘未送达生气值之和完成转移。

亲戚工资无条件照付并把每道菜覆盖数封顶到 2，按工资升序逐个决定雇不雇零工，用（恰好一人的菜，已满员的菜）双 bitmask 做 0/1 背包式 DP。

神曲最长必放最后，问题化为容量 t-1、先比首数再比总长的 0/1 背包。