AcWing 5396. 棋盘（二维差分）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 5396. 棋盘（二维差分）原题链接简单

作者：

Pedestrian , 2024-01-15 21:01:40 , 所有人可见 , 阅读 2878

27

3

2024寒假每日一题全部题解传送门>>

可以发现棋子的颜色取决于棋子的操作次数。如果操作次数为奇数，棋子颜色就是黑色，否则就是白色，故只需计算出每个棋子被操作的次数即可。由于每次是对二维矩阵某个范围进行操作（相当于对每个位置加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;
}

10 评论

努力的zero天赋 10个月前

必须给我大哥狠狠支持上去，我大哥题解写得基本非常好，大家可以参考这位大哥的。

徐义博 10个月前

#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
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

acwing_907271 7个月前

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();
    }



}

}

为什么我写完时间还是超的

痛太痛了 7个月前

Scanner和System.out是很慢的,上网搜一下快读和快输出就能过了,当输入和输出超过 1万的时候就能明显感觉到快读和快输出的优势了

痛太痛了 7个月前

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);

痛太痛了 7个月前

贴一份我的代码
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);

}

厄斐琉斯 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;

}
为什么这样做不对呢

Pedestrian 10个月前

最后应该是$s[i][j]%2$吧，因为$a$数组是差分数组，而$s$才是前缀和数组

厄斐琉斯 10个月前回复了 Pedestrian 的评论

谢谢谢谢~

努力的zero天赋 10个月前

tql

App 内打开