Day5 备战CCF-CSP练习

题目分析

暴力/二维前缀和
暴力就不说了，讲一下优化

二位前缀和，我们将矩形中每一个点都当成前缀和的点，那么，我们只需要将顶点标注一下，就可以利用前缀和的性质画出整个矩形

如图一，蓝色是要画的目标矩形

那么怎么构建差分数组呢
根据前缀和公式f[i][j] = f[i][j - 1] + f[i - 1][j] - f[i - 1][j - 1] + a[i][j]
其中f[i][j - 1] + f[i - 1][j] - f[i - 1][j - 1]都是以\((i , j)\)为最右下的顶点的矩形面积（差分数组的矩形），问题是我们怎么通过控制顶点的a[i][j]来控制矩阵的大小。

红色点是矩形的左上角，在此之前的所有点都为\(0\)，那么前缀和自然也为\(0\)，那么a[x1][y1] = 1，到了橘色点，矩形已经结束了，可是前缀和依然为\(1\)，因此a[x2 + 1][y1] = -1，同理另一个橘色点a[x1][y2 + 1] = -1 ，到了紫色点，由于两个橘色点，紫色点的前缀和为\(-1\)，所以a[x2 + 1][y2 + 1] = 1

然后推广就可以了，利用前缀和性质，只要不是\(0\)的点就是覆盖的点，求面积即可

构造差分数组 \(\rightarrow\) 前缀和构建矩形 \(\rightarrow\) 再次前缀和求覆盖面积

C++ 代码

#include <bits/stdc++.h>using namespace std;
const int N = 110;int f[N][N];
int n;int main()
{cin >> n;while (n -- ){int a , b , x , y;cin >> a >> b >> x >> y;a ++ , b ++ ;f[a][b] += 1;f[x + 1][b] -= 1 , f[a][y + 1] -= 1;f[x + 1][y + 1] += 1;}for(int i = 1 ; i < N ; i ++)for(int j = 1 ; j < N ; j ++)f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];for(int i = 1 ; i < N ; i ++)for(int j = 1 ; j < N ; j ++){if(f[i][j]) f[i][j] = 1;f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];}    cout << f[N - 1][N - 1];        }