题目列表

先用 Tarjan 找出无向图中的所有桥，再把这些桥删掉，剩下的每个连通块就是一个边双连通分量。

先用 BFS 求出任意两座城市之间的最短骑士步数，再把“从已占领城市攻占一座新城市”的代价视作边权，整道题就转化成一棵最小生成树。

要求把 N 个点连成恰好 K 个连通块且总代价最小，本质就是最小生成森林；按边权从小到大做 Kruskal，连到只剩 K 个连通块时停止。

要求先用最少的边把全图连通，因此一定选 n-1 条边；再把这些边中的最大权值压到最小，直接按边权从小到大做 Kruskal，最后一条加入的边权就是答案。

把两棵树之间能否跳过去看成边，所有树都能互达所需的最小跳距，等于一棵最小生成树中的最大边长；用 Prim 求出这个临界值后统计能达到的猴子数量。

在保留成树的前提下，一条边必走两次，而点 i 的谈话时间会按它在树中的度数计入；把每条边改写成 2*l+c_u+c_v，再额外加上最小的起点费用即可。

因为边权是严格递增的 2^i，最优环一定在按边编号从小到大加边时第一次形成；先用并查集找到这条边，再在此前形成的森林里找两端唯一简单路径。

把每次有效连边变成并查集合并树上的一个新父节点，测试操作只给当前连通块根打标记，最后 DFS 一次把信息总量下传到所有原节点。

把每一列看成一个并查集集合，维护每艘战舰到队头的距离；合并时整体挂到另一列后面，就能在线回答两舰之间隔了多少艘船。

把每个数出现后占掉这个位置，并查集维护“从某个值开始往后第一个没被占用的位置”，从而快速找到修改后的最小可行值。

把关闭谷仓的过程倒过来看成重新开门，按倒序激活点并用并查集维护当前开着的连通块数量。

先判定有向欧拉路存在条件，再把每个点的出边按升序走 Hierholzer，最后逆序得到字典序最小的欧拉路径。

在 DAG 上按拓扑序传播精确分数流量，每个点把当前污水均分给所有出边，最后统计所有汇点的分数结果。

按拓扑序模拟神经元信号传播，只有 `C[i] > 0` 的点才向后继传值，非输入层先扣掉自己的阈值。

把记忆约束建成带权 DAG，在拓扑序上做最长路转移，`dp[i]` 表示第 i 次挤奶能安排的最早日期。

把“某摄像头所在位置被别的摄像头监视”建成有向边，反复删除入度为 0 的点，最后剩下的摄像头数就是答案。

把每条推荐规则看成依赖一组前提题的规则节点，维护未满足前提数和前提最大完成天数，单调传播每道题的最早完成日。

把每种宝物的件数做二进制拆分，转成若干件 0/1 物品后，再做一维 0/1 背包。

先用调度场算法把中缀表达式转成后缀，再由后缀建出语法树，最后在树上按短路语义 dfs 求值，只统计真正访问到的子树里的短路次数。

把状态设成 (点, 当前时刻 mod k)，在状态图上跑 Dijkstra，转移时把时间补到不早于开放时刻且同余不变的最早值。

先用 Tarjan 建圆方树，再统计 x 到 y 在圆方树路径上经过了多少个原图割点。

给释放名单两端补哨兵，设 dp[l][r] 表示释放两边界之间所有目标囚犯的最小代价，枚举第一个释放点。

设 dp[l][r] 表示区间 [l, r] 整体能合成出的最大值，枚举最后一次合并的断点，把两个相等子区间向上合并。

把每个城堡的对手兵力排序并合并相同值，转成若干个阈值台阶，再做分组背包求最大得分。

把每个英雄的皮肤选择看成分组背包，按总花费做 DP，记录最多能得到多少种展示方式。

先按允许高度排序，再用多重 01 背包判断哪些电梯高度可达。

把每个分组大小看成完全背包物品，预处理一趟运送的总时间后做最小值 DP。

按余数做 0/1 计数 DP，统计总能力对 F 取模为 0 的非空子集数。

把每个四次方数看成可以重复使用的物品，按数字 m 做一维完全背包，维护凑出 j 的最少项数。

先把每道题的耗时按水平倍率换算出来，再把奖励当价值、耗时当容量做一维 0/1 背包。

先用 0/1 背包求达到及格线所需的最少作业时间，再把剩余时间留给耗时最短的喜欢题。

把每种菜看成只能选一次的物品，倒序做计数 0/1 背包，统计恰好花完 M 元的方案数。

先按长度降序、同长度按宽度降序排序，再在宽度序列上求最长严格上升子序列长度，它等于最少需要开的加工链数。

设 `dp[i][j]` 为两条序列前缀的最大相似度，最后一列只会来自字符对字符、字符对空位、空位对字符三种转移。

按高度排序后，设 `dp[i][j]` 为保留 i 本且最后一本是第 j 本时的最小不整齐度，枚举上一本转移。

设 `dp[i]` 表示前 i 头牛最多能分成多少组，枚举最后一组起点并用前缀和判断区间和是否非负。

把每个单词内部字母排序成标准形，用集合统计不同标准形的个数，就是不同类别数。

把数字单词映射成数字后平方模 100，格式化为两位块排序拼接并去掉整体前导零。

在文章两端补空格后查找带空格的目标单词，从而实现不区分大小写的整词匹配。

把相同高度且 8 连通的格子缩成一个平台，flood fill 这一整块时只要发现周围有更高格子，它就不是山顶。

把每一行选哪些格子压成状态，只保留行内不相邻的状态，再做相邻两行之间的兼容性 DP。

先预处理每个格子的最早摧毁时间，再在“到达时间必须严格早于摧毁时间”的约束下做 BFS，第一个到达的永不摧毁格即答案。

把所有感染源同时作为 BFS 起点，一次多源 BFS 预处理整张图，再直接回答每个领主的感染时间。

给每个格子记录最早落障时间，从起点 BFS，并只在到达时间仍早于落障时间时进入该格子。

把棋盘看成无权图，从起点做一次 BFS 按层扩展，就能同时求出马到所有格子的最短步数。

利用插入排序的稳定性维护按 (值, 原下标) 排序的普通数组，通过二分查找回答排名。

把答案拆成完整年份、完整月份和当月已过天数，再对 1582 年换历与缺失 10 天分段处理。

先用差分统计有多少行和多少列被覆盖，再用容斥计算最终被打扫的方格数。

先把所有数字排序，让相同数字连续出现，再线性扫描统计每个数字的出现次数。

连续乘法时做上界截断；一旦超过 10^9 就输出 -1，a >= 2 时最多乘约 30 次。

设 P=x0*a、Q=x0*b 后可化成 a*b=y0/x0 且 gcd(a,b)=1，答案就是 y0/x0 的不同质因子个数对应的 2^k。

利用偶数位回文除 11 外都不是质数的性质，只构造少量奇数位回文再试除判素。

逐行提取字符串中的数字形成整数，超过 4e7 直接报大，否则做素数判断并按升序输出质因数分解。

把较大根统一成 -b/(2a)+sqrt(Delta)/(2|a|)，再用质因数分解或倒序枚举两种方式提净判别式里的平方因子并格式化输出。

把人数当作权重后，最优聚会地点就是距离轴上的带权中位数。

从 s 开始枚举，用试除法求真约数和，找到第一对互为真约数和的友好数。

二分最低睡前幸福值，用每天吃到刚达标就停止的贪心检查可行性并构造吃巧克力日期。

排序学校分数线后，对每个学生二分找到左右相邻候选，累加最近分数线差值。

把多次区间加分转成差分数组的两个端点修改，最后前缀还原并维护最低成绩。

用二维差分把每个半开矩形覆盖变成四个边界修改，再用二维前缀和还原并统计恰好 K 层的格子。