题意：
一个给定的矩阵，然后给定一个子矩阵的大小，子矩阵可以 将覆盖矩阵的区域的值减1，问能否将矩阵全部减为0
题解：
思路和下面这个链接讲的题十分相似
传送
本质就是二维树状数组差分求解
用mp数组来存矩阵，然后对空白的data数组进行构造，构造完对mp进行清理，最后要看data能否构造出mp的样子，也就是看mp是否全为0
从左上角到右下角的顺序开始处理
代码：
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
typedef long long ll;
ll mp[1005][1005];
int m,n,a,b;
int t;
const int MAX = 1123;
ll data[MAX][MAX];
int lowbit(int x) {
return x&-x;
}
void Add(int x, int y, ll w) {
for (int i = x; i <= n; i += lowbit(i)) {
for (int j = y; j <= m; j += lowbit(j)) {
data[i][j] -= w;
}
}
}
void Add2(int x, int y, ll w) {
for (int i = x; i <= n; i += lowbit(i)) {
for (int j = y; j <= m; j += lowbit(j)) {
data[i][j] += w;
}
}
}
ll Sum(int x, int y) {
ll ans = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
for (int j = y; j > 0; j -= lowbit(j)) {
ans += data[i][j];
}
}
return ans;
}
int g(){
for(int i=1;i+a-1<=n;i++){
for(int j=1;j+b-1<=m;j++){
ll num=Sum(i,j);
num=mp[i][j]-num;
mp[i][j]=num;
if(mp[i][j]>0){
int x1, x2, y1, y2;
x1=i;x2=i+a-1;y1=j;y2=j+b-1;
Add2(x1, y1, mp[i][j]);
Add(x2+1, y1, mp[i][j]);
Add(x1, y2+1, mp[i][j]);
Add2(x2+1, y2+1, mp[i][j]);
mp[i][j]=0;
}
else if(mp[i][j]<0){
return 1;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i>n-a+1||j>m-b+1)mp[i][j]-=Sum(i,j);
if(mp[i][j]!=0){
return 1;
}
}
}
return 0;
}
int main(){
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d",&n,&m,&a,&b);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%lld",&mp[i][j]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
data[i][j]=0;
}
}
int sign=g();
if(sign==0){
printf("^_^\n");
}else{
printf("QAQ\n");
}
}
return 0;
}
京公网安备 11010502036488号