Arson In Berland Forest【Codeforces 1262 E】【二维差分 + 二分答案】

Codeforces Round #602 (Div. 2, based on Technocup 2020 Elimination Round 3) E

这道E题当真是HACK了不少人，先讲一下题意吧。

  有一个N*M的矩形，里面放了‘ X ’和‘ . ’两种类型的东西，我们想要用最大的' X '阵来覆盖完整个矩阵的' X '，问最大阵的变长是多少，并且这个最大阵可以看成是从一个点向外延伸多少次，且必须被看成是一个点向外延伸多少次，问的是最多的延伸次数，也就是（变成 - 1）/2。

  然后，一开始的时候呢，偷懒了，想了个（很容易被HACK，但还是敢交）先去求图中最小的最大阵的宽度或长度来先确定边长，然后就是直接构造，这样的方法（可以假装AC）

代码也在后面会给出来。

  现在啊，该说一下正解了，正解就是一个二分答案再加上二维差分，我们知道一维直线上的差分就是，我们要给一段区间[l, r]都加上1，我们可以在l这个位置上+1，在r+1这个位置上-1，然后做一个前缀和就可以了，那么对于二维平面，我们该有怎样的做法了呢？

  一样是用到了二维前缀和的思想。（这就是二维前缀和的思想了。）

  然后，我们可以去二分答案这个向外的延伸次数，我们就可以去对它进行check了。把所有覆盖了一整块面积的，都做这样的操作，假设（x，y），现在是（x - lim, y - lim）和（x + lim, y + lim）这样的矩形，我们对（x - lim, y - lim）这个点上+1，对（x - lim, y + lim + 1）这个点-1，对（x + lim + 1, y - lim）这个点-1，对（x + lim + 1, y + lim + 1）这个点进行+1，这样就能保证经过二维前缀和之后的答案就是覆盖次数了，那么，假如这个点是一个'X'点，但是呢却没有被覆盖，很显然，这里的二分答案就偏大了。

正解Ac——Code

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e6 + 7;
int N, M;
vector<int> mp[maxN], t[maxN];
vector<bool> X[maxN];
char s[maxN];
int Area(int lx, int ly, int rx, int ry) { return mp[rx][ry] - mp[lx - 1][ry] - mp[rx][ly - 1] + mp[lx - 1][ly - 1]; }
inline bool In_map(int x, int y) { return x >= 1 && y >= 1 && x <= N && y <= M; }
inline bool check(int lim)
{for(int i=0; i<=N + 1; i++) t[i].clear();for(int i=0; i<=M + 1; i++) t[0].push_back(0);for(int i=1; i<=N + 1; i++) for(int j=0; j<=M + 1; j++) t[i].push_back(0);int SS = (2 * lim + 1) * (2 * lim + 1);for(int i = lim + 1, x1, y1, x2, y2; i + lim<=N; i++){for(int j = lim + 1; j + lim<=M; j++){x1 = i - lim; y1 = j - lim; x2 = i + lim; y2 = j + lim;if(In_map(x1, y1) && In_map(x2, y2) && Area(x1, y1, x2, y2) == SS){t[x1][y1]++; t[x1][y2 + 1]--; t[x2 + 1][y1]--; t[x2 + 1][y2 + 1]++;}}}for(int x=1; x<=N; x++){for(int y=1; y<=M; y++){t[x][y] = t[x][y] + t[x - 1][y] + t[x][y - 1] - t[x - 1][y - 1];if(X[x][y] && !t[x][y]) return false;}}return true;
}
int main()
{scanf("%d%d", &N, &M);for(int i=0; i<=M; i++) { mp[0].push_back(0); mp[N + 1].push_back(0); }for(int i=1, val; i<=N; i++){mp[i].push_back(0);X[i].push_back(false);scanf("%s", s + 1);for(int j=1; j<=M; j++){val = mp[i - 1][j] + mp[i][j - 1] - mp[i - 1][j - 1];if(s[j] == 'X'){val++;X[i].push_back(true);}else X[i].push_back(false);mp[i].push_back(val);}}int l = 0, r = min(N, M), mid, ans = 0;while(l <= r){mid = (l + r) >> 1;if(check(mid)){l = mid + 1;ans = mid;}else r = mid - 1;}printf("%d\n", ans);int SS = (2 * ans + 1) * (2 * ans + 1);for(int i=1; i<=N; i++){for(int j=1; j<=M; j++){if(X[i][j] && In_map(i - ans, j - ans) && In_map(i + ans, j + ans) && Area(i - ans, j - ans, i + ans, j + ans) == SS) printf("X");else printf(".");}puts("");}return 0;
}
/*
2 2
XX
XX
*/

错误的但是也可以作为参考的解：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e6 + 7;
int N, M;
vector<int> mp[maxN];
vector<bool> X[maxN];
char s[maxN];
int Area(int lx, int ly, int rx, int ry) { return mp[rx][ry] - mp[lx - 1][ry] - mp[rx][ly - 1] + mp[lx - 1][ly - 1]; }
inline bool check(int x, int y) { return x >= 0 && y >= 0 && x <= N && y <= M; }
int main()
{scanf("%d%d", &N, &M);for(int i=0; i<=M; i++) { mp[0].push_back(0); mp[N + 1].push_back(0); }for(int i=1, val; i<=N; i++){mp[i].push_back(0);X[i].push_back(false);scanf("%s", s + 1);for(int j=1; j<=M; j++){val = mp[i - 1][j] + mp[i][j - 1] - mp[i - 1][j - 1];if(s[j] == 'X'){val++;X[i].push_back(true);}else X[i].push_back(false);mp[i].push_back(val);}}int ans = min(N, M), now = 0;for(int i=1; i<=N; i++){now = 0;for(int j=1; j<=M; j++){if(X[i][j]) now++;else if(now) { ans = min(ans, now); now = 0; }}if(now) ans = min(ans, now);}for(int j=1; j<=M; j++){now = 0;for(int i=1; i<=N; i++){if(X[i][j]) now++;else if(now) { ans = min(ans, now); now = 0; }}if(now) ans = min(ans, now);}ans = (ans - 1) / 2;int SS = (2 * ans + 1) * (2 * ans + 1);printf("%d\n", ans);for(int i=1; i<=N; i++){for(int j=1; j<=M; j++){if(!X[i][j]) { printf("."); continue; }if(check(i - ans - 1, j - ans - 1) && check(i + ans, j + ans) && Area(i - ans, j - ans, i + ans, j + ans) == SS) printf("X");else printf(".");}puts("");}return 0;
}
/*
2 2
XX
XX
*/