题目列表

把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的文件。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

把观察条件改写为深度等式，按 LCA 拆两段路径，用桶与树上差分在 DFS 中统计每个观察员看到的人数。

等差数列区间加可拆系数用双 Fenwick 维护差分，也可用线段树等差数列懒标记，两者均 O(log n)。

线段树节点同时维护区间和与平方和，用懒标记支持区间加，方差由二阶矩公式 O(log n) 求出。

位掩码压缩集合 + 集合并运算，popcount 输出颜色种类数。

离散化后固定中间点，用两次树状数组扫描分别统计左小与右大个数，相乘求和得三元组总数。

用倍增 LCA 定位每条路径的公共祖先，再以树上点差分四个端点标记统一汇总，求出被经过次数最多的点。

区间加与区间和模板题，可用懒标记线段树或两个 Fenwick 树维护。

每个串压成 0/1 两个位掩码，线段树按位或合并区间约束，统计兼容二进制串数量。

从 1 号点 BFS，边权全为 1 时层数即距离，距离为 d 的点停止扩展并计数，一次遍历 O(n)。

最大堆和最小堆维护前缀的较小一半与较大一半，奇数长度输出最大堆顶。

两个堆维护已输出排名左侧与右侧元素，使每次 GET 的目标值位于右堆顶。

有修改的堆 1. 自己维护堆+桶 2. 堆的过时元素删除

Fenwick 维护当前不相交线段的起点，并按秩寻找可能相交的前驱和后继。

单调递增 deque 保存窗口内仍可能成为最小值的下标。

在差分数组上用 Fenwick 做两个端点修改，前缀和恢复单点值。

Fenwick 维护单点增量与前缀和，用两个前缀和相减回答区间和。

把当前国家与已学文化集合共同作为 Dijkstra 状态，并用集合包含关系做支配剪枝。

从初始格做八方向 BFS，最远可达草地的距离就是完全侵占周数。

把 12 个四进制旋钮压成整数，正反生成状态做双向 BFS 并恢复最短操作序列。

枚举前缀 / 字典树 / DP 三种方式求以每个单词结尾的最长词链长度。

KMP 统计 border 链长度，再用第二遍线性扫描限制前后缀不能重叠。

分别用合法姓名集合和已点名集合区分 WRONG、OK 与 REPEAT。

同一道顺序统计题给出三种解法：离线坐标压缩 + Fenwick、Python 版 FHQ-Treap，以及 C++ 版 FHQ-Treap。

周期和 border 是同一枚硬币的两面：最长 period = len - 最短 border，沿前缀函数链递推。

把树上路径异或转为两个根前缀异或，再用 01-Trie 求最大异或对。

把后缀异或改写为前缀异或区间查询，用可持久化 01-Trie 支持追加与最大异或。

可持久化 01-Trie 求每个右端点的第 rank 大异或，用堆归并取全局前 k 大。

采用贡献覆盖视角，把每个元素能接受的异或值区间在 01-Trie 上打懒标记，最后通过 DFS 下传求得最优解。

利用异或消去所有成对长度，并用 fread 流式读入满足千万数据和 8 MB 内存限制。

把 qiandao(x) 转化为 x-phi(x)，再用分段筛批量计算短区间内每个数的欧拉函数。

每加入一条大小关系就重跑拓扑排序，用队列分支数判断唯一序列并用处理点数判断矛盾。

从所有入度为零的生产者开始拓扑 DP，把路径条数沿捕食边累加到出度为零的消费者。

把逆序对看成二维偏序，从左到右扫描并用 Fenwick 加速值域桶统计。

按高度排名建立两列位置的对应排列，再把最少相邻交换次数转成逆序对。

按编号做字典序贪心，以区间调度倍增作为可扩展性判定，并用 Treap 维护空闲时间段。

筛出不小于 p 的质数，并查集合并区间内每个质数的所有倍数。

用姓名字典记录直接父亲，沿父链查找最早祖先并进行路径压缩。

离线压缩所有长度，用树状数组维护库存并按排名寻找最近的前驱和后继。

逐行构造空白高度，并用单调栈求所有以当前行结底的空白矩形数量。

先横向、再纵向运行单调队列，在线性时间得到每个 n×n 方块的最大值和最小值。

排序后用双指针求每个起点的最长合法区间，再用后缀最优组合两个不相交展示柜。