标签:二维差分

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

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

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

输入格式

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

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

输出格式

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

如果是白色则输出 0，否则输出 1。

数据范围

对于 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

 讲讲思路:

一开始想直接暴力,很显然,我是失败了

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2010;
int m , n;
int x1 , y1 , x2 , y2;
int qp[N][N];

int main()
{
    cin >> n >> m;
    memset(qp, 0, sizeof qp);
    for (int i = 0; i < m; i ++ )
    {
        cin >> x1 >> y1 >> x2 >> y2;
        for (int k = x1 - 1; k < x2; k ++ )
            for (int j = y1 - 1; j < y2; j ++ )
                if(qp[k][j] == 0) qp[k][j] = 1;
                else qp[k][j] = 0;
    }
    
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < n; j ++ )
            cout << qp[i][j];
        cout << endl;
    }
        
    
    return 0;
}

​

那有什么算法吗?有,没错,他就是二维差分

对于读入的x1,x2,y1,y2确定四个角,分别进行加减

 最后用二维前缀和,然后判断奇偶.

以下是AC代码:

/* 果然暴力做不了捏 */
/* 二维想着想着就想到了差分 */

#include <iostream>
#include <cstring>
#include <algorithm>

/* 定义 */
using namespace std;
typedef long long LL;
const int N = 2024;
int m , n;
LL a[N][N], b[N][N];
int x1 , y1 , x2 , y2;

/* 二维差分 */
void insert(int x1, int y1, int x2, int y2, int c) // c可以用1替代,这里只是通用格式
{
    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;
    for (int i = 1; i <= m; i++)
    {
        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) b[i][j] = 0; // 直接改0 1
            else b[i][j] = 1;
        }
    }
    
    /* 输出 */
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cout << b[i][j];
        }
        cout << endl;
    }
    return 0;
}

​