AcWing 5396. 棋盘
原题链接
简单
作者:
颓废
,
2024-04-09 11:04:36
,
所有人可见
,
阅读 3
差分裸题 思路:二维区间棋子颜色取反等价于让二维区间每个数加一,最后求得前缀和数组,偶数为白字,奇数为黑子
时间复杂度$O(n^2)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int b[N][N];
int n,m;
void insert(int x1,int y1,int x2,int y2,int c)
{
b[x1][y1]+=c;
b[x2+1][y1]-=c;
b[x1][y2+1]-=c;
b[x2+1][y2+1]+=c;
}
int main()
{
cin>>n>>m;
while(m--)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
insert(x1,y1,x2,y2,1);
}
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";
}
puts("");
}
return 0;
}