区间修改——前缀和,差分或线段树或树状数组

Matrix Subtraction

https://ac.nowcoder.com/acm/contest/7501/J

题意:有t组输入,有一个n * m的矩阵,每次只能在n * m的矩阵中取一个a * b大小的矩阵,将其全部减一,问经过若干次后,能否将n * m的矩阵,都变为0,若可以输出"^_^",否则输出"QAQ"
分析:
把区间减一这个操作翻过来看,就是 地毯地毯题解(二维前缀和,差分)
此题为固定区间修改
区间修改————前缀和,差分或线段树或树状数组

#include<bits/stdc++.h>
using namespace std;
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int const N=1e3+7;
int n,m,a,b,f;
int mp[N][N];   //原数组
int c[N][N];   //差分数组
int main(){
  fio;
  int t;
  cin >> t;
  while(t--){
    f=0;
    memset(mp,0,sizeof(mp)); 
    memset(c,0,sizeof(c));
    cin >> n >> m >> a >> b;
    for(int i=1;i<=n;++i){
      for(int j=1;j<=m;++j){
        cin >> mp[i][j];
        c[i][j]=mp[i][j]-(mp[i-1][j]+mp[i][j-1])+mp[i-1][j-1]; 
      }
    }
    for(int i=1;i<=n;++i){
      for(int j=1;j<=m;++j){
        mp[i][j]=c[i][j]+(c[i-1][j]+c[i][j-1])-c[i-1][j-1];
        if(mp[i][j]<0){
          f=1;break;
        }
        if(i+a-1<=n&&j+b-1<=m){
          c[i][j]-=mp[i][j];
          c[i+a][j]+=mp[i][j];
          c[i][j+b]+=mp[i][j];
          c[a+i][b+j]-=mp[i][j];
        }
        else if(mp[i][j]!=0){
          f=1;break;
        }
      }
      if(f) break;
    }

    if(f) cout << "QAQ" << endl;
    else cout << "^_^" << endl;
  }
  return 0;
}
全部评论

相关推荐

点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务