CF1799E 题解
题外话：本来没打这场，但同寝室的巨佬 @赵悦岑 在打，所以我说帮他口胡一下 E，结果我口胡出来的时候他还没过 B，而且一直到最后都没过！咳咳……
题意
给你一个 $n\times m$ 的矩阵，矩阵中有 . 和 #，且 # 构成两个四连通块。请用尽量少的操作，将一些 . 改成 # 使得所有 # 构成一个四连通块，且任意两个 # 的最短路（只经过 # ）为他们的曼哈顿距离。
分析
由题目要求，我们可以发现一些简单的性质：如果一个格子上下或左右都有 #，则他必定会被染成 #，否则无法满足条件。补充完这些后，如果此时只剩一个连通块，那么就做完了。否则继续考虑这个性质：对于上下左右四个边界，一定只会出现单峰的情况，而且剩下的两个连通块一定是左上-右下或右上-左下的，而且不会有某一行或某一列出现两个 # 属于不同连通块。现在我们只考虑左上-右下型的。一个显然的想法是先分别把左上的右下角补齐，把右下的左上角补齐，再用一条简单的路径把两个连通块连起来。举个例子，如果图是这样的：
1 | ###.... |
那么我们补充完后可以是这样的：
1 | ###.... |
不难证明，这样补充填充的 # 一定是最少的。
代码
有点长，放在这里。