题目描述

http://codeforces.com/contest/480/problem/E

做法

首先加入所有询问坐标，求出答案。
初始答案很好求，你可以设f[i,j]表示以(i,j)为左下角的最大正方形边长。
那么 f[i,j]=min(f[i−1,j],f[i,j+1])(+1) 后面是否+1要判断右上角。
当然左下角是障碍f[i,j]=0。
接下来来考虑时间倒流。
首先我们维护left和right表示每个位置可以往左往右延伸多长。
时间倒流后，相当于删除障碍，答案一定是递增的。
删除一个障碍只需要暴力更改这一行的left和right。
接下来我们不断判断是否存在ans+1（ans是当前答案）边长的正方形，存在将ans+1，继续做。
容易得知这个正方形一定跨过障碍所在列。
于是可以单调队列，得到障碍所在列每一个长度为ans+1的区间，向左向右能延伸多长，如果加起来达到ans+1，则判定成功。
复杂度是n^2。

#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
const int maxn=2000+10;
int f[maxn][maxn],left[maxn][maxn],right[maxn][maxn];
int ans[maxn],b[maxn],dl[maxn],ask[maxn][2];
int pd[maxn][maxn];
int i,j,k,l,t,n,m,q,head,tail,now,x,y;
int read(){

int x=0,f=1;

char ch=getchar();

while (ch<'0'||ch>'9'){

if (ch=='-') f=-1;

ch=getchar();

}

while (ch>='0'&&ch<='9'){

x=x*10+ch-'0';

ch=getchar();

}

return x*f;
}
char get(){

char ch=getchar();

while (ch!='.'&&ch!='X') ch=getchar();

return ch;
}
bool check(int ans){

int i,j,k;

head=1;tail=0;

fo(i,1,n){

while (head<=tail&&left[dl[tail]][y]>=left[i][y]) tail--;

dl[++tail]=i;

while (dl[head]<=i-ans) head++;

b[i]=left[dl[head]][y];

}

head=1;tail=0;

fo(i,1,n){

while (head<=tail&&right[dl[tail]][y]>=right[i][y]) tail--;

dl[++tail]=i;

while (dl[head]<=i-ans) head++;

b[i]+=right[dl[head]][y]-1;

}

fo(i,1,n)

if (i>=ans&&b[i]>=ans) return 1;

return 0;
}
int main(){

scanf("%d%d%d",&n,&m,&q);

fo(i,1,n)

fo(j,1,m)

if (get()=='X') pd[i][j]++;

fo(i,1,q){

ask[i][0]=read();ask[i][1]=read();

pd[ask[i][0]][ask[i][1]]++;

}

fo(i,1,n)

fd(j,m,1){

if (pd[i][j]) continue;

if (i==1||j==m){

f[i][j]=1;

now=max(now,f[i][j]);

continue;

}

f[i][j]=min(f[i-1][j],f[i][j+1]);

if (!pd[i-f[i][j]][j+f[i][j]]) f[i][j]++;

now=max(now,f[i][j]);

}

fo(i,1,n)

fo(j,1,m)

if (pd[i][j]) left[i][j]=0;else left[i][j]=left[i][j-1]+1;

fo(i,1,n)

fd(j,m,1)

if (pd[i][j]) right[i][j]=0;else right[i][j]=right[i][j+1]+1;

fd(i,q-1,1){

ans[i+1]=now;

x=ask[i+1][0];y=ask[i+1][1];

pd[x][y]--;

fo(j,1,m)

if (pd[x][j]) left[x][j]=0;else left[x][j]=left[x][j-1]+1;

fd(j,m,1)

if (pd[x][j]) right[x][j]=0;else right[x][j]=right[x][j+1]+1;

while (check(now+1)) now++;

}

ans[1]=now;

fo(i,1,q) printf("%dn",ans[i]);
}

最后

以上就是苗条煎蛋为你收集整理的[CF480E]Parking Lot题目描述做法的全部内容，希望文章能够帮你解决[CF480E]Parking Lot题目描述做法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。