蓝桥杯第十四届真题 棋盘 二维差分数组

题目

 小蓝拥有 n×n 大小的棋盘，一开始棋盘上全都是白子。

小蓝进行了 m 次操作，每次操作会将棋盘上某个范围内的所有棋子的颜色取反(也就是白色棋子变为黑色，黑色棋子变为白色)。

请输出所有操作做完后棋盘上每个棋子的颜色。

输入格式

输入的第一行包含两个整数 n,m，用一个空格分隔，表示棋盘大小与操作数。

接下来 m 行每行包含四个整数 x1,y1,x2,y2，相邻整数之间使用一个空格分隔，表示将在 x1 至 x2 行和 y1 至 y2列中的棋子颜色取反。

输出格式

输出 n 行，每行 n 个 00 或 11 表示该位置棋子的颜色。

如果是白色则输出 00，否则输出 11。

数据范围

对于 30%30% 的评测用例，1≤n,m≤500；
对于所有评测用例，1≤n,m≤2000，1≤x1≤x2≤n，1≤y1≤y2≤n。

输入样例：

3 3
1 1 2 2
2 2 3 3
1 1 3 3

输出样例：

001
010
100

思路和解题方法

1. 定义一个二维数组 b[N][N]，大小为 N * N，用于记录每个位置上数字的变化情况。

2. 输入两个整数 n 和 m，分别表示矩阵的大小和操作次数。

3. 进入一个循环，循环 m 次，每次输入一个矩形的左上角和右下角坐标。

4. 对应矩形区域内的四个顶点进行操作：

   • 左上角 (x1, y1)：在 b[x1][y1] 上加一。
   • 右上角 (x1, y2+1)：在 b[x1][y2+1] 上减一。
   • 左下角 (x2+1, y1)：在 b[x2+1][y1] 上减一。
   • 右下角 (x2+1, y2+1)：在 b[x2+1][y2+1] 上加一。

   这样就相当于对矩形区域内的所有元素加一，并对矩形区域的四个边界进行相应的减法操作。

5. 使用二重循环遍历整个矩阵，对每个位置进行更新。对于第 i 行和第 j 列的位置，根据二维差分数组的性质，可以通过以下公式计算当前位置的值：

   复制代码

   b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1]

   这样就得到了每个位置上的最终值。

6. 输出最终结果。对于每个位置 (i, j)，输出 b[i][j] 的奇偶性，即 (b[i][j] & 1)。

7. 循环结束，程序正常退出。

复杂度

        时间复杂度:

               O(N2)

        空间复杂度

               O(N2)

c++ 代码

#include<bits/stdc++.h>  // 包含常用的 C++ 标准库

using namespace std;

const int N = 2010;  // 定义常量 N 为 2010
int n,m;  // 定义变量 n 和 m
int b[N][N];  // 定义二维数组 b，大小为 N * N

int main()
{
    cin>>n>>m;  // 输入 n 和 m
    while(m--)  // 循环 m 次
    {
        int x1,y1,x2,y2;  // 定义矩形左上角和右下角的坐标
        cin>>x1>>y1>>x2>>y2;  // 输入矩形的坐标
        b[x1][y1]++;  // 对应位置加一
        b[x1][y2+1]--;  // 对应位置减一
        b[x2+1][y1]--;  // 对应位置减一
        b[x2+1][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];  // 更新当前位置的值
            cout<<(b[i][j]&1);  // 输出当前位置的奇偶性
        }
        puts(" ");  // 换行
    }
    
    return 0;  // 程序正常退出
}

觉得有用的话可以点点赞，支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。