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
*/