EC Final 2018

EC Final 2018 做题记录。

（本来应该在 WC 之前就发出来的。。。）

（参考吉老师 B 站讲课）。

D, L, I 略（两道签到 + 一道不是我写的。。。）

F 题搞出最优解在三点形成的平面上，然后就变成初中几何题了。而且不爆精。。。

然后我们去搞 C，把满足 $2^2, 3^2, 5^2, 7^2$ 的 $\mu$ 的周期规律的筛出来，然后 CRT + 判断（居然状态这么少！）（一开始写残了）。

（然后我们去吃饭了。。。）

J 题比赛的时候没搞懂这个长式子在干什么，然后说是纳什均衡，其实只要在后缀树上 DP，合并的时候根据定义推一下式子，然后是两个一次函数取 $\min$，然后就是取交点。

K 题均摊，按照 $k$ 从小到大，维护每个点为左端点时的最左右端点，然后把相同的合并，复杂度就是对的了。。。

G 题大分讨。我的构造选择 gap 总长更长的 $2m$ 个点。然后将所有区间按照和 $k$ 的大小关系分成两份，然后两边轮换放置（需要特判 size = 1），不够的地方用对面的补齐，然后多出来的全部放在一个位置上。

E 有趣的括号序列题。首先推出结论：两个序列任意位置前缀和之和大于 $-2$ ，且一个串前缀加一个整串的和要大于 $-1$（感性理解，发现它是对的）。然后 $O(n^3)$ 是个经典的栈 DP，$O(n^2)$ 只需要把它反过来，让原先所有的终止状态同时 DP（我写的还要容斥？）。

B 是 LCA 的营员交流。其实这个想法的出发点是若 $A, B, C$ 相连， $AB$ 连续，$BC$ 连续则 $ABC$ 连续，且 $A < B < C$ 或 $A > B > C$。所以如果一个区间是 sorted 的，那么其所有子区间都是连续的，然后我们可以把它缩成一个点，并附上新权值。而且，不考虑非平凡子区间，所有区间形成了树形结构。然后可以发现，如果每个非叶结点都有多于一个儿子的话，则它是合法的（可以考虑如何构造），且与一个连续区间集合一一对应。
但是，还有这个反例：2 4 1 3，它的每个非平凡子区间都不连续，但整个区间都连续。发现这一种情况，也满足树形结构关系，且孩子数量至少为 $4$。而且，父亲-儿子关系满足所有非平凡子区间要么都连续，要么都不连续。
有了这个我们可以 DP，也可以多项式 ($f$ 表示第一类点，$g$ 表示第二类点，$h$ 表示答案)：

$$h = f + g, f = x + h ^ 2 + h ^ 3 + \ldots, g = h ^ 4 + h ^ 5 + \ldots.$$

可以得到关于 $h$ 的表达式，多项式求解。

A 题有几步转化。首先观察权值范围较小，根据最小生成树的性质，我们如果知道对于 $x \in [1, 30]$，权值 $\le x$ 的边形成的生成森林的形态（具体地说，只需要知道有几条边在生成森林上），我们就可以求出答案。这时发现任意的生成森林这个值都是相同的，所以我们就可以不管权值限制。
然后我们就可以采取暴力求出前 $i$ 层生成森林边数：第一层直接求，然后每次合并，如果有这两个连通块各有一个在右边的点，我们记录这两个点（因为这个连通块在下一层中相当于一条边）。对于某一层，如果成环，这一层就必须额外删去一条边。最后求一下前缀和。$O(w^2 m)$。