题目列表

把车票拆成车厢、排号、过道侧、侧内下标四项，按题目给的四个条件逐层判断。

答案是不匹配的对称位置对数；用双指针在行程编码两端同时向内走，整段记账，不展开字符串。

按测试点分档推进：枚举组合 → 固定 m 的四个特判 → 值域开桶的超集计数 → 从高到低逐位贪心，全范围 O(30n)。

每局结束的桌面等于一条跳转链：T[i] 由 a[i] 与 T[最后一次出现 a[i] 的下一个位置] 拼成，统计链被经过的次数即可。

用 itertools.product 枚举 10 种配料各取 1 到 3 的所有状态，筛出总和等于 n 的方案。

Tarjan 缩点得到 DAG，统计入度为 0 的 SCC 数量，检查是否存在 size=1 且后继入度均大于 1 的可省略分量，答案为 1 - must/n。

倍增把三角形按 2 的幂拆块求最值：主解只用正三角形，6 个同尺寸块补上空隙（图解 + 2 层滚动，内存稳定）；备选引入倒三角形做 DAG 分解（小 k 更快但内存高）。

枚举每条断边，两侧各求重心：沿“最大子树”方向下降的路线唯一，用重儿子链上的倍增跳表 O(log n) 定位；换根时只有当前端点需要重算重儿子与跳表。

以 1 为根求一次深度和与子树大小，再沿父子边换根：D(v) = D(u) + n − 2·sz(v)，两遍 O(n) 扫完整棵树，取深度和最大的点。

距离和最小的点即树的重心：用重心模板求重心再算距离和；换根 DP 递推全部点的距离和；最省的一版只跑一遍 DFS，从根沿重子树下降到重心，边走边累加增量。

树链剖分把路径变区间，宗教过滤给出三种实现：按宗教动态开点线段树（主解）、离线离散化的普通线段树、单树每节点挂 map，附实测对比。

枚举医院节点做 BFS 求加权距离和 O(n²)；再用加权换根 DP 把答案压到 O(n)：挪一条边只让一侧居民少走一步、另一侧多走一步。

路径最大买卖差：一次线性扫描做部分分，树剖把路径拆成 O(log n) 段，线段树四元摘要维护正反序利润并支持区间加；满分档给出两套方向处理写法。

两种正解并列：双 dfs 序把祖先判定变成二维偏序、线段树二分 O(log n)；重链剖分后每条重链维护黑点集合 O(log^2 n)。

树链剖分 + 线段树，边权映射到较深端点的点权，路径最大边权转化为路径上非 LCA 节点的入边权最大值。

用树链剖分把树上路径拆成若干个 DFS 序区间，再在线段树中同时维护区间和与区间最大值。

用重链剖分把树上路径与子树映射为 DFS 序连续区间，再由懒标记线段树维护区间加与区间和。

区间 DP：f[i][j] 表示把 s[i..j] 补成回文的最少插入数，两端相同继承内层、不同则补一侧，O(n²) 求解；同一答案也等于 l − 最长回文子序列。

二分锯片高度，扫描树高判断当前高度能否得到至少 M 米木材，寻找最大可行高度。

每个商品耗时一天、有截止日期，求最大利润。两种做法并列：按截止日期排序后用小顶堆反悔，或按利润排序后用并查集抢占最晚可用日。

线段树维护区间最大值，查询时用「这段最大值都不大于 k 就整块剪掉」的判据单路下降定位第一个大于 k 的位置，把二分的 O(log^2 n) 降到 O(log n)。

懒标记线段树维护区间和, 再把前缀和达到 d 的判断改写成还差多少在树上二分, 单次操作 O(log n), 前提是元素非负.

倒序时光倒流将标记撤销转化为并查集向上合并，实现近线性 O((n+q)α(n)) 查询最近已标记祖先；同时提供在线重链剖分与线段树解法对比。

把「点到根路径和」倒过来算成每次修改对询问的贡献：单点加变成子树区间加常数，子树加拆成 a·dep[x] 与常数两项，DFS 序上两棵「区间加、单点查」树状数组即可。核心是点对子树的贡献，DFS 序差分数组的前缀和求出单点被贡献的值。

树上边差分：P 对 u、v、lca 三个点做差分配置，Q 用 DFS 序子树和回答单边覆盖次数。

答案 = 直径长 + max_u min(d(u,A), d(u,B)); 三臂分解得主干与支链折返，配合极简树上上界与无需证明直径的换根 DP 双解法.

两个正解: 倍增 LCA 求同色点直径端点并判共线; 或自底向上数同色点方向数, O(n) 直接定出两个端点与外侧连通块.

按「结尾位置 + 上一项位置」记等差子序列的个数, 每轮把中间项左侧的状态按高度分桶, 让右侧查询 O(1), 从而在不依赖值域的前提下做到 O(n^2)。

线性 DP + 方案还原: dp[i][j] 表示前 i 束花放入前 j 个花瓶的最大美学值, 按放或不放转移, 再反向还原出递增方案.

把「能不能赶到」化成曼哈顿距离不超过时间差, 于是事件序列成为 DAG, 用 dp[i] 表示以第 i 只结尾的最长链做 O(m^2) 转移.

把按「上一个数是谁」转移的 O(n^2) 子序列 DP 弱化成按二进制位建 30 个桶, 每次读自身 1 位的桶最大值再加一写回, 做到 O(n log A).

两条树上路径相交的三种判法：某条路径的 LCA 落在另一条上、距离和比较、树链剖分染色，都归约到常数次 LCA 查询。

在数字三角形的路径 DP 上多加一维「已用次数」, dp[i][j][c] 表示走到 (i,j) 恰好用了 c 次三倍的最大得分; k 可先截断成 min(k,n).

将赏花时间建模为容量、审美值建模为价值, 无限次数正序转移, 有限次数二进制拆分后倒序转移。

排序后枚举最后一根被选木棍，用前缀子集和 DP 统计能与它组成多边形的方案数。

反向图Dijkstra预处理最短路，将路径长度转化为相对最短路的额外偏差量，结合记忆化搜索与递归栈判0环。

用树形 DP 计算必须保留每个点时的最大连通块权值，负贡献子树直接剪掉。

将树定根为 1，将保留边转化为含根连通子树；每个儿子子树看作一组物品，以保留边数为容量做树上分组背包。

建立虚拟根将森林统一为树，使用树上分组背包求解有依赖选课的最大总学分。

通过将边权不超过 5 的有向图拆点为 5n 个状态，把按天动态规划转化为 (max, +) 矩阵乘法，并利用二进制预处理矩阵幂与向量乘法在 O((5n)^3 log T + k(5n)^2 log T) 内解决。

通过先序序列递归建树，利用树形 DP 分别维护每个节点在三种颜色下的最多与最少绿色节点数。

通过中序遍历区间与二叉树子树一一对应的性质，建立 O(n^3) 的区间 DP 模型求最大加分，并通过记录各区间最优根节点递归输出前序遍历。

先求以 1 为根时的子树牛数与总代价，再通过换根公式 dist[v]=dist[u]+(total-2*sub[v])*w 线性求出最优集会点。

将用户数作为背包容量维度，利用树形背包 DP 求解在净收益非负条件下的最大转播用户数。

值域很小而位置很大, 于是把区间 DP 的维度反转: dp[i][v] 存从 i 合成 v 的最短结束位置, 答案取最大的可达 v.

用全局时间队列清理过期优惠票，再按票价分桶寻找最早可用且票价足够的地铁券。

把「恰好 k 个点又要连通」翻译成每个点的第二长臂长：答案是第 k+1 大臂长加 1，用直径中点求向下高度或剥叶分层都能直接算出。

把一次涂色看成一段连续区间，用区间 DP 让左右端点相同的字符共用一笔涂色，转移枚举拆分点，时间 $O(n^3)$。

两次 DFS：先根化建父子关系，再后序求每棵子树大小，边费用 = 边权 × |2·子树大小 − n|。

把插入过程反过来看：已入队的人在理想队形中是连续区间 [l,r]，设 dp[l][r][0/1] 记录最后插入者在左端还是右端，按区间长度递增向两侧扩张计数。

把环按断边展开成链，用同时记录区间最大与最小值的双状态区间 DP 处理负数的乘法，最后枚举所有断边取最优并按编号升序输出。

从指数级枚举合并顺序的暴力出发，利用相邻合并对应连续区间的性质，设区间 dp[l][r] 枚举最后一次合并的断点，用前缀和加速得到 O(n³) 区间 DP。

把函数调用关系看成 DAG，逆拓扑序求每个函数的整体乘法倍数，再正拓扑序从后往前传播加法的最终系数。

将动态删点与可达性等价转换为中间点编号受限的双向最大瓶颈路径，利用倒序 Floyd 动态规划在 O(n^3 + m) 内求解所有子图答案。

树上最大权独立集模板题：通过树形 DP 记录当前节点选或不选两种状态，自底向上合并子树最优解。

对角线前缀和 O(1) 查段收益，交换 max 后每条对角线单调队列滑动窗口，O(nm) 决策优化 DP。

通过 Tarjan 缩点将软件循环依赖转化为不可分割的超点，再连虚拟根构成树形结构，进行树上有依赖的背包 DP 求解。

通过树形 DP 求解树的最小顶点覆盖，根据结点放与不放两种状态在子树间转移。

通过 Tarjan 缩点将强连通分量内的边转化为完全采摘的点权，跨分量的边化为单次通行的有向边，再在 DAG 上利用拓扑排序求最长路。

通过倍增预处理图上任意两点间是否存在长度为 2^k 的路径，转化为边权为 1 的最短路问题并用 Floyd 求解。