题目列表

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

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

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

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

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

网格 BFS 求单源单汇最短路，边权为 1，墙壁不可通过。

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

枚举两个方框的 3×3=9 种运算符组合，逐一计算验证是否等于 d，常数时间。

每次操作删一个元素，上界 n-1；序列不全相同时总能通过改成全新值续命，答案为 n-1 否则 0。

贪心切分：存在最优解每段长不超过 2，与上一段冲突时取双字符段，O(n) 扫描。

f(u,v,i) 为 i 到 u-v 路径的距离，闭式化简化得答案 = D*(n-2)/2，D 用边贡献 size*(n-size) 累加。

操作等价于环上交换相邻差分；好位置数=正差分段数，把正差分聚成一段的最少相邻交换用中位数公式 O(n) 求。

按 kirai、daishuki、shuki 的优先级检查子串并顺序模拟气压变化。

比较分段模拟和树状数组三种维护当前序列的方法，正式主解用树状数组 kth 定位动态排名。

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

把棋子更新转化为长度恰好 n 的反向可达，用有向环加通向 k 的路径构造方案。

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

引入偏移量，把每个砝码可放左边(-w)或右边(+w)转化成带偏移的可行性背包，dp[sum]=true 为初始，统计正可达重量数。

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

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

把1..N分成和相等的两堆→0/1背包计数dp[target]，总和奇数直接0，最后结果除以2去重。

每个好友打不打都获经验，按药水量做 01 背包变体——打输也得 lose_i 经验，dp[j]=max(dp[j]+lose_i,dp[j-use_i]+win_i)。

二分最小文件大小限制L，每次check用0/1背包判断在容量S限制下能否装下价值≥p的文件。

先枚举纸币再枚举金额做完全背包计数，不同支付顺序合并为同一种组合，dp[j]=(dp[j]+dp[j-v])%MOD。

先枚举金额再枚举纸币做完全背包计数，不同支付顺序视为不同方案，dp[j]=(dp[j]+dp[j-v])%MOD。

把每种纸币看作可以无限使用的物品，dp[j]=min(dp[j],dp[j-v]+1) 正序枚举金额求最少张数。

先求出全部物品的方案数f[j]，再对每个物品i用g[j]=f[j]-g[j-w[i]]推出不含i的方案数。

01背包和完全背包混合：根据类型标记分别用倒序（01）和正序（完全）转移，同一次dp内完成。

在容量和承重两维约束下做01背包：dp[j][k]表示容量j承重k的最大价值，两维均倒序转移。

每组最多选一个物品：保留上一组状态previous，对当前组每个物品从previous转移，避免组内互窜。

树形依赖背包：dp[u][j]表示子树u容量j的最大价值，递归时先选u再对子节点分配容量做类分组背包合并。

物品价值随分配容量变化：分段线性插值得val[c]=f(c)，然后倒序DP对所有容量c尝试分配x容量得val[x]。

通过从后向前 DP 得到最优值，再从前向后贪心回溯，优先选取编号小的可行物品，输出字典序最小的最优方案。

先 DP 得到二维最优值表，再用 DFS 回溯所有能走到最优值的分支，收集全部最优方案并按字典序输出。

在 01 背包 DP 的同时维护方案计数 dp2，dp 值更大时覆盖计数，相等时累加计数，滚动数组倒序成组。

dp 初始值区分可达与不可达：dp[0]=0 可达，其他 dp[c]=-INF 不可达。只有从可达前驱转移才参与计数。

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

使用完全背包DP，dp[c]表示容量c时的最大总价值，容量正序枚举支持每件物品无限次使用。

多重背包模板题，数据范围很小（N,V,s≤100），直接三重循环 DP，每个物品枚举选取件数即可。

使用01背包DP判断容量V是否可达，dp[c]记录容量c能否被某组物品恰好凑出，容量倒序枚举。

使用01背包DP计数恰好装满背包的方案数，dp[c]+=dp[c-v]累加组合方案，容量倒序枚举，对1e9+7取模。

使用完全背包DP判断容量V是否可达，每种物品无限件可用，dp[c]记录容量c可否凑出，容量正序枚举。

使用完全背包DP计数恰好装满背包的组合方案数，每种物品无限件，dp[c]+=dp[c-v]，容量正序枚举，对1e9+7取模。

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

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

多重背包模板题，数据极大需用单调队列优化，按体积余数分组，滑动窗口维护最优前驱状态，O(NV)。

按 v 排序消掉 max，每头牛只与前面牛配对，两个树状数组维护坐标数量与坐标和。

每个圆盘的溢出去向唯一（下方第一个更大直径），构成链式森林，倍增 + 容量前缀和回答查询。

分治求最近点对：左右递归取 d，合并时只检查分界线 d 内窄条，按 y 排序相邻比较。

子树变 Euler 区间版本差，路径用根到点版本四根容斥，可持久化 01-Trie 回答最大异或。

经典 BFS 网格可达性：从 (1,1) 出发逐层扩展，判断能否到达 (n,m)。

每个格子指向唯一下一格的函数图，用三色标记 DFS 记忆化判环，q 次询问 O(1) 回答。

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

并查集判断设计图是否为一棵树：任意两点有且仅有一条路径，即无环且连通。

每行 A[i]+B[j] 有序，用最小堆多路归并 N 条有序流，弹 N 次取最小 N 个和。

前缀和 + ST 表区间最值 + 堆分裂区间，贪心取前 k 大子数组和。

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

用 DFS 枚举不下降序列，统计把 m 个苹果分到 n 个盘子的不同分法数。

用按高度滚动的动态规划合并连续点击与重力转移，并在管道位置过滤非法高度。

用 Python 整数位集加速 Warshall 传递闭包。