Contest page
A
猜想段的长度只会有$1$和$2$（感性理解，应该可以反证……），然后就可以DP/贪心了
B
考虑如何构造合法方案。从右往左考虑球，因为当前球的位置相比于其他未考虑的球靠右，所以它要尽可能产生负贡献（成为三元组的$a$），否则尽可能产生$0$贡献（成为三元组的$b$）。
产生负贡献的条件是存在其他两种颜色的球构成的二元组，产生$0$贡献的条件是存在一种其他颜色未组成二元组的球。在产生$0$贡献时当前球可以选择一个未组成二元组的球形成二元组，此时对答案有"未形成二元组数量的球"的贡献；而产生负贡献时则对答案有“二元组数量”的贡献。
将所有贡献乘起来再乘上$N!$就是答案。
C
考虑最后一次操作，因为操作是将数字变为当前数字和相邻数字之和，而数都是正的，所以最后一次操作的结果一定会比相邻两个数要大。
所以考虑倒着做，每一次选择当前$B$序列中不满足$A_x = B_x$的最大值位置$x$，它一定满足比相邻两个位置的值之和大，否则无解。找到这个位置之后我们认为最后若干次操作在$x$上进行，然后进行若干次逆操作直到$A_x = B_x$或者$B_x < B_{x+1}+B_{x-1}$。这么做下去如果发现存在$A_x > B_x$则无解，否则统计逆操作次数即为答案。
D
题目等价于：设$b_{i,j} = \lfloor\frac{a_{i,j} - 1}{M} \rfloor$，需要重排行使得$b$的每一列是一个$0$到$N-1$的排列。
不难证明将某一列安排为$0$到$N-1$的排列之后删去这一列，剩余的$b_{i,j}$矩阵也有解。所以我们按列去做。不难发现这是一个行和数字的匹配问题，Dinic/匈牙利即可构造出一种方案。
最后我们按照$b_{i,j}$的顺序排列$a_{i,j}$就可以得到第一次输出的矩阵，然后按照$b_{i,j}$从小到大对列进行排序即可得到第二次输出的矩阵。
E
考虑初始的$S$中字典序最小的字符$x$。我们希望$x$在开头出现得尽可能多。
设初始的$S+rev(S)$中最长的$x$连续段长度$L$，则最后的串的前缀$x$长度一定可以构造为$\min\{N , 2^{K-1}L\}$，因为我们可以将$S+rev(S)$的$L$个连续的$x$放在$S‘$末尾，就可以每一次倍长$x$连续段长度，最后把这个连续段放在$S‘$的最前面即可。
对于$2^{K-1}L \geq N$的情况直接输出$N$个$x$，否则枚举所有可能的$S+rev(S)$的子串，可以$O(N)$得到进行上述做法之后得到的串。因为有$O(N)$个这样的子串，所以复杂度是$O(N^2)$的。
F在路上了
AGC037
原文：https://www.cnblogs.com/Itst/p/11372789.html
