深圳专业做网站排名公司哪家好,做网站可能遇到的困难,湖州建设网站制作,电商网站开发报告Matrix Subtraction
题意#xff1a;
一个给定的矩阵#xff0c;然后给定一个子矩阵的大小#xff0c;子矩阵可以 将覆盖矩阵的区域的值减1#xff0c;问能否将矩阵全部减为0
题解#xff1a;
思路和下面这个链接讲的题十分相似 传送 本质就是二维树状数组差分求解 用…Matrix Subtraction
题意
一个给定的矩阵然后给定一个子矩阵的大小子矩阵可以 将覆盖矩阵的区域的值减1问能否将矩阵全部减为0
题解
思路和下面这个链接讲的题十分相似 传送 本质就是二维树状数组差分求解 用mp数组来存矩阵然后对空白的data数组进行构造构造完对mp进行清理最后要看data能否构造出mp的样子也就是看mp是否全为0 从左上角到右下角的顺序开始处理
代码
#includestdio.h
#includeiostream
#includestring.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 i1;ia-1n;i){for(int j1;jb-1m;j){ll numSum(i,j);nummp[i][j]-num;mp[i][j]num;if(mp[i][j]0){int x1, x2, y1, y2;x1i;x2ia-1;y1j;y2jb-1;Add2(x1, y1, mp[i][j]);Add(x21, y1, mp[i][j]);Add(x1, y21, mp[i][j]);Add2(x21, y21, mp[i][j]);mp[i][j]0;}else if(mp[i][j]0){return 1;}}}for(int i1;in;i){for(int j1;jm;j){if(in-a1||jm-b1)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 i1;in;i){for(int j1;jm;j){scanf(%lld,mp[i][j]);}}for(int i1;in;i){for(int j1;jm;j){data[i][j]0;}}int signg();if(sign0){printf(^_^\n);}else{printf(QAQ\n);}}return 0;
}
