题目列表

使用DP计数恰好装满背包的排列方案数，先枚举容量再枚举物品，dp[c]+=dp[c-v]累加不同顺序的方案，对1e9+7取模。

多重背包模板题，数据范围扩大（N,V,s≤1000），需用二进制分组将每种物品拆分成 O(log s) 个 01 物品。

编号天然是拓扑序，按终点递推 f[i] = max(f[j] + a[i])，用 pre 数组还原最优路径。

每趟车建立虚拟节点压缩停靠与不停靠站的大小约束，再做拓扑最长路求最少级别数。

离散菜先做凹费用完全背包求每个整数重量的最优值，连续菜再把剩余重量写成分段二次函数最优分配，最后合并两部分答案。

先做一个容量 200 的 0/1 背包，求每个总 p 下能得到的最大总 k，再按回合数与 d 值差做极小极大动态规划。

先用完全背包预处理“花费 x 资源当秒最多新增多少采集效率”，再按时间推进 DP：dp[j] 表示当前手里有 j 资源时的最大已有采集效率。

先把可行性化成“所选挂钩总数至少是所选挂饰数减一”，再把挂饰分成必选、必不选和可选三类，对负收益但能加挂钩的部分做 0/1 背包。

把每段固定方向的时间看成一次行或列上的区间转移，设 dp[x][y] 表示当前位置最大滑行距离，再用单调队列优化每段的滑动窗口最大值。

状压 TSP：用 dp[mask][u] 表示已吃集合 mask 且最后停在 u 的最短距离，起点固定、终点不限。

先预处理 4 种硬币无限使用时的完全背包方案数，再对每个询问用 16 个子集做容斥，扣掉任意一种硬币超上界的方案。

付款方做有限硬币最少张数 DP，找零方做无限硬币最少张数 DP，再枚举实付金额取最优。

利用每条边都从小编号指向大编号的天然拓扑序，按编号进行 DAG 最长路 DP。

把每株草药看成只能选一次的物品，按时间做 0/1 背包；记忆化搜索填二维表，一维倒序 DP 把表滚动压缩。

先标记马所在格和马控制格，再用网格 DP 从上方和左方累加合法路径数。

把进位看成数位上的选择：每位取刚好够用的最小数字，用「当前进位状态 + 已用进位次数」的 DP 求最小 y，答案可达 10^35 需用 128 位整数。

把操作次数记成 c_u，颜色由 c_u 的奇偶决定、相邻两点满足 c_u <= c_{a_u}+[a_u=s]；在 s 所在的功能图基环树上做树形 DP，环上用前缀 max 转移。

把每个操作的值看成一段存活区间，先分块双指针求出每个操作被弹出的时刻，再在时间轴上扫描统计颜色数。

折叠一次后 t 变成关于中心对称的向量，之后每折叠一次只翻倍；于是 b 只能是 x·t + H·(t+reverse(t)) 的形式，解出唯一的非负整数 x,H 再验证即可。

每个瓜有「不买 / 买半个(劈一刀) / 买整个」三种去向，重量统一乘 2 化为整数后用折半搜索分别枚举两半并合并，求恰好凑出 2m 的最少劈瓜数。

每维只记录已被切掉的最大坐标，剩余部分始终是长方体，体积等于三个剩余长度之积，单次操作 O(1)。

最少操作数等于 n 以内无平方因子数个数；容斥化为 μ(d)·⌊n/d²⌋ 求和，对 d 分块并用杜教筛求莫比乌斯前缀和，压到 O(n^0.4)。

由 B=⌊A/V⌋ 反推出每条记录的 V 区间 [⌊A/(B+1)⌋+1, ⌊A/B⌋]，答案就是所有区间的交集。

按行优先逐格染色，每填一格立刻检查刚刚被确定的那个 3×3 数字约束，用黑格数与剩余格数上下界剪枝搜索。

按右端点线性扫描，用变量 cnt 单调维护上界 j-K+1 内 c1 出现的次数，遇 c2 累加 cnt，O(n) 计数。

日期统计用贪心找最靠左落点判断子序列，01 串的熵用单调性二分定位峰值附近的两个候选，两问都只需常数级计算。

状态图是一棵树：把第 k 个环的桥递归成 T_k = T_{k-1} + T_{k-1}，在树上用 O(n^2) 的区间 DP 求起点到终点距离。

A 题按「半长 + 数位和」统计并按乘法原理合并，B 题以「末尾连续答对数」为状态做线性递推，一次算出一句答案。

用“恰好出现 t 次的颜色种数”把子树判定降到 O(1)，再用 DSU on Tree 让父亲复用重儿子的统计，做到 O(n log n)。

子段异或和化为两个前缀异或的异或，再按位统计前缀异或中 0/1 的个数，用 cnt0×cnt1 累加每位贡献。

把“水往低处流”看成有向图的可达性，每个蓄水厂一次 BFS 求出它能灌溉的干旱区城市；可行时这个集合恰好是一段连续区间，于是问题化为区间覆盖贪心。

$x=y^2-z^2$ 等价于 $x$ 有同奇偶的因子对，即 $x$ 为奇数或 $4$ 的倍数；用前缀计数 $F(R)-F(L-1)$ 即可 $O(1)$ 求出答案。

二分答案，倍增 LCA 求路径长度，树上差分找所有超标路径的公共边并比较最大公共边权。

二分木材长度，统计总共能切出的段数是否至少达到 k。

二分最短跳跃距离，贪心统计给定距离下最少需要移走的石头数。

把极大极小乘积按 B 区间符号分三类讨论，只需在 A 区间查询最值、最小正数、最大负数和是否有零。

按开始时间排序后，用小根堆维护每个牛棚最后占用的结束时间；堆顶能空出就复用，否则新开棚，得到最少牛棚数与一套合法分配。

两条航道交叉等价于两岸坐标的顺序相反；把友好城市按南岸坐标排序后，问题变成求北岸坐标序列的最长严格上升子序列，用二分手写 LIS 做到 O(N log N)。

两个排列的 LCS：把 P1 的值映射成它在 P1 中的下标，P2 就变成位置序列，公共子序列恰好对应它的严格上升子序列，再用 tail 数组加手写二分求 LIS，总复杂度 O(n log n)。

前缀 DP：f(i,j) 表示两个前缀的 LCS 长度，字符相等时取 f(i-1,j-1)+1，否则取上侧与左侧的较大值，答案是 f(n,m)。

将连续用户压缩成可动态撕裂的区间块，本质是区间映射: 每次撕裂出一个单点

把被摧毁的房子看成断点，用有序集合维护断点，查询时求左右最近断点使答案等于 R - L - 1；给出 FHQ-Treap 与 std::set 两种实现。

用隐式 Splay 或隐式 FHQ-Treap 维护序列顺序，通过双哨兵或按排名分裂实现区间翻转。

使用01背包DP，dp[c]表示容量c时的最大总价值，容量倒序枚举确保每件物品只选一次；同模型的 Python 写法因 3 MB 内存限制必然 MLE。

比较 n、n^2 与 5×10^8 的关系，按复杂度从高到低输出能够通过的最高级别。

利用兑换门槛不超过 20，把可达钱数拆成低状态和统一平移的高状态，特殊机器再合并至多三份集合。

每次合并当前最小的两堆果子，等价于构造 Huffman 树；可用小根堆维护，也可排序后用两个普通队列 O(n) 完成合并阶段。

DFS 回溯枚举所有简单路径，按 上左下右 方向序输出全部路线，无路输出 -1。

用倍增表 up[u][j] 记录 2^j 级祖先，查询时先提深再同步跳，单次询问 O(log n)。

递归解析方括号结构，遇到 [D... ] 时先展开内部字符串，再重复 D 次拼接。

先求树的直径，在直径上用双指针枚举长度不超过 s 的核区间，偏心距由两端距离与分支最大深度决定。

对每个中间点聚合邻居权值，用 S²−Σw² 得到距离为 2 的有序点对总和，用前两大权值求最大值。

用线段树双懒标记维护区间赋值与区间加，赋值覆盖加法、下传先赋值后加，查询区间最大值 O(log n)。

用线段树双懒标记（赋值覆盖翻转）维护 01 序列，节点存 0/1 两套前缀后缀与最长连续段，单次操作 O(log n)。

把区间乘和区间加统一成仿射懒标记，维护模意义下的区间和。

用翻转懒标记维护区间亮灯数量，整段翻转时数量取反、标记异或，单次操作 O(log n)。

用线段树维护区间和与最大值，整段最大值不超过 1 时剪枝跳过开方，摊还 O(log n) 级单次操作。

线段树维护区间和、最大前缀、最大后缀和最大子段和，支持单点修改。

线段树节点维护区间两端值与最长交替前后缀，合并时按跨中点边界是否交替拼接，单点翻转 O(log n)。

把格子按高度关系看成 DAG，用记忆化搜索计算每个格子出发的最长滑坡，每个格子只算一次。