本文共 2830 字，大约阅读时间需要 9 分钟。
题意：
给一个n*m的01矩阵，每次可以将一个0修改为1，求最大全0的矩阵。
分析：
将询问离线，从后往前处理询问，相当于每次将一个1变成0，答案是递增的。
用悬线法或者单调栈来求。
代码：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 using namespace std;12 typedef long long LL;13 14 inline int read() {15 int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;16 for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;17 }18 19 const int N = 2010;20 21 char a[N][N];22 int x[N], y[N], L[N], R[N], U[N][N], D[N][N], q1[N], q2[N], ans[N], sk[N];23 int Ans, n, m;24 25 void solve() {26 for (int i=1; i<=n; ++i) 27 for (int j=1; j<=m; ++j) 28 U[i][j] = a[i][j] == '.' ? U[i-1][j] + 1 : 0;29 for (int i=n; i>=1; --i) 30 for (int j=1; j<=m; ++j) 31 D[i][j] = a[i][j] == '.' ? D[i+1][j] + 1 : 0;32 for (int i=1; i<=n; ++i) { // 单调栈 33 U[i][0] = U[i][m+1] = -1;34 for (int top=0,j=1; j<=m+1; ++j) {35 while (top > 0 && U[i][j] < U[i][sk[top]]) R[sk[top]] = j, top--;36 sk[++top] = j;37 }38 for (int top=0,j=m; j>=0; --j) {39 while (top > 0 && U[i][j] < U[i][sk[top]]) L[sk[top]] = j, top --;40 sk[++top] = j;41 }42 for (int j=1; j<=m; ++j) 43 Ans = max(Ans, min(U[i][j], R[j] - L[j] - 1));44 }45 /*memset(R, 0x3f, sizeof(R)); // 悬线法 46 for (int i=1; i<=n; ++i) {47 int last = 0; 48 for (int j=1; j<=m; ++j) {49 if (a[i][j] == '.') L[j] = max(L[j], last + 1);50 else last = j, L[j] = 0;51 }52 last = m + 1;53 for (int j=m; j>=1; --j) {54 if (a[i][j] == '.') R[j] = min(R[j], last - 1);55 else last = j, R[j] = m + 1;56 }57 for (int j=1; j<=m; ++j) 58 Ans = max(Ans, min(U[i][j], R[j] - L[j] + 1));59 }*/60 }61 bool update(int x,int k) { // 判断能否组成k*k的方阵 62 int L1 = 1, R1 = 0, L2 = 1, R2 = 0;63 for (int j=1; j<=m; ++j) {64 while (L1 <= R1 && j - q1[L1] + 1 > k) L1 ++;65 while (L1 <= R1 && U[x][q1[R1]] >= U[x][j]) R1 --;66 q1[++R1] = j;67 68 while (L2 <= R2 && j - q2[L2] + 1 > k) L2 ++;69 while (L2 <= R2 && D[x][q2[R2]] >= D[x][j]) R2 --;70 q2[++R2] = j;71 72 if (j >= k && U[x][q1[L1]] + D[x][q2[L2]] - 1 >= k) {73 Ans = k;74 return true;75 }76 }77 return false;78 }79 void Change(int x,int y) {80 a[x][y] = '.';81 for (int i=x; i<=n; ++i) U[i][y] = a[i][y] == '.' ? U[i-1][y] + 1 : 0;82 for (int i=x; i>=1; --i) D[i][y] = a[i][y] == '.' ? D[i+1][y] + 1 : 0;83 }84 int main() {85 n = read(), m = read(); int Q = read();86 for (int i=1; i<=n; ++i) scanf("%s",a[i]+1);87 for (int i=1; i<=Q; ++i) {88 x[i] = read(),y[i] = read();89 a[x[i]][y[i]] = 'X';90 }91 solve();92 for (int i=Q; i>=1; --i) {93 ans[i] = Ans;94 Change(x[i], y[i]);95 while (update(x[i], Ans + 1));96 }97 for (int i=1; i<=Q; ++i) printf("%d\n",ans[i]);98 return 0;99 }
转载于:https://www.cnblogs.com/mjtcn/p/9606571.html