题目列表

按列拆解 N 进制加法竖式，从最高位向低位 DFS，用 0/1 进位链反解入进位并即时剪枝，直接得到唯一解。

以传播代数分层，把每层可切断的候选边集合状态化，位图记忆化搜索枚举本层切断选择，感染人数 = n − 救下的子树总大小。

环上断环成链，区间分段 DP：dp[i][j] 记前 i 个数分 j 段的最小/最大乘积，段和取模 10 作权值，复杂度 O(n³m)。

把分层神经网络看成 DAG，按拓扑序一次遍历：非输入层先扣阈值，只有 C>0 的兴奋神经元才把状态乘边权传给下游，最后输出出度为 0 且状态为正的神经元。

枚举（罪犯，星期）共 M×7 个假设，逐句把证词翻译成身份约束，检查无冲突且说谎者可恰好凑成 N 人，按候选数输出三态。

中序遍历固定为 1..n 时子树必是连续区间，区间 DP 枚举根求最高加分，并记录每段最优根还原前序遍历。

把字符串变换建成隐式状态图，双向 BFS 从 A、B 两端分层扩展，相遇处两侧深度之和即最少变换步数。

把每个机场建成图上的点：用直角顶点补出矩形第 4 个机场，同城连铁路、异城连航线，多源 Dijkstra 求 A 城到 B 城的最少花费。

每份得分只依赖两个端点：预处理 cut[t][j] 计数表，用 f[j][m]=max(f[t][m-1]+cut[t][j]) 恰好分成 k 份求最大值。

两条等长路径按反对角线同步推进，状态 (k, r₁, r₂) 消去列维、同格收益只计一份，O(N³) 滚动 DP 求最大取数和。

区间划分 DP：dp[j][i] 表示前 i 位放 j 个乘号的最大乘积，转移枚举最后一个乘号的位置，大整数用 Python 原生 int。

把有向沟渠网络看作流网络（容量=速率，源=1，汇=M），用 Dinic 的 BFS 分层 + DFS 阻塞流 + 当前弧求最大流。

把编号与幻灯片建成二分图，用匈牙利算法求完美匹配，再对每条匹配边删边判交错路，找出所有完美匹配公共的必须边。

把「每个王子能娶谁」化为二分图完美匹配的可行边问题：以给定初配构造交替有向图，非匹配边可行当且仅当两端同属一个强连通分量。

把小人与房子的最短步数（曼哈顿距离）作为权值，转化为二分图最小权完美匹配，用匈牙利算法 O(n³) 求出最少花费。

把「最少士兵走遍所有点且每点只走一次」建模为 DAG 最小路径点覆盖，拆点建二分图跑匈牙利算法，答案 = N - 最大匹配。

无向连通图求字典序最小的欧拉回路（按边编号）：Hierholzer 迭代版 + 每步贪心选编号最小的可用边 + 下标前进摊还，O(m log m)。

每行每列被墙壁切出的极大段当作二分图两侧顶点、空地格连边，机器人互不射击等价于匹配边不共享端点，答案即最大匹配，用 Hopcroft-Karp 求。

把环上滑动窗口建成 de Bruijn 图，每个节点只有两条出边，用 Hierholzer 算法求欧拉回路即得 M=2^k 的最短超排列环。

把每小时的 8 小时窗口需求写成上班人数前缀和的差分约束，二分总雇佣人数 total 并把它参数化进跨零点的约束里，建图用 SPFA 判正环决定可行性。

把每条路线看成「首尾车次」之间的一条无向边做 01 分数规划：二分四舍五入后的答案 r，把边权换成 2s−(2r−1) 后用 SPFA 判正环，图无环输出 −1。

把宝石划成若干个能量和为 0 的连通块：块内代价是子集最小生成树，再用子集划分 DP 合并出全局最小花费。

绳索等长时两个环最多拉紧的绳索数就是它们之间的最少绳索数，把题意翻译成无向无权图的点对最短路，Floyd 求全源距离后取最大即图的直径。

把每个城市拆成「相对最短路超出 0/1」两层状态，跑一遍分层 Dijkstra 统计条数，答案是最短路与次短路层条数之和。

把（楼层，手柄槽位）作为图上节点，扳槽与电梯移动拆成两类边权，Dijkstra 求从（1 层，0 号槽）到 N 层的最短时间。

把「贪心匹配一份 s2」压成一次确定性状态转移，再对「走 2^k 份 s2」倍增建表，在 O(|s1|²|s2| + |s1|log n1) 内求出最多能放多少份 s2。

把奶牛看成区间，用 dp[x] 表示铺满班次 1..x 的最少奶牛数；按右端点升序合并后，转移只依赖一段区间最小值，用线段树做到 O(N log T)。

固定列压缩的状压 DP：行内合法方案只有 60 个，按行推进时状态记录本行与上一行的列方案，新行的方案要求与这两行都不同列。

海拔排序双向链表 O(N) 求出每座城市东侧的最近与次近城市，再用倍增预处理「走 2^k 步后到哪、两人各开多少公里」，每个询问 O(log N) 跳跃回答。

断环成链后把 A_i+A_j+(j-i) 拆成 (A_i-i)+(A_j+j)，用单调队列在长度 N/2 的窗口里取最大左端点值，O(N) 求出最大代价。

环上选恰好 B 个小时，段首不计体力；状态只需「睡/醒」两维，按第 1 小时是段首还是续睡分成两条链，各做 O(NB) 滚动 DP 取最大值。

加虚拟根 0 把课程森林变成树，用树形背包 dp[v][j]（v 子树内选 j 个点且必选 v）逐儿子合并，答案取 dp[0][M+1]，O(NM)。

逐行扫描的轮廓线状压 DP：外层按行、内层逐格 dfs 填本行，竖牌记录向下伸出的列集合，横牌要求右侧格未被占，答案为填完 M 行且伸出集合为 0。

破环为链后区间 DP 同时维护每段的最大与最小值：枚举最后一次合并的分割边，四端点组合取最值；长度为 N 的弧对应第一步删边。

把机器人遍历记录切成每个节点的连续块：f[l][r] 记区间成块方案数，枚举首子块后的根记录位置 k 乘法切分，按奇数长度递推，O(|S|^3) 区间 DP。

树上最大权独立集：每个点只保留参会、不参会两档状态，后序遍历按 f[v][1]=H_v+Σf[u][0]、f[v][0]=Σmax(f[u][0],f[u][1]) 自底向上递推，答案取根的两档较大者，O(N)。

选 M 人使控辩总分差最小、总分和最大：以 diff=D-P 为状态维度的 01 背包（分层 DP），逐人更新并记录成员位掩码，O(N·M·range)。

把枚举合并顺序换成枚举最后一次合并的断点，得到区间 DP：f(l,r)=min(f(l,k)+f(k+1,r))+S(l,r)，按区间长度递推，O(N^3) 时间、O(N^2) 空间。

把每种硬币按 1,2,4,… 二进制拆成 O(log C) 组，再用大整数的比特位并行做可行性背包：reach |= reach << v，答案是 bit_count()-1。

先按贪婪度降序排序证明最优分配单调，再用 f[i][j] 的两种转移（全体减 1 块 / 末尾一段各 1 块）做 O(n²m) DP 并回推方案。

把子段异或和化成前缀异或对，用可持久化 01 Trie 把任意前缀区间与 x 的最大异或降到 O(31)，再按块三分区间、预处理两张端点表，单次询问降到 O(√N)。

一去一回拉直成两条同向路径，两条路全程共处同一条反对角线，用 f[i][j] 记两条路的行号把四维状态降到三维。

按行扫描的四状态 DP：左端点先减后增、右端点先增后减，连通约束化为矩形前驱区域，用区域最大值把转移压到 O(N·K·M²)。

最优 B 只需取 A 中出现过的数，按末位台阶做前缀最小值优化的线性 DP，正反两个方向各跑一次取最小。

把 LCIS 压成一维 dp：外层枚举 A 的值 x，内层一次扫描 B，扫描中维护所有 b[k]<x 的 dp 最大值 best，遇 b[j]==x 就写 best+1。

请求位必是三服务员站位之一，故按请求做 DP，状态只存三名服务员当前站位，每步在 3 个『派谁去』里取最小花费。

所有国家一起二分答案：同一轮里各国的答案区间互不相交，于是把每场雨归属节点后拼成一个数组，用 numpy 一次性完成区间加、单点查与国家汇总，O((n+m+k)log k log(n+m+k))。

逐个放人的阶梯状线性 DP：最高者必占 (1,1)，状态只需各排已放人数，前缀阶梯 + 列约束转移计数标准 Young 表个数。

把子矩阵和拆成 4 个二维前缀角点，CDQ 分治时间维 + 归并排序 x + 树状数组维护 y，三维偏序 O((M+Q) log²W) 完成带插入的矩阵求和。

点分治：每层在重心处统计所有经过它的路径，用 best[距离] = 最少边数 的定长数组代替哈希表，子树先查询后合并避免同子树内配对，总复杂度 O(N log N)。

把并集边界拆成水平、竖直两组，用扫描线线段树维护截面上被覆盖的极大区间个数，逐条带累加 2 × 区间数 × 条带宽，总复杂度 O(n log n)。

序列会被翻转、轮换、插入、删除，按位置组织的静态结构全部失效；用平衡树按中序维护显式序列，两次 splay 切出区间子树后打整树加与翻转懒标记，轮换化为三次翻转，每个操作均摊 O(log n)。

每天营业额的最小波动值（与之前某天差的绝对值最小）：数组式 Treap 逐日插入 + 最近值查询，期望 O(n log n)，避免递归爆栈。

线段树维护每段的 len/pre/suf/best（贴左、贴右、段内最长连续空房），入住时按「左孩子 → 跨中缝 → 右孩子」下降找最左空段，配懒标记做区间染色，单次业务 O(log N)。

分块预处理每个完整块对中正偶数种类数，询问时对两侧散段的互异值用「(值,位置) 排序键二分」算出总次数做二次补偿，强制在线下 O((n+m)√n)。

点分治：每层在重心处 DFS 收集各点到重心的距离，用排序加二分统计距离和不超过 K 的点对，再减去同一子树内部的点对完成容斥，总复杂度 O(N log^2 N)。

离线收集所有数值做坐标压缩，用树状数组维护计数数组，把六个操作全部归约成单点加、前缀和与树上二进制提升求第 k 小，总复杂度 O(n log n)。

把区间 [l,r] 的第 k 小看成两棵前缀权值线段树的计数相减，用可持久化线段树（主席树）在 O((n+m)log n) 内回答每个询问。

把罪犯拆成两个'域'，用扩展域并查集维护'分居两狱'的约束；怨气值降序处理仇恨边，第一条无法分居的边其怨气值就是答案。

静态区间众数强制在线：按 sqrt(n) 分块预处理「整块区间众数」表 + 每个值的有序出现位置，询问只枚举两端残缺块的值 O(sqrt(n) log n)。