ARC130 A-D
A Remove One Character
对每个连续块分别处理即可。
B Colorful Lines
非常经典的题目，对于每一行每一列记录最后出现的颜色并计算贡献即可。
C Digit Sum Minimization
有点细节。枚举最后两个数，显然加起来超过十是很好的；然后前面的数应该尽量凑九，然后要注意尽量不选九，因为最后长数可以留一串九进位。
D Zigzag Tree
考虑根节点是大点还是小点，确定之后其他点直接黑白染色（或者说大小染色）。从下到上考虑贡献，用 \(f_{x,y}\) 表示当前子树 \(x\) 中根节点排名为 \(y\) 的方案数，随便优化一下就可以做到 \(O(N^2)\)。
ARC131 A-E
A Two Lucky Numbers
很简单的构造。
B Grid Repainting 4
五种颜色，还是四相邻。无脑判断即可。
C Zero XOR
对 \(n\) 的奇偶性分类讨论。先说奇数，直觉上来说应该是必赢的，可以证明。
假设当前异或和为 \(s\)，如果数列中存在 \(s\)，那么选择这个数即可获得胜利。其它的情况可以按值把元素分类，然后希望选择一个数使得后手不存在选另一个数的方案让两个数异或和恰为 \(s\)。把集合们按 \(s\) 互补两两配对，如果有落单的盲选这个即可。剩下的就是两两配对的情况了，然而似乎并不存在这种情况。然后然后分类讨论云云。最后发现尼玛数列互不相同那不是很傻逼。
于是奇数可以误伤转移到下一轮，显然是必胜的；偶数要么一击致命，要么把奇数留给后手，让后手必胜自己寄掉。然后就没了。
D AtArcher
显然应该尽量靠近，考虑一定有一个点在 \([0,D]\) 的范围内，并且其余的点在两边均匀分布，证明上调整一下就出来了。于是枚举中心点的位置并动态计算答案取最大值即可。
E Christmas Wreath
考虑满足不存在斑斓三角形的方法，大概方法就是考虑一个点的入边颜色全部相同，这样一定能保证两条边颜色相同。问题转化成给定连续数分三组，组内和相同的方案数。答案是显然的。
ARC132 A-E
A Permutation Grid
简单讨论大小关系即可。
B Shift and Reverse
简单分类讨论。
C Almost Sorted
简单的状压DP，记录周围十个数的使用情况正常转移即可。
D Between Two Binary Strings
考虑 \(n\) 个 \(1\) 会形成 \(2n\) 个无用空挡，于是思考如何最大化有用的，即相邻相同和与边界相邻的情况数。题目限制相当于给定了一些区间，并且这些区间具有可以高效转移的性质。考虑用 \(f_x\) 代表前 \(x\) 个 \(1\) 最多能产生多少有用的空隙，然后思考当前 \(1\) 和哪些 \(1\) 连续，显然存在一个分界点，二分出来取后缀最大即可。注意边界，复杂度为 \(O(n\log n)\)。
E Paw
感觉被诈骗了。遇到这种问题应该先考虑最终形态是否有什么特殊性质，发现就这道题而言是有的。会发现最终的 形态应该是中间存在一个空隙，两边有连续的一直绵延到边界的脚印。于是想到每个空隙称为幸运儿的概率。发现成为幸运儿当且仅当两边都不经过这个空隙，令 \(n\) 个方块并且不会碰到特定边界的概率为 \(f_x\)，发现这玩意似乎可以递推。考虑当前块在排列中的位置，令为倒数第 \(y\) 个，那么前面的可以忽略，后面的就转化成了一个规模为 \(y\) 的子问题。于是有 \(f_{x}=\sum\limits_{i=0}^{x-1}f_{i}\dfrac{1}{2x}\)，维护一下前缀和就能常数转移了。然后计算贡献即可，复杂度 \(O(n)\)。
标签：arc132,相同,arc130,题解,然后,即可,空隙,考虑,边界 From： https://www.cnblogs.com/Feyn/p/17636909.html