A. Add One 2
一个比较关键的想法是去考虑操作后什么样的数列是能够得到的，然后通过这个性质尝试得出比 \(\{y_n\}\) 大的最小合法数列，这个数列的和就是答案。
将数列差分，你会发现如果要使 \(x_i - x_{i+1} =d\)（这里不妨假设 \(d>0\)，我们等会可以再倒过来考虑 \(d<0\) 的位置）,那么我们至少要对 \(i\) 这个前缀操作 \(d\) 次，你先把这若干次减掉，不难发现此时其他位置的差分不受影响。
继续这样做直到所有数都相等，此时如果 \(x\) 非负则能够得到，否则你无法从 \(0\) 得到这样一组差分数列。
换句话说，考虑被减最多次的两个数 \(x_1\) 和 \(x_n\)，我们要求：
\[x_1 \ge \sum_{i=1}^{n-1} \max(0,x_i-x_{i+1}) \]\[x_n \ge \sum_{i=1}^{n-1} \max(0,x_{i+1}-x_i) \]不妨在前后加入一个极大值 \(M\) 分离 \(x_1\) 和 \(x_n\) 的限制，这样我们就能得到一个非常简洁的限制：
\[2M \ge \sum_{i=0}^n |x_i-x_{i+1}| \]这样我们的任务就变成了增加 \(\{y_n\}\) 并将其变成一个合法序列，不难发现每次最优的操作一定是将一个最短的下凹段抬升，这样可以将差分减小 2，可以用堆维护。复杂度线性对数。
B. Periodic Sequence
先找一个答案的上界，题解给出的方法是通过每个 \(S_i\) 都能被 \(S_1\) 的一个极长前缀和若干前缀表示，且 \(S_1\) 的某一前缀组合不能用其他组合来表示。
题解还给了求到这个上界的构造，这样确实是最大的，但是我并不太清楚怎么能想到这步/yun。
到这步之后尝试计算，不难得到数列的生成函数：
\[\sum_{k=1}^{\infty} \frac{x^k}{1-2x+x^{k+1}} \]直接做是平方的，但注意到 \(k\) 变大后有用的项不会太多，考虑对这个柿子根号分治：
-
对于 \(k \le \sqrt n\)，直接把 \(\frac1{1-2x+x^{k+1}}\) 看成 \(\frac1{1-(2x-x^{k+1})}\)，然后这个就变成了背包，每次可以从 \(i-k-1\) 以 -1 的系数转移，或者从 \(i-1\) 处以 2 的系数转移。
-
对于 \(k > \sqrt n\)，把分母拆开成 \((1-2x)(1+\frac{x^k+1}{1-2x})\) 然后看作 \(\frac1{1-(-\frac{x^k+1}{1-2x})}\) 和 \(\frac1{1-2x}\)，把前者再暴力展开，你会发现这里有用的就只有根号项了，可以类似秦九韶算法一样每次对所有 \(k\) 算指数相同的项的贡献，后者直接乘进前面一起算就行。
有两只 log 的 bouns，但是不会。也有不用 GF 直接 dp 并分析非 0 项的做法，和 GF 应该是本质相同的。
C. Colorful Graph 2
官方题解给出了一个非常巧妙的做法，直接对 bfs 后深度相同的节点染一个颜色，隔层不同，如果无解必定是同层的环，但是在这个图下同层不可能有环。
D. Min or Max
模拟。
标签：Chengdu,Cup,题解,Universal,2x,ge,frac1,sum,数列 From： https://www.cnblogs.com/eastcloud/p/18450282