2020小米网络赛第一场 Matrix Subtraction（二维前缀和）

本文主要是介绍2020小米网络赛第一场 Matrix Subtraction（二维前缀和），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
每次使得一个$a\ast b$的子矩阵每个值减1，问能否使得这个$n\ast m$的矩阵全部变成0。

思路：
也是套路题了，直接维护二维前缀和。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>using namespace std;typedef long long ll;const int mod = 1e9 + 7;
const int maxn = 1000 + 7;ll maze[maxn][maxn],f[maxn][maxn];ll get(int x1,int y1,int x2,int y2) {return f[x1][y1] - f[x1][y2] - f[x2][y1] + f[x2][y2];
}int main() {int T;scanf("%d",&T);while(T--) {int n,m,a,b;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",&maze[i][j]);f[i][j] = 0;}}int flag = 1;for(int i = 1;i <= n;i++) {for(int j = 1;j <= m;j++) {f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];ll sum = get(i,j,max(0,i - a),max(0,j - b));maze[i][j] -= sum;if(maze[i][j] < 0) {flag = 0;break;}if(i > n - a + 1 || j > m - b + 1) {if(maze[i][j] != 0) {flag = 0;break;}}f[i][j] += maze[i][j];}if(!flag) break;}if(flag) {printf("^_^\n");} else {printf("QAQ\n");}}return 0;
}

这篇关于2020小米网络赛第一场 Matrix Subtraction（二维前缀和）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---