题目列表

把“同一局域网”正确理解为互相可达即强连通，用迭代 Tarjan 缩点，把分量内部边权变 0，再跑堆优化 Dijkstra 求最短路。

贡献视角改写询问：DFS 序把子树变连续区间，单点加与子树加都化为区间加，子树加按 depth 拆成一次项与常数项两棵树状数组，点查即得根到 x 的路径和。

树链剖分把根到 x 的路径拆成 O(log n) 段连续区间，配合带懒标记的线段树做区间赋值与求和，用段长减和得到安装数、子树区间和得到卸载数。

聚会点是三对 LCA 中最深的那个，费用等于三点深度和减三对 LCA 深度和；重链跳跃把每次询问压到 O(log N)。

把异象石按 DFS 序排成环，环上周长等于斯坦纳树的两倍；用有序表维护环，插入删除只改 O(1) 条相邻距离。

树上差分统计每条主要边被几条附加边跨越，按 0/1/≥2 三类累加 M/1/0，倍增求 LCA。

在线 ST 表按“以位置结尾”分层预存 2^k 段最大值：追加时增量补层 O(log m)，询问用两段幂等覆盖 O(1) 取出后缀最大值。

对最大、最小各建一张 ST 表，询问用两段可重叠的 2 幂区间 O(1) 取出极值，极差即两表相减。

区间翻转 + 单点查询，用异或差分把区间翻转降成两次单点翻转，再用异或树状数组在线维护前缀异或，O((n+m) log n)。

把单词看成首字母到末字母的有向边，欧拉路径判定：非零度点弱连通，且入出度差只出现 0 与至多一对 ±1。

Tarjan 求割点与点双后按分量内割点数三分类计数：叶子点双放 1 个出口、无割点连通块任选 2 点，各块方案相乘。

Tarjan 缩点把环内收益合并为分量点权和，再在缩点 DAG 上按分量编号降序做最长路 DP，线性时间求出起点到任意酒吧的最大收益。

无权图最短路计数：BFS 按层求距离的同时递推 cnt[v]，首次到达赋 cnt[u]、同层前驱累加 cnt[u]，边算边对 100003 取模，O(N+M)。

把状态扩成 (格子, 钥匙位掩码)，在无权状态图上 BFS 求从 (1,1) 到 (n,m) 的最短路。

以环上编号最大的点拆环，用 Floyd 并入该点前的受限最短路闭合成环，再沿后继表回溯输出方案。

非树点对只能补“路径最大边权+1”的边；按边权升序并查集合并，用块大小乘积批量累计所有点对的路径最大边权，O(n log n) 求最小完全图边权和。

把病毒串建成 AC 自动机并标记危险节点，在安全节点的转移子图上拓扑判环：有环输出 TAK，无环输出 NIE。

状压 DP 用位掩码记录已用串集合并以结尾串为附加状态，转移按最大后缀-前缀重合补尾拼接，终点按长度与字典序取最小。

树上前缀异或把任意路径异或化成两端点 d 值异或，问题坍缩为序列最大异或对，再用 01 字典树 O(31n) 贪心求解。

查询词全部插入 Trie 建 AC 自动机，扫描文章只标记到达状态，再沿 fail 树自底向上合并命中，一次 O(|S|) 扫描统计出现过的查询词个数。

把全部信息插入 01-Trie，节点记录经过数与终止数；查询密码时沿路径累加终止数，走通再补上经过数减终止数，把两两前缀比较降为一次树上行走。

两段不相交子数组异或和之和：用分割点拆成前后缀各自的最大子数组异或，01-Trie 贪心求与历史前缀的最大异或后合并。

把每个数按 30→0 位序插入 01 字典树，查询时每位优先走与 x 相反的边，O(31N) 求出最大异或对。

屏蔽词建 AC 自动机，逐字符扫描并用栈平行保存字符与每个前缀的自动机状态；命中词尾就按词长整段弹出并恢复状态，均摊 O(|S| + 26·∑|t|)。

把反对称子串改写成缝隙两侧逐位互不相等，套用 Manacher 的镜像继承与右端截断，把逐缝隙暴力扩展均摊成 O(n)，按半径求和计数。

把“愿意拷贝”建成有向图，一张光盘覆盖放置者可达的所有人；bitset 传递闭包求 SCC，能到 i 的点都能被 i 反达即源分量，答案就是源分量个数。

把「所选糖果总数模 K 的余数」作为背包状态，每个余数只保留最大总和：dp[j] = max(dp[j], old[(j - a%K)%K] + a)，答案取 dp[0]。

把一次单向滑翔拆成两个方向的最长下降子序列：高度取负后就是标准 LIS，用 tails 数组按长度维护最小结尾、二分定位，每个方向 O(N log N)，两方向取较大值即为答案。

把「最长复制时间最小」转成判定问题：二分上限 L，用贪心数出 L 下最少的段数；再倒序贪心让后面的人尽量多抄，重建出前面人少抄的字典序最小方案。

外层枚举组、容量倒序、内层枚举组内物品，容量倒序保证每轮只读上一组的旧值，同组物品不会叠加。

分组背包 DP：f(i,j)=max_k f(i-1,j-k)+a[i][k] 求前 i 家恰好分 j 台的最大盈利，并用 res 记录决策 O(N) 回溯输出分配方案。

数塔 DP：自底向上递推 f(i,j)=a[i][j]+max(f(i+1,j),f(i+1,j+1))，滚动一维数组即可。

第一问最长不升子序列，第二问由 Dilworth 定理等于最长严格上升子序列；两问共用一个二分 LIS 函数，O(n log n)。

把坐标看成顶点、三种操作看成边权为 1 的边，BFS 逐层扩展，首次到达 K 的层号即最少分钟数；起点大于等于终点时答案直接是 N-K。

固定 5×5 迷宫 BFS 求唯一最短路，入队时记录前驱并兼作访问标记，到终点后回溯再反转输出路径。

棋盘上马的最少步数就是隐式无权图的单源最短路：边权全为 1，按步数分层 BFS，首次到达终点即答案。

网格 BFS：从左上角 BFS 到右下角，按层扩展，首次到达时的层号就是最少经过的格子数（含起点终点）。

把方块看成顶点、相邻且公共边无墙时连边，问题化为无向图连通分量个数与最大分量大小，一次洪水填充即可 O(mn) 求出。

三维网格建成无权图，可通行格是顶点、六方向相邻连边，BFS 入队即标记，命中 E 的层号就是最短分钟数。

弧长与弦长固定时圆心角唯一，二分求角后代弓形高公式输出偏移。

对答案二分：可行性随要求跳跃距离单调变差，判定用左端贪心扫一遍，越过 L−mid 的岩石必删以保住最后一跳，O(n log L) 求最长的最短跳跃。

取 n 的末四位作为指数，用快速幂求 2011^n mod 10^4。

枚举行区间把二维压成一维：先用列前缀和得到每列在该行区间内的和，再对这一维数组跑 Kadane 求最大子段和，O(N³)。

把分组抽象成冲突图染色：不互质就连边，一组是一个独立集，用 2^n 子集 DP 求最小染色数。

预处理每对单词的最小合法重叠增益，再按增益降序做带上界剪枝的 DFS 回溯，每词最多用两次，搜出最长接龙。

设 f(n,lo) 为把 n 拆成不小于 lo 的因子之积的方案数，按首因子 d 分类递推 f(n,lo)=1+Σf(n/d,d)（d≤√n 且 d|n），记忆化即可

链上选 n 个村建小学：前缀和定位后，“去最近学校”等价于把链切成 n 个连续段，每段代价是到中位村的距离和，O(m^3) 区间划分类 DP 直接转移。

按天同步传播就是网格上的多源 BFS：一天对应一层，每轮按当前队列长度成批出队，入队时就地标记患病格。

按 (成绩降序, 报名号升序) 排序，第 floor(m*150/100) 名的成绩即分数线，所有不低于该分数的选手构成排序前缀，一并输出。

滚动维护阶乘并高精度累加 1! 到 n! 的和。

枚举 a 用真因数和 σ(n) 判定亲和数，σ(σ(a))=a 且 σ(a)≠a 即命中。

把小岛转成 x 轴上的覆盖区间，按右端点排序，遇到未被覆盖的区间就把雷达放在它的右端点。

1. 前缀比较具有二分性 (左对右错) 2. 字符串哈希具有结合律 3. fhq-treap 中序就是字符串原来的序列 4. 利用fhq-treap 的logn 分裂合并的性质维护 动态插入与删除 与 结合律

把每个位置需要的翻转次数写成除数前缀异或，按下标递增唯一决定每个操作是否选择。

枚举最大值后，把其余 k-1 个数转成最大异或值，用二进制 Trie 在线查询前 k-1 个异或和。

正难则反：指定坏点后序列碎成段内同值的独立段，容斥计数，再用单调栈维护后缀最小值阶梯把转移压成 O(1)。

从每个格子沿 8 个方向 DFS 游走匹配单词，用标记记录是否已转过一次 90° 弯。

单窗口内按 b 降序排队可证最优，全体排序后退化为 0/1 分配问题，用背包式 DP 求最小完成时间。

经典 LIS 贪心表的变体：同一位置的候选值先统一评估再统一写回，避免同一位置的候选值互相接龙。

按 mex 值贡献:分类，把条件转化为区间必须包含所有小于 x 的位置且避开所有 x 的位置。