251128 以前 x 天

CF1188C Array Beauty

给定原序列 \(a\)，统计 \(a\) 的所有长度为 \(k\) 的子序列的最近两个数的差的和。\(n\le 1000,~a_i\le 10^5\)

对 \(a\) 排序，然后拆贡献，转化为枚举 \(x\) 然后统计所有间距都 \(\ge x\) 的子序列数量。由于 \(x\le\frac{V}{k}\)，因此复杂度为 \(O(\frac{V}{k}nk)=O(nV)\)。

P7916 [CSP-S 2021] 交通规划

直接跑最大流显然过不了。若是普通的平面图我们可以把最小割转化为跑一次最短路。对于这个边界上有一些问题的图，先把边界上两类点构成的连续段搞出来，发现貌似给连续段的分界处跑若干遍最短路把所有不同类的连续段都分开就行。

然而每次我们不知道最短路的起点和终点。可以引入反悔，但是这样会有负权边，只能用 spfa 这也让我深刻的理解了 spfa 的运行效率。发现最优解中最短路不会交叉，因此进行区间 dp 即可。

CF1699E Three Days Grace

你可以把一个数拆成它的两个因数 \(i\) 和 \(x/i\)。初始给你一个集合，通过任意次操作最小化极差。

很久以前的题，写了题解就放这吧。想到双指针扫描线，对下界进行扫描线，考察最小的上界。扫描的过程形如不断放松限制，将一个数 \(i\) 变为合法。按顺序把 \(i\) 的倍数都更新一遍即可。

AT_agc016_f [AGC016F] Games on DAG

给你一个 DAG，在 \(1\) 号和 \(2\) 号节点处有两颗棋子，形成一个组合有向图游戏。计数使得先手必胜的边集的子集数量。

先手必败当且仅当 \(sg(1)=sg(2)\)。对 \(sg\) 函数的值分层进行 dp，钦定 \(1,2\) 分在同一层即可。具体的限制是同层之间不能有边，一层的所有点都必须向之前的每个层连一条边。后者可以将限制提前为：后面的所有节点都必须向本层至少连一条边。瞎写一个 \(O(n3^n)\) 的做法就行。

P1484 种树

考虑从大往小贪心，但这样显然是假的。考虑引入反悔，插入一棵树可能删除两侧的两棵树。发现如果一棵树被删除了，那么它两侧的两棵树一定是同时被选择，否则可以调整为初始情况不劣。因此插入一棵树后，在原地插入一棵价值为 \(a_{i-1}+a_{i+1}-a_i\) 的树，表示它被删除的情况。用链表和堆维护。

P8227 「Wdoi-5」建立与摧毁的结界

对于一个括号序列，你可以把其中的 (((..()..))) 子串变为等长的 ()()...()() 子串，或者反向变换。给定两个串，问将其中一个变为另一个的最小步数。

注意到对于两个串不匹配的地方一定是全变成 ()()()...()()。记录 \(mat[i]\) 表示对应的右括号匹配了哪个左括号，然后记录 \(f[i]\) 表示将 \([mat[i],i]\) 变成 ()()()...()() 形式的最小步数。转移需要再记一个 \(g[i]\) 表示变成 (((..()..))) 的最小步数。

P3343 [ZJOI2015] 地震后的幻想乡

给定一个图，边权是 \([0,1]\) 之间的独立均匀随机实数。问最小生成树边权最大值的期望。

先求出 \(k\) 条边恰好将图连通的概率，然后乘以 \(\frac{k}{m+1}\) 即可。

P7962 [NOIP2021] 方差

注意到操作等价于任意重排差分数组。猜测最终形态形如前面一段上凸后面一段下凸，显然是对的。

我们关心 \(\sum a_i\) 以及 \(\sum a_i^2\)，后者值域较大，因此将前者计入状态。前者的值域是 \(n\times \max a_i\)。注意到非零的差分值只有 \(\min(n,\max a_i)\) 个，每次转移考虑将当前差分值扔到序列开头还是结尾，因此时间复杂度 \(O(\min(n,\max a_i)\times n\times \max a_i)\)。