CF Round#941 Div.2
A. Card Exchange
题意：给定\(n\)个数，可以选择\(k\)个相同的数变为\(k-1\)个任意数，求操作后最少剩几个数。
题解：只要能开始操作，答案就是1。
B. Rectangle Filling
题意：给定一个二维黑白染色矩阵，操作是选择两个颜色相同的块，将这两个块对应的矩形染为这个颜色，求是否能将矩阵染成纯色。
题解：手玩一下，不能染为纯色的充要条件是黑色和白色各站住了对侧最边缘的一条（左右/上下）。
C. Everything Nim
题意：一堆石子，每次要从所有所有堆中拿走一样多的石子，不能操作的输。
题解：差分一下变成从一堆石子里面取，然后倒着推一下状态，只考虑数量是否为1就可以。
D. Missing Subsequence Sum
题意：构造一个数组，子序列的和可以覆盖\([1,n]\)，但是不能含有\(k\)。
题解：首先构造\([1,k-1]\)，类似二进制的方式构造，最后一步跟\(k\)做差算一下，然后后面很简单地缺什么加什么，例如得到\([1,k-1]\)后添加\(k+1\)，子序列和对应\([1, 2k]\)，然后添加\(2k+1\)，注意这次开始会引入新的缺陷\(3k+1\)，然后逐次添加缺陷即可，会发现缺陷每次会倍增，因此构造的数组不会超过\(log2_{2}\)级别。
E. Folding Strip
题意：一个01纸带，定义合法的折叠是指折叠后空间上重合的纸袋数字相同，求经过合法折叠后纸带最短的长度。
题解
看着很像回文串相关，区间dp相关，但是仔细想做不了一点，全是后效性和影响。因此尝试找性质，提出一种可能：在每个相邻的相同数字之间都折一下，是一种合法的折叠方案。证明从奇偶性考虑，这样折叠后按照下标考虑，所有的0和1奇偶性一定不同（相同的就被折叠了），因此在空间上重叠的一定都相同，方案合法。这样折叠之后不可能再次折叠了，而且通过回文的性质可知，局部的回文折叠不会影响更长的回文串，因此这个折法是最优方案。
考虑怎么求解最后剩余的纸带长度，从空间上一层一层摊开，可以认为纸带先往一个方向延申，遇到需要折叠的地方再调转方向，这样就可以模拟一个数轴，记录纸带到达的最左侧和最右侧，做差即为折叠后并在一起的纸带的长度。实际代码特别短，这道题很有意思。
F. Missing Subarray Sum
题意：有一个回文数组，给出所有子数组的和，但是去掉了其中一个，尝试还原数组。
题解：回文的性质很好地限制了数组的构成，但是不太好找出被删掉的数是什么。那么分情况讨论一下：如果数组是奇数长度\(2k+1\)，那么子数组的和构成的序列中，应该会有\(k+1\)个出现过奇数次的和，且保持一样的奇偶性；如果数组是偶数长度\(2k\)，应该会有\(k\)个出现过奇数次的和，且都为偶数。那么就可以根据这个性质得出，删掉的数到底是本应出现奇数次的中心对称回文的和，还是一个本应出现偶数次的和。
分情况讨论，如果删掉的是本应出现奇数次的和，也就是删掉了一个中心对称的回文和：那么我们先当作没有删，去重建这个数组，可以发现相当于得到的数组相比于原数组，会有两个数合在了一起，对应着被删掉的和的位置。举例来说原数组在\(a_{x}=3,a_{x+1}=2\)，那么在重建数组中只会得到\(a_{x}=5\)，因为区间和\(a_{x+1, n}\)被删掉了。同样地，如果是删掉了偶数次的和，那么会有一个数被拆开成两个数。
那么我们比较重建数组的子数组和与给出的删掉一个数的原数组和，排序后第一个不同的和\(t\)就代表着两个数组的差异。对于两个数合二为一的情况，说明原数组的和刚好只包含了两个数之一，对于拆开的情况，则是重建的和包含了拆开的两个数之一。无论哪个情况，这个和都包含着回文数组和的一半，再加上从中心到达两个数之一的子数组之和。
如果删除的不是数组的最大值\(sum\)，那么就可以通过\(2 * t - sum\)来算出删掉的和，补全后重建即可。如果删除的正好是数组的最大值，那么仍然这么做，可以发现\(t=a_{1, n - 1}\)，依然可以还原出删去的值。