被打爆了 /fn。
CF1550A
不难想到有最优情况下前几个数都有 \(a_i=2\times i-1\)，暴力即可。
CF1550B
因为要把全部的都删完，那么答案就是 \(a\times n+b\times cnt\)，其中 \(cnt\) 表示删除的次数。
-
\(b\ge0\)，那么删除的次数越多越好，每次删一个即可，答案就是 \(a\times n + b \times n\)。
-
\(b<0\)，那么需要删除的次数尽量少，设该字符串有 \(x\) 段，那么每次删除最多可让段数 \(-2\)（删掉一段，然后两段相同的可以合并成一段），当 \(x\le2\) 的时候每次只能让段数 \(-1\)。不难发现最少的次数就是 \([\frac n 2 ]+1\)。
CF1550C
被诈骗题打爆了。
不难发现一个序列 \(a\) 是 good 的当且仅当不存在三个数 \(i,j,k\) 满足 \(a_i \le a_j \le a_k\) 或者 \(a_i \ge a_j \ge a_k\)。
不难发现不存在长度 \(\ge 5\) 的 good 的序列，暴力即可。
CF1550D
这个题实在太吐了，我读完题一秒就会了，然后调了一年才过，然后就爆炸了。
首先考虑这个最大值是多少，不难发现，一种可行的并且唯一的构造方法是选出两个集合 \(S1,S2\)，\(a_i=\)
然后就相当于要数有多少种这样的情况 /tuu。
咕咕咕咕。
CF1550E
感觉这个题是个傻逼题，但是不知道为啥场上过的人这么少，我因为 D 调了太久也没时间想 /kk，第二天补题的时候就直接秒了。。
不难想到二分，考虑如何判断，注意到 \(k\) 很小，考虑状压。
当判断 \(x\) 是否满足条件的时候，设 \(dp_S\) 表示最小的数使得 \(s_{1 \dots dp_{S}}\) 可以让集合 \(S\) 中的所有字符出现 \(x\) 次（如果不能则是 \(\infty\)），那么若 \(dp_{All} \ne \infty\) 则说明可行。
考虑转移，枚举当前情况最后字符 \(i\)，令 \(f_{i,j}\) 表示从 \(s_i\) 开始要到 \(s_{f_{i,j}}\) 才能够凑出 \(x\) 个 \(j\)，那么 \(dp_S=\min(f_{dp_{S-2^{i-1}}+1})\)。
考虑如何求出 \(f_{i,j}\)。另 \(g_{i,j}\) 表示从 \(s_i\) 开始最多有连续字符 \(j\) 的数量，若 \(g_{i,j}\ge x\)，则 \(f_{i,j}=i+x-1\)，否则 \(f_{i,j}=f_{i+1,j}\)，然后就做好了。
CF1550F
考虑对于每个结点 \(i\) 算出最小的满足条件的 \(k\)，记为 \(d_i\)。
对于两个结点 \(u,v\)，如果 \(u\) 可以直接到 \(v\)，那么 \(k=|d-|a_u-a_v||\)。对于所有的 \((u,v)\) 连一条 \(|d-|a_u-a_v||\) 的边，那么 \(s \to i\) 的最小满足条件的 \(k\) 就是最小的 \(k\) 满足存在 \(s \to i\) 的路径且每条边的边权不大于 \(k\)。
根据最小生成树的性质，实际上建出最小生成树后，\(d_i\) 就是 \(s \to i\) 的路径中最大的权值，这意味着我们需要找到这个最小生成树。
边数为 \(n^2\) 级别的，直接使用 kruskal 和 prim 显然会超时，可以使用另外一种最小生成树算法：boruvka 。
这个东西就是维护每个联通块，然后对于每次迭代，对于每个联通块找到他连出去的最小的边，然后全部找完之后合并。因为每次联通块的次数会至少减半，所以迭代的次数是 \(\log n\) 级别的。
虽然边数仍然是 \(n^2\) 级别，但是对于联通块的每一个点 \(u\)，只要快速找到联通块以外最小的边，即 \(|d-|a_u-a_v|||\) 最小。
- \(a_u < a_v\)，即 \(|d+a_u-a_v|\) 最小，即 \(a_v\) 最接近于 \(a_u+d\)。
- \(a_u \ge a_v\)，即 \(|d-a_u+a_v|=|a_u-d-a_v|\) 最小，即 \(a_v\) 最接近于 \(a_u-d\)。
那么利用一个 set 维护所有的点，对于每个联通块，先删去这个联通块中的所有点，然后再遍历所有点，用 lower_bound 快速找到最接近于上面两个数的点，然后在遍历完成后连上最小的边就可以，然后就可以在 \(\mathcal{O}(n \log^2 n)\) 的时间复杂度内找到最小生成树。
然后再按照上面所说的在这个树上 dfs 一次即可。