可以发现棋子的颜色取决于棋子的操作次数。如果操作次数为奇数，棋子颜色就是黑色，否则就是白色，故只需计算出每个棋子被操作的次数即可。由于每次是对二维矩阵某个范围进行操作（相当于对每个位置加1）的，故使用二维差分维护即可。
C++代码：
#include<iostream>
using namespace std;
const int N = 2010;
int b[N][N];
int n, m;
void insert(int x1, int y1, int x2, int y2)
{
b[x1][y1] ++;
b[x1][y2 + 1] --;
b[x2 + 1][y1] --;
b[x2 + 1][y2 + 1] ++;
}
int main()
{
scanf("%d%d", &n, &m);
while(m --)
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &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];
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
{
if(b[i][j] % 2 == 0) printf("0");
else printf("1");
}
puts("");
}
return 0;
}
必须给我大哥狠狠支持上去，我大哥题解写得基本非常好，大家可以参考这位大哥的。
#include[HTML_REMOVED]
using namespace std;
int n,m,dif[2005][2005];
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i){
int x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
dif[x1][y1]+=1;
dif[x1][y2+1]-=1;
dif[x2+1][y1]-=1;
dif[x2+1][y2+1]+=1;
}
for(int i=1;i<=n;i){
for(int j=1;j<=n;j++){
dif[i][j]+=dif[i-1][j]+dif[i][j-1]-dif[i-1][j-1];
cout<<dif[i][j]%2;
}
cout<<endl;
}
return 0;
}
作者：1GNI5T3R
链接：https://www.acwing.com/solution/content/221574/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
import java.util.Scanner;
public class Main {
//在这里练习一下差分代码的写法 static void increment(int x1,int y1,int x2,int y2,int val,int[][]diff) { int n=diff.length; int m=diff[0].length; diff[x1][y1]+=val; if(x2+1<n) diff[x2+1][y1]-=val; if(y2+1<m) diff[x1][y2+1]-=val; if(x2+1<n && y2+1<m) diff[x2+1][y2+1]+=val; } static int[][]res(int[][]diff) { int n=diff.length; int m=diff[0].length; int[][]res=new int[n][m]; for(int i=0;i<n;i++) for(int j=0;j<m;j++) { if(i>0) diff[i][j]+=diff[i-1][j]; if(j>0) diff[i][j]+=diff[i][j-1]; if (i > 0 && j > 0) diff[i][j] -= diff[i - 1][j - 1]; // 移除重复计数 res[i][j] = diff[i][j]; } return res; } public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); int m=scanner.nextInt(); int[][]a=new int[n][n];// for(int i=0;i<m;i)
// {
// int x1=scanner.nextInt();
// int y1=scanner.nextInt();
// int x2=scanner.nextInt();
// int y2=scanner.nextInt();
// for(int j=x1-1;j<x2;j)
// for(int k=y1-1;k<y2;k)
// {
// if(a[j][k]==0)
// a[j][k]=1;
// else
// a[j][k]=0;
// }
// }
//这里来练习一下差分的写法
for(int i=0;i<m;i)
{
int x1=scanner.nextInt();
int y1=scanner.nextInt();
int x2=scanner.nextInt();
int y2=scanner.nextInt();
increment(x1-1,y1-1,x2-1,y2-1,1,a);
}
a=res(a);
for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { System.out.print(a[i][j] % 2 != 0 ? 1 : 0); } System.out.println(); } }}
为什么我写完时间还是超的
Scanner和System.out是很慢的,上网搜一下快读和快输出就能过了,当输入和输出超过 1万 的时候就能明显感觉到快读和快输出的优势了
public static int nextInt() throws IOException {
sc.nextToken();
return (int) sc.nval;
}
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); public static StreamTokenizer sc = new StreamTokenizer(br); public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); public static PrintWriter print = new PrintWriter(bw);贴一份我的代码
package test;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Main {
public static void main(String[] args) throws IOException { int n = nextInt(); int m = nextInt(); int sum[][] = new int[n + 2][n + 2]; while (m-- > 0) { int x1 = nextInt(); int y1 = nextInt(); int x2 = nextInt(); int y2 = nextInt(); sum[x2 + 1][y2 + 1]++; sum[x2 + 1][y1]--; sum[x1][y2 + 1]--; sum[x1][y1]++; } for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) //将差分数组前缀和 sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { print.print((sum[i][j] + 10000) % 2 ); } print.println(); } print.flush(); } public static int nextInt() throws IOException { sc.nextToken(); return (int) sc.nval; } public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); public static StreamTokenizer sc = new StreamTokenizer(br); public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); public static PrintWriter print = new PrintWriter(bw);}
同款思路，就最后输出方式不同，我是直接输出的b[i][j]%2
#include[HTML_REMOVED]
using namespace std;
int main(){
int n,m;
cin>>n>>m;int arr[n+10][n+10]={0};
for(int i=1;i<=m;i){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
arr[x1][y1];arr[x2+1][y1]–;arr[x1][y2+1]–;arr[x2+1][y2+1];
}
for(int i=1;i<=n;i)
for(int j=1;j<=n;j){
arr[i][j]+=arr[i-1][j]+arr[i][j-1]-arr[i-1][j-1];
}
for(int i=1;i<=n;i)
for(int j=1;j<=n;j++){
if(arr[i][j]%2==0) cout<<0;
else cout<<1;
if(j==n) cout<<endl;
}
return 0;}
为什么我把arr[n+10][n+10]这样开辟空间答案就不一样
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
const int N = 2010;
int n, m, q;
int a[N][N], s[N][N];
int main()
{
cin >> n >> m;
while (m – )
{
int x1, y1, x2, y2;
scanf(“%d%d%d%d”, &x1, &y1, &x2, &y2);
a[x1][y1] ;
a[x1][y2 + 1] –;
a[x2 + 1][y1] –;
a[x2 + 1][y2 + 1] ;
}
for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) s[i][j] = a[i][j]+s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; for(int i = 1; i <= n; i ++) { for(int j = 1; j <= n; j ++) { if(a[i][j] % 2 == 0) printf("0"); else printf("1"); } puts(""); } return 0;}
为什么这样做不对呢
最后应该是s[i][j]吧，因为a数组是差分数组，而s才是前缀和数组
谢谢谢谢~
tql