題目鏈接：點擊這里
題意：有一個
n
×
m
n×m
n×m 的矩陣
M
M
M，通過反復選擇子矩陣
a
×
b
a \times b
a×b 并且使子矩陣中的所有元素都減去
1
1
1，問最終矩陣
M
M
M 能否變為全
0
0
0，如果可能，在一行中列印 ^_^，否則在一行中列印 QAQ，
思路：從左上角開始，一行一行地減去當前值使之變為
0
0
0，利用二維差分可以快速實作這個操作，如果中途出現了負數或最后不全為
0
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;
}
微信公眾號《演算法競賽求職》，致力于詳細講解競賽和求職所涉及到的演算法原理和模板，歡迎關注，一起交流進步！
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/195236.html
標籤：其他
上一篇：C語言練習