题解 - QOJ 10019 Gold Coins

题意懒得写。

首先证明结论。

这段证明的大体思路是：找到一些基本的性质，把原问题转化为形象的“楼梯”模型，然后直观地说明结论。

基本约定

我们称 01 矩阵为“图形”，而其中符合题目条件的称为“合法图形”。

杨表这个名字很不近人情，我们下文称它为“楼梯”，如果还是不知道是啥的可以前往 WC2023 T1，楼梯的意思就是 1 的形状长成这样的图形。

对于一个合法图形中的每个 1，想像成滑块，它在原来矩形中的坐标是 $(x,y)$，称它为原块 $(x,y)$，也称它为实块 $(a_{x,y},b_{x,y})$。那么我们再令实块 $(x,y)$ 的原块坐标为 $(c_{x,y},d_{x,y})$。显然对于一个合法图形，实块和原块一一对应。

默认图形中已经去除了全 0 行和全 0 列。

上下左右和题目输入文本一致。

基本性质

基本是对题意的翻译。由于有对称性，交换 $x,y$ 轴仍然生效。

性质 1：$\forall x, \forall z<y$，存在原块 $(c_{x,z},d_{x,y})$。

考虑 $x=1$ 的 case 下这是显然的，然后把 $x=1$ 的实块全部删去，即可归纳。当然这也可以被归纳地用于判定合法性。

推论：$\forall x$，$c_{x,y}$ 单调递增，$d_{x,y}$ 单调不降。

转化为“楼梯”

我们先描述一下“下坠”。比如说把一个图形向上下坠，就是把每一列的 $1$ 变成这一列的一个前缀，而个数不变。向左下坠也是对应的。

任意图形向左下坠，然后向上下坠，会得到一个楼梯，我们称它为楼梯甲；先向上下坠后向左下坠亦然，我们称它为楼梯乙。

结论 1：一个图形为合法图形，当且仅当它的楼梯甲和楼梯乙完全相同。也就是说，每个原块在楼梯甲的终点和在楼梯乙的终点是一致的。

证明考虑两者的第一次下坠都可以让每个原块的某个维度变为实块。必要性：发现两维都被一致地确定了，所以双射已经被构造出来了。充分性：考虑一次下坠后该维坐标相同的必然按照原块的另一维坐标排序。根据性质 1，如果合法那么另一次下坠应该刚好归位，如果不归位就是双射不成立。

直观地解释

结论 2：楼梯甲和楼梯乙完全相同，等价于存在 $(x,y)$，使得 $[1,x]\times [1,y]$ 是全 1 矩阵，$[x+1,n]\times [y+1,m]$ 是全 0 矩阵，$[1,x]\times[y+1,m],[x+1,n]\times ]1,y]$ 都是合法图形。

考虑提取出楼梯丙，满足这些块在楼梯甲和楼梯乙的生成中都不发生位移。它们显然是一个楼梯，而且无论在哪个图形，它们位置不变。由于上面的推论，对于非空图形，$(1,1)$ 必须存在，所以楼梯丙非空。

反证法，假设不存在 $(x,y)$。那么楼梯丙和坐标轴形成了一些内凹。不存在满足条件的 $(x,y)$，也就是说无论在楼梯丙上怎么取 $(x,y)$，都一定存在原块 $(x_0,y_0)$，满足 $x_0>x,y_0>y$，同时我们要求在这样的条件下 $(x_0,y_0)$ 二元组最小。对原图进行向左下坠和向上下坠，$(x_0,y_0)$ 必然分投在 $(x,y)$ 的两侧，更准确地说是分别在 $(x,y)$ 左右的两个内凹。而做第二次下坠的时候任何点都不会逃出内凹，所以楼梯甲和楼梯乙就无法相等了，矛盾。

也可以感性理解为：必然存在至少一个分隔符，把两次滑动分开为互不干扰的子问题，如果无法分开说明两维已经发生了交叉，那就完了。

故合法图形必然存在至少一个 $(x,y)$。结合结论 1、2，本题结论得证。

结论：一个图形为合法图形，当且仅当存在 $(x,y)$，使得 $[1,x]\times [1,y]$ 是全 1 矩阵，$[x+1,n]\times [y+1,m]$ 是全 0 矩阵，$[1,x]\times[y+1,m],[x+1,n]\times ]1,y]$ 都是合法图形。

DP

由于 1 不能 变成 0，并且希望变化尽量小，所以在右下方 0 的轮廓线上做区间 DP。$O(n^3)$。