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

题目

��小蓝拥有 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 31 1 2 22 2 3 31 1 3 3

输出样例：

001010100

难度：简单

时/空限制：2s / 64MB

---

思路和解题方法

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  // 包含常用的 C++ 标准库using namespace std;const int N = 2010;  // 定义常量 N 为 2010int n,m;  // 定义变量 n 和 mint b[N][N];  // 定义二维数组 b，大小为 N * Nint 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