传送门:[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)

分类: 文章

quhengyi11

喵(ฅ>ω<*ฅ)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *