CF1753
成功因为虚拟机炸了，重新写一遍此文。
都是没有保存的错。
A. Make Nonzero Sum
由于 Note that it is not required to minimize the number of segments in the partition.。考虑每一段最小化……
可以发现，每一段都可以划分为长度为 1 或 2 的段。于是考虑影响。
只有长度为 2 的段会改变正负，不妨令 \(C_+, C_-\) 分别表示 1 和 -1 的个数，并假定 1 更多。
不难发现，只需要 \(\frac {|C_+ - C_-|}2\) 个长度为 2 的即可。
如果不是整数，那么直接判不可以即可。
由于有影响，考虑 DP。
设 \(f_i\) 表示考虑前 \(i\) 个数，最多能够放多少个长度为 2 的。
于是有
\[f_i = \max \begin{cases} f_{i - 1} \\ f_{i - 2} + 1 &, a_i = 1 \end{cases} \]考虑在 DP 变化的地方放置长度为 2 的即可。
B. Factorial Divisibility
当时脑子抽了，用了两种合并的方法。
但是实际上只需要通过 \(x! = x \times (x -1)!\) 合成即可（2048……
C. Wish I Knew How to Sort
假定有 \(C_0\) 个 \(0\)，并且在前 \(C_0\) 个数中有 \(k\) 个 1。
那么考虑此时一个有效的操作，即是在前 \(C_0\) 中选择到了一个 \(1\)，在后面中选择了一个 \(0\)。
有效的概率为
\[P_k = \cfrac {k^2}{n \choose 2} \]于是考虑状态转移，设 \(f_k\) 表示从前 \(C_0\) 个数中有 \(k\) 个 \(1\) 的状态转移到 \(0\) 个 \(1\) 的期望步数。
根据 markov 中的期望线性方程求解的方法，有
\[f_k = 1 + (1 - P_k)f_k + P_k f_{k - 1} \]稍微魔改一下，就变成了：
\[f_k = \frac {1}{P_k} + f_{k - 1} \]于是小小递推即可。
然而我当时是反着推的，无所谓，一样的：Submission #211560140 - Codeforces
D. The Beach
转换问题：等价于将两个 . 移动到一起的最小代价。
显然可以发现，一个障碍最多移动一次。
借用大佬的图：
于是我们可以考虑如此建图。跑一个最短路即可。
提交：Submission #211566195 - Codeforces
E. N Machines
非常恶心，虽然不是顶级难度。
最优的策略一定是把乘法向后移，把加法向前移。
思考 It's guaranteed that the current value of the resulting product does not exceed 2x10^9. 的意义。
发现，除去 \(\times 1\)，最多只会有 \(\log C\) 个乘法。
于是考虑枚举其子集，为 \(2^{\log C}\)。所以需要优化。
有一个简单而优雅的剪枝：如果两个数相等，那么一定是选择最前面的。
由于 \(12! = 6227020800 \gt 2 \times 10^9\)，所以其实最多只会有 \(O(2^{12})\) 种状态。
那么在钦定了向后移动的乘法后，我们需要找到前 \(rest\) 个移动到前面贡献最大的加法。
考虑二分移动到前面的贡献 \(\Delta\)，在每一段再二分数量。
考虑如何计算每一个加法的 \(\Delta\) ？考虑加法移动前，其贡献为 \(x \times suf_x\)，移动后的贡献为 \(x \times pre_x \times suf_x\)。
其中 \(suf_x\) 和 \(pre_x\) 是指乘法移动后，\(x\) 前面的乘法前缀积和后面的乘法后缀积。
于是 \(\Delta x = x \times (pre_x - 1) \times suf_x\)。
NOTICE：
-
二分 \(\Delta\) 时找到最大的 \(cnt > rest\) 的那个 \(\Delta\)，由于多算了 \(cnt- rest\) 个，并且这些数的贡献一定是 \(\Delta\)，所以再减去 \((cnt - rest) \times \Delta\) 即可。
-
\(\Delta\) 可能很大很大，所以上界大一点（我用的倍增，所以直接是从 \(2^{60}\) 开始向下……虽然没必要）
提交：Submission #211609810 - Codeforces
F. Minecraft Series
首先固定一个正方形，考虑贡献：将数分为正数与负数，分别计算 \(mex_p\) 与 \(mex_n\)。
正的为
positive，负的为negative。
于是贡献为 \(mex_p + mex_n - 1\)。
由于 \(mex\) 的单调性，发现包括合法正方形的正方形一定合法，所以考虑双指针维护所在最小合法正方形的。
注意，是在每一条对角线上来一发双指针，这样才能保证复杂度。
然后，然后就搞定了。
可以优化的是，\(mex\) 可以利用分块优化复杂度。
于是你可以得到一个复杂度为：
\[O(nm \cdot \min\{n, m\} + n m \sqrt k) \]的优雅 brute force……
提交：https://codeforces.com/contest/1753/submission/211685792
标签：CF1753,times,Delta,考虑,移动,mex,乘法 From： https://www.cnblogs.com/jeefy/p/17521324.html然而……不断的 TLE 让我怀疑人生，最后发现……
参考：讨论