题目列表

二分最大允许造价 T。对每个 T，只看二级造价不超过 T 的边是否能连通全图，再看一级造价不超过 T 的边最多能提供多少条一级公路，从而判断可行性。

每周只新增一条边，因此当前最小生成树只可能通过“接上一条新边”或“用新边替换环上的更大边”发生变化；维护最小生成森林即可在线输出答案。

题面按轮修路的过程本质是在构造欧几里得最小生成树，最终总长度就等于 MST 边长之和；点数较大时直接用 Prim 求解即可。

这是带门槛的最小生成树：只有距离平方不小于 c 的边允许使用，直接在完全图上做 Prim，若中途出现不可达点则答案不存在。

题目给的是完整邻接矩阵，直接用 Prim 维护每个未选点到当前生成树的最小连边代价，逐个把点加入生成树即可。

并查集合并已有道路并实时维护连通块数，最少新道路数就是连通块数减一。

用并查集维护若干元素所属的集合，操作 1 合并两个集合，操作 2 判断两个元素是否已经连通。

分别求出 A 公司里与 1 号同组的人数、B 公司里与 -1 号同组的人数，答案就是这两个连通块大小的较小值。

把每个格子看成一个点，出现连根关系就并查集合并两个编号，最后连通块数量就是合根植物的总株数。

把限制反向建图，用大根堆在反图上做拓扑排序，再把得到的序列倒过来输出，就能得到题目要求的最优顺序。

在 DAG 上同时维护从起点到每个点的路径条数和所有路径长度总和，最后加上每次重新坐船返回的固定时间。

把先后约束建成 DAG，在拓扑序上做最长路 DP，`dp[i]` 表示完成第 i 头奶牛的最早结束时间。

分别用显式栈模拟前序、中序、后序遍历，其中后序用双栈避免深递归爆栈。

统计前序相邻且在后序中反向相邻的父子对个数，每出现一个这样的单孩子歧义点，答案就乘 2。

后序计算每棵子树的正常表示和镜像表示，若二者相等则该子树对称，再用子树大小更新最大答案。

把“有相同萌元素”转成“有公共质因子”，每次修改后整树 DFS，沿根路径按质因子维护最近祖先栈即可回答所有查询。

用有序集合维护已插入节点，只看当前值的前驱和后继，取插入更晚者为父亲，再迭代输出后序遍历和最大深度。

利用后序末尾字符确定根，再在中序里切出左右子树区间，递归按根左右顺序输出先序遍历。

递归处理每个二分区间，先输出左右子树结果，再用区间内 0/1 的分布判定当前结点类型。

利用前序首字符确定根，再在中序里切出左右子树区间，递归按左右根顺序输出后序遍历。

把问题转成从 1 到 a 是否存在长度恰好为 L 的游走，用奇偶分层图 BFS 求最短同奇偶步数。

把已访问顶点压成二进制集合，设 dp[mask][u] 表示走过 mask 且停在 u 时的最大路程。

每条边必须恰好有一个端点被选，因此图必须二分染色；每个连通块取两种颜色中较少的一侧。

固定路径中间的有向边，左右两端独立从两侧端点的其余邻居中选择，边贡献就是两个度数减一的乘积。

把每一层看成连续区间，设 dp[l][r] 表示上一层支撑区间为 [l,r] 的方案数，再用区间包含和转到下一层。

设 dp[l][r] 表示删光当前区间 [l, r] 的最大收益，枚举这一步从左端或右端删掉多长的一段。

设 dp[l][r] 表示卖掉区间外所有零食后，剩余区间 [l, r] 能取得的最大收益，按当前天数转移左右端点。

按时间排序后，用高度状态记录最晚存活时间，逐个垃圾做吃或堆的转移。

把相邻两天的价格差当作收益，按每天做一次完全背包，逐步更新手里的金币。

用完全背包求每个面值的最少邮票数，再扫描最长连续可达前缀。

用偏移数组做 01 背包，记录智商和对应的最大情商，再在非负状态里取最大总和。

用前缀和优化的多重背包计数 DP，统计每种花最多取 a_i 盆时的摆放方案数。

把每座城堡能保留的高度看成前缀和，取所有城堡共同可达的最大高度。

用二维 01 背包同时记录最多能泡到的 MM 数和对应的最少时间。

先用完全背包求出一年内的最优收益，再按年份滚动更新总资产。

把每种题目看成可重复物品，按耗时做一维完全背包，求不超过 T 的最大总分。

把每个素数看成可以重复使用的物品，按整数 n 做一维完全背包，统计凑出 n 的组合方案数。

把每种草药看成可以重复选的物品，按时间做一维完全背包，容量正序枚举维护最大价值。

把每个物品看成只能选一次的背包物品，按容量做一维 0/1 背包，维护不超过 M 时的最大价值。

把每捆草的体积同时看成重量和价值，用一维 0/1 背包求不超过容量 C 的最大总体积。

把每捆干草的重量同时看成重量和价值，用一维 0/1 背包求不超过 H 的最大总重量。

设 dp[i][v] 表示调完前 i 次后音量 v 是否可达，按加减两种转移，最后从大到小找最大可达音量。

把有限枚砝码逐个展开成 0/1 物品，按总重量做布尔可达性背包，最后统计所有可达的正整数重量。

先预处理每个正整数的真约数和，再把数字本身当重量、真约数和当价值，做一维 0/1 背包求最大总价值。

先把每件物品的收益算成价格乘重要度，再按预算做一维 0/1 背包，维护不超过预算时的最大满意度。

把每个物品的体积同时看成重量和收益，先用一维 0/1 背包求最大可装体积，再用 V 减去它得到最小剩余空间。

把每块木石看成只能用一次的物品，按体积做最小代价背包，并把超过目标体积的状态统一截断到 v。

把每个候选人看成价值为资料量的 0/1 物品，用探查风险和工资作为两维容量，做二维费用背包求最大资料量。

把每个愿望看成价值为 1 的物品，用金钱和时间作为两维容量，做二维费用 0/1 背包求最多能完成多少个愿望。

把分队问题转成恰好选 n/2 人、总分不超过总和一半的二维 01 背包，在可达状态里倒序找最大和。

把体积和质量分别作为两维容量，做二维 0/1 背包，状态表示在双重限制下能获得的最大卡路里。

设 dp[l][r][t] 表示区间内恰好用 t 个乘号的最大值，转移时枚举最后一次运算是加号还是乘号。

设 `dp[i][j]` 为前 j 天结束后走完前 i 段路的最小疲劳值，每天在“休息”和“前进一段”之间转移。

把问题看成最长摆动子序列，线性扫描相邻高度差值，只在第一次出现趋势或趋势符号变化时增加答案。

设 `dp[i][j]` 表示传了 i 次后球在 j 号同学手里的方案数，当前位置只会从左右相邻同学转移而来。

只维护数字 k 出现次数的奇偶性，按位递推偶数态和奇数态方案数，预处理后每次询问 O(1) 输出。

设 `dp[i]` 为必须以第 i 天结尾的最大连续利润，递推 `dp[i]=max(a[i],dp[i-1]+a[i])` 后取最大值。

把“是否刚跳过”当成 DP 状态，分别维护当前可跳和当前疲惫两种最小花费，按层线性转移。

把题目看成分层 DAG，设 `dp[i][j]` 为到达第 i 层第 j 个星球的最小花费，按层枚举前驱转移即可。

枚举分界点，统计前缀里需要改成 1 的 2 的数量和后缀里需要改成 2 的 1 的数量，取最小值。