题目列表

环形舱室切成 K 段使段长和方差最小。方差乘 K² 后只需最小化段长平方和：小 N 枚举断环起点做斜率优化 DP，大 N 的 K 只为 2 或 3，双指针逼近 S/K 切点。

把切点合法性等价化为「前缀 b 最小值 > 后缀 a 最大值」压成原子段，再二分答案并用单调队列加可重集做判定 DP。

把评价指数拆成 G[j] 乘前缀和，固定班数后断点项与 i 无关，用单调队列维护滑窗最小值，O(NM) 求出最小评价指数，再按班数、末班人数依次取优。

把「k 个宽 w 的球」看成数轴上 k 个长度 w 的区间，按最后一个球的右端点设计 DP，重叠项用单调队列取区间最大值，做到 O(nk)。

体积只有 300 种，按体积分组取价值最大的前缀；固定余数把容量拆成独立链后，前缀和的凹性给出决策单调性，用分治优化把 O(nm) 降到 O(n log n + Σ m log(m/s))。

先证山谷集合必是八连通独立集，再用容斥把“恰好为 X”化成“含 X 的独立超集全为山谷”，每个超集在 2^{|T|} 个前缀状态上做子集 DP 求偏序线性扩张数。

按 v 把限制分层，每层用并集面积差定出可填 v 的格子，再对同值矩形做子集容斥，各层相乘。

取反层间连边等价于把邻接矩阵转置，只关心源点到各点路径条数的奇偶性，用 2^k 个奇偶向量作状态做状压 DP 计数方案。

状压 DP：f[点集][叶子集] 统计恰含 k 个叶子的生成树，靠「每次只剥离编号最小的叶子」保证每棵树恰被计一次。

0 起编号后白格当且仅当 i&j==0，白格构成的四连通图是一棵树；矩形内连通块数等于父亲越出边界的白格数，用数位计数 O(log C) 求出。

按算子分治：与用逐位贪心加超集计数，异或用 0-1 Trie 求最大异或对，或用值域超集变换加逐位贪心，三者都是 O(20n) 级。

用背包 DP 统计数位和分布 f[k][s]，容斥后答案 = 2Σf[n][s]² − Σf[⌈n/2⌉][s]² · Σf[⌊n/2⌋][s]²。

用 f(n)=#{j<n: popcount(j)=k-1} 把合法 n 压成一段连续区间，位贪心求第 m 个候选数，O(log n) 得最小 n 与解的个数。

树形背包：把一条起点到终点的路线拆成最多两条开口的腿，三态 DP 合并儿子求带主路径的连通块最大收益。

树上随机游走的期望步数可沿路径相加：向上 f[x]=deg[x]+Σf[儿子]、向下 g[c]=g[x]+f[x]-f[c]，配树上前缀和与倍增 LCA 做到 O(1) 回答每个询问。

以任意点为起点在树上并行扩散消息，用两次树形 DP 求出每个点的子树与父亲方向耗时，换根时靠前后缀最大值 O(1) 剔除一个方向，取最小值加 1 即答案。

把树形限制拆成祖先约束与兄弟链约束，按后序遍历自底向上做树形 DP，倒序合并兄弟子树，用组合数 C(N_i-1, sz_i-1) 统计跨子树插空。

先手第一步之后局面被「两端取较大者」完全确定，答案写成交错和；再把同侧连取整段压成一次「区间内第一个小于 t 的位置」线段树查询，O(n log n) 求出全部起点。

把逐行的零和博弈化成区间扫荡模型：Bob 只能在一段连续的门区间内逼 Alice 折返，自下而上倒推最小罚分，O(n·m³) 足够。

M≤15 时异或只改距离的低 4 位，用换根 DP 同时维护距离和与距离 mod 16 的分布，O(16n) 求出每点到全树的花费之和。

矩形底边都贴在 y=0，故存在「底边区间相离或包含」的最优解；按此性质对最左列做区间 DP，按高度分层转移，O(nn³m) 解决。

从恒等排列出发按 q 的顺序做 n-1 次相邻交换，倒着钦定每个区间最后使用的边，左块值域必须对齐，两段操作可自由交错，答案由区间 DP 乘组合数归并系数得到。

把最后被取走的一批当作区间骨架，其余元素被它切成互相独立的空隙；用 g[l][r][x][y] 记「留下含 l 的一批、其分数排名夹在 [x,y] 内」的代价，区间 DP 即可。

用斐波那契加法公式把按深度加 Fib(k+D) 拆成两个静态系数，子树区间差分套树状数组，路径和转为根前缀和与 LCA。

利用区间合并后残留长度恒为 (len-1) mod (k-1)+1 这一不变量，把长度不超过 k-1 的残留 01 串整个压进区间 DP 的状态，分割点以 k-1 为步长枚举。

DFS 序把子树化为区间；用 n 位颜色位集表示一段区间的颜色集，位置分块后由线段树维护块位集的并，询问只需 O(log nb) 次或加两侧暴力扫描。

树链剖分把路径拆成 O(log n) 段连续 dfn 区间；线段树懒标记把等差与公比 2 等比统一成「锚定两端的 2 的幂 + 一次函数」，任意模数 P 下都不求逆元。

点分治把树上距离按点分树 LCA 拆开，每个重心预处理管辖块的编号升序点表与距离前缀和，询问沿祖先链二分求区间距离和。

把「恰好含一条树边的割」化归成 T-e 两侧的割，用树上边差分统计每条树边被多少条非树边跨过，答案即最小覆盖数加一。

把管辖关系建成森林：parent(i) = LCA(B_i)，管辖集 S_i 就是根到 i 的路径；询问按 DFS 序排序后套虚树恒等式求根路径并大小。

带权树每个子树求偏心距最小的点的偏心距，即子树半径，用树形 DP 与长链剖分求中点。

树上最远边境城市距离由直径两端决定，再用树链剖分加线段树在路径上二分出第一个安全系数达标的城市。

把 c=1 的边当成待消的奇偶约束：每个连通块内生成树边放双份补连通、奇数度点接一个虚点，跑欧拉回路并按虚点切开，即得最少人数。

把台阶分给两条从地面出发的链，代价是各链绝对差之和；用「一条链停在 H_i、另一条停在 x」的 DP 加锥形下包络，两棵树状数组维护前缀最小做到 O(n log n)。

最小生成树即最小瓶颈生成树，把每次询问化归为树上路径最大边权，用倍增 LCA 在 O(log n) 内回答。

两个区间只要交集长度大于零就能互相走到，于是可达即无向连通：并查集维护连通块，再用按左端点有序的表把每个连通块压成一段线段并在线合并。

按 D 排序把值域区间变成下标区间，用区间多项式 Π(1+V·y) 的系数表示初等对称和，容斥除掉最小 V 后乘 K!。

把一段连续操作抽象成需求函数 F(x)=max(need,x+cap)，线段树合并三个字段，单点修改后根的保留和即答案。

把 C[i][j] 恒等变形为 (A[i]+i)(B[j]+j)，行列最大值即可分离，再用单调栈统计每个元素被各长度窗口计入的次数、差分还原全部 F[k]。

把串切成同字母的连续段，每次排序先二分定位区间内的段、统计 26 个字母的计数，再按升/降序整段铺回，段数均摊 O(n+26m)。

固定右端 r，合法左端只能是左侧最后一个身高不低于 a[r] 的位置之后的最小值，用两个单调栈加一次二分做到 O(n log n)。

把 m 条子串相等限制化成位置的并查集，用倍增分层（ST 表思想）把每条限制压到 O(log n) 次合并，最后按连通块数算 9×10^(t-1)。

对矩阵做二维稀疏表：先按行合并再按列合并，每次询问用四个 2^a×2^b 方块 O(1) 完全覆盖矩形取最大值。

组队条件只看队长：预处理每人当队长时的最大组队人数，再把询问按地位阈值离线，用年龄离散化 + 线段树区间最大值回答。

统计排列中 132 型三元组：一遍正序扫描，树状数组给出左侧更小个数，借“元素互不相同”反推出右侧更大个数，边扫边累加 C(last,2)-pre·last。

把 gcd 为合数翻译成共享「见证数 pq / p²」，在原点加见证数的二部图上跑 Tarjan 求割点子树，逐个点算出删点后的最大连通块。

在值域上用树状数组维护可合并信息 (长度, 方案数)，合并时长度大者胜、等长则方案数相加，空段记为 1 种方案，O(n log n) 求出最长严格上升子序列长度与方案数。

把全部①要求原样连成图，缩点后按逆拓扑序做分块 bitset 可达性，检查每条②是否被传递闭包满足，满足即无解。

把叉积平方和展开成 (Σx²)(Σy²)−(Σx·y)²，用树状数组同时维护三个分量，单点改速度与区间询问都是 O(log n)。

每站把两条入边与两条出边配成接续即得线路的分解；先取局部最省配对得到若干环，把翻转每站的代价当边权，用最小生成树把环并成一个完成枚举。

片段逼出「每条弧的唯一后继」，粘合成链后收缩成超边，再在收缩图上判从路口 1 出发的欧拉回路：逐点入度等于出度且带边的点弱连通。

答案拆成与删边无关的基线 T0 加上桥的贡献 s*(C-s)：并查集算 T0，迭代式 Tarjan 求桥与 DFS 子树大小，回答每次询问 O(1)。

度数不超过 3 时点对最大流只可能是 0/1/2/3，用并查集、边双连通分量与「删每条边后的边双划分」三层等价类分别数出流量至少 1/2/3 的点对数。

Tarjan 边栈求点双：桥即不在任何简单环上的边；块内边数大于点数时块内每条边都在至少两个简单环上，累加这些块的边数。

把区间连续化为 l + cnt(l,r) == r，扫右端点用线段树维护 mx[l] 的前缀最大值，询问按右端点分桶后按 x 递减结算，得到最短连续区间。

把“x 集合严格大于区间内其余位置”翻译成差分约束，用线段树把区间连边压到 O(log n)，拓扑序推出每个位置的下界即为可行解。

tarjan 求割边把图缩成边双与桥树，src→dst 在桥树上的唯一路径里只要有权 1 的桥或内部含权 1 边的边双即 YES。

先求最大匹配，再在按匹配边定向的交错图上用强连通分量与自由点可达性判定每条边是否属于某个大小为 n 的匹配。

把月度收入换成前缀和 s[i]，每条记录即 s[y]-s[x-1]=w；等式组化成差分约束判负环（带权并查集同样可判），矛盾则输出 false。