2020ICPC·小米网络选拔赛第一场 J.Matrix Subtraction（二维差分）

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

题目链接：https://ac.nowcoder.com/acm/contest/9541/J

题目描述
Given a matrix M_{}M of size n\times mn×m and two integers a, b_{}a,b , determine weither it is possible to make all entrys of M_{}M zero by repeatedly choosing a\times ba×b submatrices and reduce the values in the chosen matrices by 1. If possible, print “^_” in one line, or print “QAQ” in one line.

输入描述:
The first line contains one integer T~(1\le T \le 100)T (1≤T≤100), denoting the number of test cases.

For each test case:

The first line contains four integers n,m,a,b~(1\le n,m \le 1000, 1\le a\le n, 1\le b\le m)n,m,a,b (1≤n,m≤1000,1≤a≤n,1≤b≤m), denoting the size of given matrix and the size of chosen submatrices respectively.The next n_{}n lines each contains m_{}m integers M_{i,j}~(0\le M_{i,j} \le 10^9)M i,j (0≤M i,j≤10 9 ), denoting the entrys of matrix M.
It’s guaranteed that \sum nm \le 10^6∑nm≤10 6.

输出描述:
Print T lines each containing a string “^_” or “QAQ”, denoting the answer to each test case.

示例1

输入

输出

QAQ
^_^

题意

给出一个 n * m 的矩阵，每次可以使大小为 a * b 的子矩阵同时减去一个数，问能否使原矩阵变为零矩阵。

分析

想一想，如果某个矩阵是符合要求的，那么我们如果从左上角按顺序放下子矩阵，然后将子矩阵内所有元素都减去最该子矩阵内最左上角的元素，最后肯定是一个零矩阵，若出现负数，则不符合要求。
我们发现如果用一般的方法的话肯定会超时，我们可以用二维差分来解决。
二维差分可以在这里学习一下：https://blog.csdn.net/justidle/article/details/104506724
注意，如果在二维差分的过程中已经出现了负数的差分，则就可以退出了，如果再继续下去可能会将不符合要求的掩盖掉（减去了负数）。

代码

#include<bits/stdc++.h>
using namespace std;int t;
int p[1007][1007],g[1007][1007];
int n,m,a,b;int main()
{scanf("%d",&t);while(t--){int flag = 1;scanf("%d%d%d%d",&n,&m,&a,&b);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&g[i][j]);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)p[i][j] = g[i][j] - g[i - 1][j] - g[i][j - 1] + g[i - 1][j - 1];for(int i=1;i<=n-a+1;i++)for(int j=1;j<=m-b+1;j++){int t = p[i][j];if(t < 0) flag = 0;p[i][j] -= t;p[i][j + b] += t;p[i + a][j] += t;p[i + a][j + b] -= t;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){p[i][j] = p[i][j] + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];if(p[i][j] != 0) flag = 0;}if(flag == 1) printf("^_^\n");else printf("QAQ\n");}return 0;
}