区间修改——前缀和,差分或线段树或树状数组
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; }