ARC130
周末把周日晚的东西都提前补了才过来打。
A： 给出一个字符串，求有多少个位置对，使得分别删去两个位置的两个字符串相同。
连续一串相同字母内的任意两个都合法。
B： 一个 \(W \times H\) 的矩阵，每次操作将某一行或一列染色，求最终状态下每个颜色有多少个格子。
从后往前直接做。
C： 给出两个数 \(a\) , \(b\) ，让你将其重排列，最小化 \(a+b\) 每一位的和。
考虑两数相加进位是有 \(-9\) 的贡献的，如果两数之和为 \(9\) ，但是后面有 \(1\) 进位，也可以有贡献。
那么暴力枚举两个最小位，这里钦定其能进位，由于进位至多为 \(1\) ，所以可以贪心地将能进位的全部靠在最小位，此时能进位的是 \(9\)~\(18\) 。
将这些放完后会有两种情况，一种是两个数都还有剩，这时只能全部求和了。
另一种是一种用完了，那另一个数就能优先把 \(9\) 放完，此时可以去掉所有 \(9\) 的贡献。
这样写 WA 了两发，还一直以为是细节没写对。
后来意识到最后的两种情况可以做点文章。
两个数都还有剩的可以并到第二种，做法是将枚举的最小位往后移，把影响答案的不可能进位数塞到前面。
D： 给出一棵树，要求计算这样的排列数：对于树上的节点，每个和它相邻的节点的对应值要么都小于它，要么都大于它。
一定要注意到是排列不然会打空。（同时说明了手玩数据的必要性）
我们设 \(f_{i,j,0/1}\) 为在 \(i\) 号节点，其子树中有 \(j\) 个 小于 它，它的所有儿子都 小于/大于 它，的方案数。
转移的时候要带上排列数的系数。
E：
题意：有数组长度为 \(n\) 的数组 \(\left\{a_i\right\}\) ，有 \(m\) 次操作，每次操作将 \(a_x+1\) ,保证操作前 \(a_x=\min \left\{a_i\right\}\) ，给出每次的 \(x\) ，求数组初始状态，要求字典序最小。
注意到
1 2 2 1
这样也是可能合法的，操作次序的相对顺序并不一定。
但是容易发现不可能有这样的情况出现：
1 2 2 2 1
于是我们对序列分组，每个组内不能有相同的数，并且后面的组需要包含前面组内的元素。
通过维护每个位置是否可以作为组末即可轻易做到这一点。
最后的一组是特殊的，它不必包含前面组内的元素，因为这组做完后是可以有数组不完全相同的情况出现的。
那么我们分成最后一组是否包含 次数MAX 的数来做，这里推推就好了。
主要是细节要注意。。。99个测试点太难搞了。
ARC059 virtual
可能是打得最好的一次ARC（
切了前三题。
C： 给出一个长度为 \(n\) 的序列，要将序列中所有数改成相同，将 \(x\) 改做 \(y\) 需要代价 \((x-y)^2\) ，问最小代价。
由于 \(n \le 100\) , \(\vert a_i \vert \le 100\) ，暴力碾。
D： 给出一个字符串，求其中一个子串使得长度大于 1 且有超过一半的字符相同。
如果存在一个这样的子串，若是偶数长度，则必有一对相邻字符相同，这对字符就是一个合法串；
若是奇数长度，则必有 \(a_i = a_{i+2}\) 存在，此时这个长度为 3 的串也是合法的。
E： 题意不赘述。
就是最简单的 DP 把所有情况的系数一起转移。
数据范围小把自然数幂和预处理了就好。
F： 每次操作可以在序列末补 0/1 或者删去最后一个字符，问 \(n\) 次操作得到字符串 \(s\) 的方案数。
差一部分没有想到。
容易发现 \(s\) 其实只有长度是有用的。
每两个保留下来的数之间的方案数是卡特兰数。
转移方程一样快速幂求就好。
最后就差第一个保留下来的数前面。
ARC060 virtual
远古题质量没有保证。。。
C 暴力DP。
D 分成小于和大于 \(\sqrt n\) 的，式子写出来就可以直接算。
E ST 表维护。
F 大胆猜结论，除了最小正周期外的点一般都合法，将一些不合法的点判掉就好。