5396. 棋盘 - AcWing题库
算法思路:
像这种通过改变两个坐标上的值去改变一个区间的值一般都是用差分
所以这道题一眼差分矩阵
我们自己构造一个差分矩阵,一个全为0的差分矩阵,然后每有一个计数,我们就把这个区间上的数加上1,我们不能固定思维,我们可以每次都加上1,然后去模上2,就知道你加的是偶数还是奇数,如果是奇数的话那就是黑,偶数就为白
#include<iostream>
#include<cstring>
#include<cmath>
#define int long long
using namespace std;
const int N = 2e3 + 10;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2)
{
b[x1][y1] += 1;
b[x1][y2 + 1] -= 1;
b[x2 + 1][y1] -= 1;
b[x2 + 1][y2 + 1] += 1;
}
signed main()
{
int n, k;
cin >> n >> k;
while (k--)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
insert(x1, y1, x2, y2);
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
if (b[i][j] % 2 == 0) cout << 0;
else cout << 1;
}
cout << endl;
}
return 0;
}