CF Round#802 Div.2
A. Optimal Path
题意：给一个\(n*m\)的矩阵，\(a(i, j) = (i - 1)m + j\)，求一条从\((1, 1)\)到\((n,
m)\)的最小权值路径。
题解：总步数是确定的，横向移动和竖向移动分别会为后面的每一步增添一个额外的代价，贪心做一下。
B. Palindromic Numbers
题意：给定一个大整数，求另一个与之长度相同的数，使得二者之和为回文数。
题解：构造，如果首位是9，那么一定可以满足回文数为全1，否则构造全9的回文数。
C. Helping the Nature
题意： 给定数组\(a\)，可以使一个前缀或一个后缀都减一，可以使数组整体加一，求最少次数使得数组元素变为完全相同。
题解：
转换为对差分数组操作，就变成了单点加一和减一，和不修改，前两种是唯一可以改变差分数组的操作，要让差分数组变为全0，再考虑整体需要加或者减几次。
D. River Locks
题意：
有若干水闸，前面的水满了会溢到后面去，每个闸有自己的容量，多次询问若要求\(t\)时间内将所有水闸放满，至少需要打开几个闸门的入水口。
题解：
注意到前面的水可以留到后面，后面不能去前面，所以一定是打开最前面若干个闸门的入水口，因此不断对前缀做判断即可。这里注意要规避掉某个极大的闸门在前面，放满它的时间是整体时间的平静。
E. Serega the Pirate
题意： 有一个\(n*m\)的矩阵，里面填有\(1\)到\(n*m\)，从\(1\)开始走，可以走重复的格，但是要严格按照升序\(1, 2, 3
...\)走，求是否有解，如果没有的话求有几种方案可以交换两个数的位置使得存在解。
题解：
做题的时候想到的是并查集来判断解存不存在，但是很脑筋急转弯的是只要每个点都存在一个相邻的更小的值，那么就一定存在解，可以归纳证明。
基于此考虑没解的情况下怎么求方案数，交换两个点只会影响交换的两个点周围的点以及本身，那么找一个周围都更大的点\(x\)，可能的方案只可能是一个点在\(x\)及周围，另一个在\(x+1\)附近，因此暴力枚举方案，依次做暴力验证即可，注意这里可能会有重复的方案。
F. Puzzle
题意： 给出两个\(2*n\)的01矩阵，可以交换两个相邻位置的数，求最少次数使得矩阵1变为矩阵2。
题解：
乍一看像是dp，但是不太好描述状态。考虑一个退化的情况，如果只有一行，那么直接按顺序分配即可，那么扩展到两行。不妨假定把竖向的操作提到最前面，已经完成了竖向的操作，那么两行内就直接按顺序分配即可。
这道题有个很新颖的想法就是换一种计算一行内情况的方式，正好是01数组，两个数组的前缀和做差，再求绝对值的和就是需要的操作次数。
那么在这个基础上考虑，纵向的移动相当于把一行的前缀和的后缀减一，另外一行的前缀和的后缀加一，考虑怎么让这个和最小。
考虑从左到右扫描，在某一列遇到了1，记第一行前缀和差为\(f_{1}\)，第二行前缀和差为\(f_{2}\)，如果\(f_{1}\)和\(f_{2}\)异号，不妨假设\(f_{1} \gt 0, f_{2} \lt 0\)，那么说明第一行前面有多余的1，第二行缺少了1，这是把第一行的1移动下来一定是最优的。
证明如下，考虑一个情况如下矩阵，那么在右上角及其右侧的第一行对于1的需求由矩阵中任何的1移动而来需要的代价是相同的，左下角及其左侧也是一样的。
\[\begin{pmatrix} 1&0\\ 0&1\\ \end{pmatrix}\]
其他的情况可以手玩一下，可以得出类似的证明，而且当\(f_{1}\)和\(f_{2}\)异号时，一定是刚刚变为异号，即绝对值为1，因此这种情况下把多余的1纵向交换到另一行一定是最优解，贪心从左到右扫描即可。