Edu Round 一般都是套路题居多……不过这次题目质量还算不错。
- A
由于按照时间排序，所以 (p_i) 和 (c_i) 都应该是不降的，并且在一段区间内，显然应该有 (p_igeq c_i)。
- B
战 时 共 产 主 义
显然只考虑富人最优（危），按照财富顺序依次考虑前 (i) 个人是否满足 (sum_{j=1}^i a_jgeq icdot x) 即可。
- C
首先，若 (b_i>a_{imod n+1})，则必然会产生浪费，可以直接令 (b_i=min(b_i, a_{imod n+1}))。这样，发现我们只需要确定先打死 (x)，然后按照 ({x, x+1, ldots, n, 1, ldots, x-1}) 的顺序打，就可以只浪费 (b_{x-1})，其余的 (b_i) 全都恰好用完。显然选择 (b_{x-1}) 最小的作为 (x) 最优。
- D
手玩 (n=4) 或 (n=5) 的情况可以得到以下伪代码：
for (i : 1 -> n)
for (j : i+1 -> n)
print(i, j);
print(1);
现在我们要证明它是字典序最小的欧拉回路。
首先，对于每个 (i)，考虑枚举 (j) 的过程，发现除了 ((n, i)) 这条边之外，所有 (j>i)，((i, j), (j, i)) 的边都走到了。同时，由于在枚举 (j) 的过程中，最后一个走到的点一定是 (n)，因此当 (i) 由 (k) 变为 (k+1) 的时候，会走到 ((n, k+1)) 这条边。最后只剩 ((n, 1)) 的边没有走，补上即可。这里我们证明了它是一条欧拉回路。
然后我们注意到，在这个流程中，假设某一步的起点是 (i)，我们在这一步中都选了 ([1, n]) 中，((i, j)) 这条边还没有访问过的所有 (j) 的最小值，因此它的字典序一定是最小的——只有某几步例外。在 (i=k, j=n, 1leq k< n-1) 的时候，我们最终停留在了 (n) 点，随后在 (i=k+1, j=k+2) 的时候走到了 (k+1) 号点。实际上这里并没有走过 ((n, 1))，但是可以发现，(1) 点此时已经没有了任何出边，如果直接回到 (1) 点，则不足以构成欧拉回路。因此此时不得不放弃走 ((n, 1)) 的打算，选择了 ((n, k+1))——除了 ((n, 1)) 外最小的边。
实际输出比较麻烦，需要对边界仔细判断。
- E
首先将题意整理一下：
给出两个可以 (O(log D)) 分解质因数的数 (x, y)，每次可以将 (x) 乘上或者除以一个质数 (p) 变为 (x')，花费的代价为 (|d(x)-d(x')|)，其中 (d(x)) 表示 (x) 的约数个数。问 (x) 变成 (y) 的过程中，花费的权值最小的方案有多少种。两种方案不同当且仅当某一步乘的质数（或质数的倒数）不同。
将 (x, y) 分解成 (prod p_i^{e_i}) 的形式，对于每个 (p_i) 分别考虑。不难发现，最优的方案中，每个 (e_i) 增加或减少的次数是确定的，区别只在于顺序不同。
现在需要寻找一种最优的顺序：设 (e_{i, x}) 表示 (p_i) 在 (x) 中的幂，(e_{i, y}) 同理。如果存在 (e_{i, x}<e_{i, y}, e_{j, x}>e_{j, y})，考虑如何安排修改 (e_{i}) 和 (e_j) 的顺序。先考虑两个在操作序列中相邻的操作：(A=e_i ightarrow e_{i}+1,B= e_j ightarrow e_j-1)，假设先进行 (A)，操作的代价是 (wcdot (e_j+e_i+1))，其中 (w) 表示除了 (p_i, p_j) 外，剩余质数对应的 ((e_i+1)) 的积。否则先进行 (B)，操作的代价是 (wcdot (e_j+e_i-1))，显然先进行 (B) 更优。
换句话说，我们证明了，先进行所有的 (B) 操作，再进行 (A) 操作最优。
再考虑方案数，注意到在进行 (B) 操作时，(d(x)) 是单调减的，并且最终一定会到达 (dleft(gcd(x, y) ight))，随后开始单调增，最终到达 (d(y))。因此，(A,B) 操作各自的顺序并不会影响代价和，最终都是 (d(x)+d(y)-2dleft(gcd(x, y) ight))。任意安排 (A, B) 操作的顺序，方案数是一个多重集排列。
- F
不难看出 (f(S)) 是求 (S) 的前缀严格最大值集合。
为了避免复杂的边界讨论，不妨设 (a_0=b_0=0, a_{n+1}=b_{m+1}=n+1)。
首先考虑确定了 (f(a)=b) 中，(b) 的每个元素 (b_i) 在 (a) 中对应的下标 (c_i)，最小的 (sum p_i) 是多少。
显然对于 (k ot in c)，且 (p_k<0) 的位置 (k)，我们会直接将它删掉。
另外不难看出，对于每一个 (iin [0, m])，我们需要保证 (jin (c_i, c_{i+1}))，且 (a_j> a_{c_i}) 的每一个 (j) 都被删除。
因此，设 (f_{i, j}) 表示已经确定了 (c_1, ldots, c_i)，且 (c_i=j) 的最小代价和。注意到只有 (a_j=b_i) 的 (j) 才有用，因此状态总数是 (O(n)) 的。考虑 (f_{i, j}) 转移到 (f_{i+1, k}) 的方程：
和式的两部分都可以拆成前缀和相减的形式，可以与 (f_{i, j}) 放在一起维护前缀最小值，转移时双指针即可。
第一部分的前缀和可以直接预处理，第二部分的前缀和可以先将所有 (p_ugeq 0) 的 (p_u) 插入到树状数组里，由于 (b_i) 单调递增，每次只需要将新增的 (a_uleq b_i) 从树状数组里删除即可，总复杂度 (O(nlog n))，常数很小。
- G
经典套路题，不过考场上做完 F 没多少时间了就咕了。赛后补题的时候虽然有点神志不清（凌晨一点多），但是居然还差点 1A，不得不说自己的代码能力有了长足进步（大雾）。
先考虑一个更加通用的字符串匹配方法：假设我们要求出 (t) 串在 (s) 串中所有可能的出现位置，我们设 (t') 表示 (t) 左右翻转后的串，(f(x)=sum_{i=0}^{|t|-1} g(t'_i, s_{x-i}))，并且对于每一个 (xin[|t|-1, |s|-1])，我们认为 (t) 能够和 (s[x-|t|+1, x]) 匹配当且仅当 (f(x)=0)。发现对于这个求和的形式与多项式卷积非常像，如果我们能特殊处理 (g(0, s_y))，就可以直接将求和的上界改为 (x)，使它完全贴合多项式卷积。
现在要做的就是设计合理的 (g(t_x, s_y))，使得：
- 它能反映字符 (t_x, s_y) 是否能匹配，只有匹配时才返回 (0)；
- 任意 (g(x, y)geq 0)，这是为了防止某些位置正负不同从而抵消；
- 它可以拆成若干 (h(t_x)cdot r(s_y)) 的和，其中 (h, r) 均为可以快速求点值的多项式。
对于一个没有任何通配符的，最普通的字符串匹配问题，我们不妨设 (g(t_x, s_y)=(t_x-s_y)^2=t_x^2+s_y^2-2t_xs_y)。前两项可以直接求前缀和，第三项可以用 FFT 优化（由于 (sum g(t_x, s_y)) 的值不会很大，直接用 NTT 也是可以的）。注意要处理由于求和上界不同而多算的 (g(0, s_y))，发现它就等于 (s_y^2)，计算 (s_y^2) 的前缀和时修改一下边界即可。
在这个问题中，我们发现字符 (t_i) 可以匹配 (t_i) 或 (p_{t_i}) 两种字符，不难想到设 (g(t_i, s_i)=(t_i-s_i)^2cdot(p_{t_i}-s_i)^2)，拆开后可以对于每个 (k) 不同的 (s_i^kcdot operatorname {poly}(t_i)) 单独做一遍 FFT。