2020ICPC·小米網路選拔賽第一場 J.Matrix Subtraction

題目連結：點選這裡

題意：有一個 $n\times m$ 的矩陣 $M$，通過反覆選擇子矩陣 $a\times b$ 並且使子矩陣中的所有元素都減去 $1$，問最終矩陣 $M$ 能否變為全 $0$。如果可能，在一行中列印 ^_^，否則在一行中列印 QAQ。

思路：從左上角開始，一行一行地減去當前值使之變為 $0$，利用二維差分可以快速實現這個操作。如果中途出現了負數或最後不全為 $0$，則輸出 QAQ。

AC程式碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 1010;

int n, m, a, b;
int f[N][N];

// 給以(x1, y1)為左上角，(x2, y2)為右下角的子矩陣中的所有元素加上c
void add(int x1, int y1, int x2, int y2, int c)
{
    f[x1][y1] += c;
    f[x2 + 1][y1] -= c;
    f[x1][y2 + 1] -= c;
    f[x2 + 1][y2 + 1] += c;
}

bool judge()
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(f[i][j] != 0)
                return false;
    return true;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        memset(f, 0, sizeof f);
        
        scanf("%d%d%d%d", &n, &m, &a, &b);
        
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                int x;
                scanf("%d", &x);
                add(i, j, i, j, x);
            }
        }
        
        bool success = true;
        
        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];
                if(f[i][j] < 0)
                {
                    success = false;
                    break;
                }
                
                int ii = i + a - 1, jj = j + b - 1;
                if(ii <= n && jj <= m)
                {
                    add(i, j, ii, jj, -f[i][j]);
                }
            }
            if(!success)    break;
        }
        
        if(!success)
        {
            puts("QAQ");
            continue;
        }
    	
    	if(judge()) puts("^_^");
    	else    puts("QAQ");
    }
    
    return 0;
}

微信公眾號《演演算法競賽求職》，致力於詳細講解競賽和求職所涉及到的演演算法原理和模板。歡迎關注，一起交流進步！