传送门：[SDOI2011] 打地鼠
话说最近做了一些好玩的题却懒得写 blog
看看能不能在 $APIO$之前更完我想写 $blog$的题 $flag+1$
题目大意：给定一个 $n \times m\;(n,m\leq 100)$的矩阵，每次可以选择一个固定大小 $r \times c$的子矩阵，将子矩阵里的所有元素 $-1$，且在操作过程中不能出现负数，求将整个矩阵变为零矩阵的最少步数（说白了就是求一个最大的符合条件的子矩阵）
这道题的推导其实超可爱的，首先我们会发现一个显然的结论（其实关键点就在这一步）：
如果一个 $2r\times c$的子矩阵可以被选择，则 $r \times c$的子矩阵绝对可以被选择（可以选择两个相邻的子矩阵进行操作，等价于选择一个大两倍的子矩阵进行操作），反之如果 $r\times c$的子矩阵不可以被选择，则
那么我们可以用它推导另一个结论：
我们称 $1\times c$的矩阵为行矩阵，$r\times 1$的矩阵为列矩阵。
设最大子矩阵的大小为 $r\times c$，则 $1\times c$的子矩阵和 $r \times 1$的子矩阵分别是行，列最大子矩阵。
我们用反证法来证明这个结论：
如果存在大于行最大子矩阵 $1\times c’\;(c’>c)$，那么由第一个结论可知，最大子矩阵应该是 $r\times c’$的，与原命题矛盾。得证。
其实这篇文章写到这里就差不多了，因为通过第二个结论，你可以用 $\Theta(n^4)$的时间找到一个最大行矩阵和最大列矩阵，乘起来就是最大子矩阵啦~
然而那样多没意思，有什么更快的做法吗？
想想前面我们的思考过程，如果我们一开始没有抓住第一个结论并顺着推下去，我们又该怎么做呢？
首先暴力的 $\Theta(n^6)$（枚举最大子矩阵行列，暴力模拟修改矩阵）肯定是人人都能想到，稍微快一点的话我们还可以用 $BIT$去维护矩阵，复杂度 $Theta(n^4log^2n)$，可是这样做跑不过去呀 $QwQ$
其实我们不妨想一下我们的操作中有那一步是可以化简的，我们每次的修改操作都是 $\Theta(n^2)$级别的，我们可以通过差分来直接做到 $\Theta(1)$修改。那么即使是暴力修改，也是 $\Theta(n^4)$的。差分就是这样的一个神奇操作（比如说 $GDOI Day1 T2$就是一个想到差分就成水题的题，然而我这种菜鸡想了两个小时没搞出来）
另外如果想到了第一个结论但没想到第二个结论，其实可以利用子矩阵的积性（小的子矩阵不能选，它的任意整数倍一定不能选）来筛掉不可能的情况，具体实现的话可以参考 $PoPoQQQ$大爷的写法：Orz_PoPoQQQ’s_idea
然后我为了偷懒就把第一种和第二种结合起来写了个 $\Theta(n^3)$的（因为怕写 $O(n^4)$的时间太丑）说白了就是把第一种方法加一个差分罢了没啥好说的。
代码：
#include<bits/stdc++.h>
#define N 105
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
int n, m, a[N][N], b[N][N], tmp[N][N], ans;
inline bool check ()
{
fo (i, 1, n)
fo (j, 1, m)
if (tmp[i][j]) return 0;
return 1;
}
int main ()
{
scanf("%d %d", &n, &m);
fo (i, 1, n)
fo (j, 1, m)
{
scanf("%d", &a[i][j]);
ans += a[i][j];
}
memcpy(b, a, sizeof a);
fd (i, n, 1)
fd (j, m, 1)
a[i][j] -= a[i - 1][j];
fd (i, n, 1)
fd (j, m, 1)
b[i][j] -= b[i][j - 1];
fd (k, n, 2)
{
memcpy(tmp, a, sizeof a);
int tmpn = n - k + 1;
fo (i, 1, tmpn)
fo (j, 1, m)
{
tmp[i + k][j] += tmp[i][j];
tmp[i][j] = 0;
}
if (check())
{ans /= k; break;}
}
fd (k, m, 2)
{
memcpy(tmp, b, sizeof b);
int tmpm = m - k + 1;
fo (i, 1, n)
fo (j, 1, tmpm)
{
tmp[i][j + k] += tmp[i][j];
tmp[i][j] = 0;
}
if (check())
{ans /= k; break;}
}
printf("%d", ans);
return 0;
}
突然感觉这篇有点水，那我。。。哎算了我本来就很水。（无奈脸.jpg）
0 条评论