題目鏈接
https://ac.nowcoder.com/acm/contest/7501?&headNav=www#question
題意
給定 n* m 矩陣，可以多次對矩陣中a* b的小矩陣全部元素減一，求是否可以全減為0
思路
從上到下，左到右遍歷每一個元素，對于每一個元素當前值ai，將以他為第一行第一列的a*b矩陣全部減去ai，遍歷完成后，如果所有值都為零，則說明可以實作，否則不能，
暴力演算法復雜度是O（nmab）的，我們可以用二維差分優化區間修改，
一維差分diff[i]=a[i]-a[i-1],對x，y區間加上z，可以對diff[x]+=z，diff[y+1]-=z.最終對其取前綴和就是原陣列，
二維差分diff[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1],若在矩形x1 y1,x2 y2范圍加z，則對diff[x1][y1]+=z,diff[x1][y2+1]-=z,diff[x2+1][y1]-=z,diff[x2+1][y2+1]+=z，原陣列則可以使用二維前綴和還原，
我們將矩陣元素減為0，則diff陣列也全為零，則我們遍歷差分陣列，如果當前元素大于等于0，則把以該點為第一行第一列的小矩形利用差分陣列進行區間減法，否則則確定答案不存在，
代碼
#include<cstdio>
#include<iostream>
#include<iomanip>
#include<map>
#include<string>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
//#define int long long
//#define double long double
using namespace std;
typedef long long ll;
const int maxn=4005;
const int inf=0x3f3f3f3f;
int n,m,a,b;
int aa[maxn][maxn];
int diff[maxn][maxn];
int main(){
IOS
int tn;
cin>>tn;
while(tn--){
cin>>n>>m>>a>>b;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>aa[i][j];
diff[i][j]=aa[i][j]-aa[i-1][j]-aa[i][j-1]+aa[i-1][j-1];
}
bool bl=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int tmp=diff[i][j];
if(!tmp)
continue;
else if(tmp<0){
bl=0;
break;
}
else if(i<=n-a+1&&j<=m-b+1){
diff[i][j] -= tmp;
diff[i][j+b] +=tmp;
diff[i+a][j] +=tmp;
diff[i+a][j+b] -= tmp;
}
else{
bl=0;
break;
}
}
}
if(!bl)
cout<<"QAQ"<<endl;
else
cout<<"^_^"<<endl;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/193500.html
標籤：其他