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

发布于 2020-10-25  0 次阅读


题目大意:

Matrix Subtraction
给你一个n × m 的矩阵,每次可从矩阵中选择一个大小为a × b 的矩阵,使得该子矩阵的值全部减一
求最后能否使得整个矩阵值全部减为0

思路:

采取差分矩阵存储矩阵
从左上开始遍历矩阵,
若当前位置的值不为0,则以当前位置为子矩阵的左上角开始构建子矩阵,子矩阵所有值减去当前位置的值
若有操作使得当前位置的值小于0,则无法使得整个矩阵值全为0
若当前位置的值不为0,并且无法以当前位置为子矩阵左上角构建子矩阵则无法使得整个矩阵值全为0

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
// #define TDS_ACM_LOCAL
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=1009;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
inline int read(){
    int x=0, f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return f?-x:x;
}
inline void write(int x){     
    if(x < 0) {putchar('-');x = -x;}        
    if(x > 9)  write(x/10);
    putchar(x % 10 + '0');
}
int n, m, a, b;
long long x[N][N], d[N][N];
// 二维差分的区间修改
void add(int x, int y, int a, int b, int v){
    d[x][y]+=v;
    d[x+a][y+b]+=v;
    
    d[x+a][y]-=v;
    d[x][y+b]-=v;
}

void solve(){
    memset(d,0,sizeof(d));
    n=read(); m=read(); a=read(); b=read();
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            x[i][j]=read();
            d[i][j]=x[i][j]-x[i-1][j]-x[i][j-1]+x[i-1][j-1];// 构造差分矩阵
            // add(i,j,1,1,x[i][j]);
        }
    }
    int flag=0;
    for(int i=1; i<=n && !flag; i++){
        for(int j=1; j<=m && !flag; j++){
            // 从左上开始求得当前位置的值
            d[i][j]=d[i][j]+d[i-1][j]+d[i][j-1]-d[i-1][j-1];
            if(d[i][j]!=0){
                if(d[i][j]<0) flag=1;
                else{
                    if(i+1-1>n || j+b-1>m) flag=1;
                    else add(i,j,a,b,-d[i][j]);     // 将当前位置的值全部减去(区间减法)
                }
            }
        }
    }
    if(flag)    cout<<"QAQ"<<endl;
    else        cout<<"^_^"<<endl;
	return ;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    T=read();
    while(T--) solve();
    return 0;
}

平平无奇的在校大学生