题目列表

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

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

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

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

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

非递减的最终串只能是 A…AB…B 的形态，枚举分割点并用前缀和 O(1) 计算翻转代价。

二分答案：时间 T 可行等价于每个人的可达区间有公共交点，判定只需比较区间左端点最大值与右端点最小值。

3×3 小矩阵只有 3^9 种形态，把每块压缩成三进制整数用 bool 数组标记，O(1) 去重计数。

先默认全部不带走，每本书改带走只改变 d_i=a_i-b_i，问题变成从 n 个数里取至多 m 个正数使和最大。

值域只有 1~50，排序后相邻差 ≤1 等价于难度值连续不断档，答案是从区间最小难度到第一个空档的出现次数之和。

三连判定只看相邻 3 列，把每列压成 3bit 图案加 3bit 已计入标记，做 3 列滑窗的带状状压 DP。

正难则反：指定坏点后序列碎成段内同值的独立段，容斥计数，再用单调栈维护后缀最小值阶梯把转移压成 O(1)。

x、y 两个方向独立取最小外接矩形，边界不算罩内且角点必须为整数，恰好把每条边强制外扩 1 格。

把单词的每次出现看成一条最多拐一次 90° 弯的路径，枚举起点与初始方向，顺着路径逐格匹配计数。

无限循环播放只是周期重复，先用 c mod L 折回单周期，再把压缩串解析成段并用前缀和定位对应音符。

单窗口内按 b 降序排队可证最优，全体排序后退化为 0/1 分配问题，用背包式 DP 求最小完成时间。

合法划分等价于全或 T 的每一位在 A、B 中都出现；容斥数坏事件，坏事件交集用并查集压成 2^连通块数。

f(i,j) 是 y_i、y_j 的加权平均，取值有界可二分；f(i,j)≥v 变形为两个序列的比较，排序后双指针 O(n) 计数求第 k 大。

图形对称等价于染色集合在镜像变换下封闭，把每个红格子的镜像格子也标记出来，逐格检查一次。

模拟十进制舍入：每步把当前数舍入到 10 的幂，逢 5 进位；低位进位会改写高位，必须对当前数连锁进位。

经典 LIS 贪心表的变体：同一位置的候选值先统一评估再统一写回，避免同一位置的候选值互相接龙。

树贪心：权和恰为 k 的连通块等价于权和 ≥k 且奇偶性与 k 相同，后序遍历维护未切区域 O(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取模。