题目列表

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

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

按测试点分档推进：枚举组合 → 固定 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(n+q)；也可用倍增跳表沿重链向下跳，每次查询 O(log n)，后者可迁移到删边类问题。

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

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

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

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

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

X_i < Y_i 让编号本身就是拓扑序：按编号扫一遍、只维护「能走到 v 的最低买入价」即可 O(N+M) 求出最大差价，含暴力枚举、记忆化 DFS 对照与答案为负的边界处理。

区间存最低价、最高价与区间内最优交易，合并时取左段最优、右段最优、右段最高减左段最低三者最大；线段树与倍增两种实现，单次询问 O(log n)。

把矩形拆成 x=l 加、x=r 减两个事件，按 x 扫描；y 方向用差分 + 树状数组，同 x 先处理事件再回答询问，正好实现半开区间。

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

对每个卖出时刻只需知道它左边出现过的最低价，扫一遍滚动维护前缀最小值，把 O(n²) 的两两枚举压成 O(n)。

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

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

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

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

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

加虚拟源点把「建电站」变成一条边，答案成为 n+1 个点的最小生成树；稠密完全图上选 O(n²) 的 Prim 现场扫描，不落地保存两百万条边。

把子树加值改写成差分数组上的两次点修改，购买集合可行等价于对应边让 0..m 连通，于是第一问变成最小生成树；第二问用按权值分组的 Kruskal 判定每条边是否属于某棵 MST。

外层线段树按 x 组存区间最大 y，靠「整段最大值不够就剪掉」单路下降定位最左可行 x；组内可用 std::set 或离线压缩后的 Fenwick 维护。

折半枚举每个数的不选、原值、阶乘三种状态，按使用贴纸数统计目标和方案。

把质数拆成两组生成所有乘积，二分答案并双指针统计不超过它的乘积对数。

枚举三个字符串的拼接顺序，用 KMP 求相邻字符串的最大后缀前缀重叠。

最后一步必含首或尾；Alice 胜当且仅当 a1=1 或 an=1。

维护非负序列 A 的区间和，用线段树上带余量下降（或前缀和的区间加配极值剪枝）在 O(log N) 内定位和第一次达到 t 的位置

二分锯片高度，扫描树高判断当前高度能否得到至少 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 分别维护每个节点在三种颜色下的最多与最少绿色节点数。