2020ICPC·小米网络选拔赛第一场 J.Matrix Subtraction (贪心,二维差分)

题意:给一个\(nXm\)的矩阵,可以选取\(aXb\)的子矩阵,使子矩阵中的所有元素减一,问最后是否能使矩阵中所有元素变为\(0\).
题解:首先贪心,我们看最左上角的元素,如果\(g[1][1]\ge0\),那么我们就要对其子矩阵的所有元素减去\(g[1][1]\),然后因为\(g[1][1]\)已经是\(0\)了,假如\(g[1][2]\)存在的话,我们就只能让它成为子矩阵的左上角然后再对所有子矩阵减去\(g[1][2]\),以此类推,但是直接暴力的话复杂度会炸,我们需要用数据结构来维护,直接用二维差分即可,每次枚举到某个元素的时候判断它是否不小于\(0\),如果不是就不合法.

代码:

int t;

int n,m,a,b;

int g[1010][1010];

int p[1010][1010];

void updata(int i,int j,int ii,int jj,int c){

    p[i][j]+=c;

    p[ii+1][j]-=c;

    p[i][jj+1]-=c;

    p[ii+1][jj+1]+=c;

}

void solve(){

    n=read(),m=read(),a=read(),b=read();

    for(int i=1;i<=n;++i){

        for(int j=1;j<=m;++j){

            g[i][j]=read();

            p[i][j]=g[i][j]-g[i-1][j]-g[i][j-1]+g[i-1][j-1];

        }

    }

    for(int i=1;i<=n;++i){

        for(int j=1;j<=m;++j){

            p[i][j]=p[i][j]+p[i-1][j]+p[i][j-1]-p[i-1][j-1];

            if(p[i][j]<0){

                puts("QAQ");

                return;

            }

            else if(p[i][j]>0){

                if(i+a-1>n || j+b-1>m){

                    puts("QAQ");

                    return;

                }

                else updata(i,j,i+a-1,j+b-1,-p[i][j]);

            }

        }

    }

    puts("^_^");

}

int main() {

    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    t=read();

    while(t--){

        solve();

    }

    return 0;

}

巴特西

2020ICPC·小米网络选拔赛第一场 J.Matrix Subtraction (贪心,二维差分)

最新文章

热门文章

巴特西

2020ICPC&#183;小米 网络选拔赛第一场 J.Matrix Subtraction (贪心,二维差分)

最新文章

热门文章

2020ICPC·小米网络选拔赛第一场 J.Matrix Subtraction (贪心,二维差分)