首页 / 更多教程 / codeforces480E Parking Lot

codeforces480E Parking Lot

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了codeforces480E Parking Lot，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1592字，纯文字阅读大概需要3分钟。

内容图文

题目大意：给一个点阵，其中有的地方没有点，操作是去掉某个点，并询问当前点阵中最大的正方形

若没有修改的话，裸dp

加上修改，可以考虑时光倒流，这样答案就是递增的

可以用并查集维护点的连通性，O^2的

技术分享 技术分享 
#include<bits/stdc++.h>
usingnamespace std;
#define maxn 2010
inline void MIN(int &a,int b){if(a>b)a=b;}
inline void MAX(int &a,int b){if(a<b)a=b;}
int n,m,q,sz;
int f[maxn][maxn],u[maxn][maxn],lg[maxn],rg[maxn],qx[maxn],qy[maxn],ans[maxn];
char s[maxn][maxn];
struct line{
    int f[maxn];
    int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
}l[maxn],r[maxn];
void del(int x,int y){
    l[x].f[y]=l[x].find(y-1);
    r[x].f[y]=r[x].find(y+1);
}
int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m+1;++j){
            l[i].f[j]=j;
            r[i].f[j]=j;
            u[i][j]=i;
        }
    for(int i=1;i<=n;++i)scanf("%s",s[i]+1);
    for(int i=1;i<=q;++i)scanf("%d%d",&qx[i],&qy[i]),s[qx[i]][qy[i]]=‘X‘;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(s[i][j]==‘.‘)
                del(i,j);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(s[i][j]==‘.‘){
                u[i][j]=u[i-1][j];
                f[i][j]=min(f[i-1][j-1]+1,min(i-u[i][j],j-l[i].find(j)));
                MAX(sz,f[i][j]);
            }
    for(int v=q;v;--v){
        ans[v]=sz;
        del(qx[v],qy[v]);
        for(int i=1;i<=n;++i){
            lg[i]=qy[v]-l[i].find(qy[v]);
            rg[i]=r[i].find(qy[v])-qy[v];
        }
        for(int i=qx[v]-1;i>=1;--i)MIN(lg[i],lg[i+1]),MIN(rg[i],rg[i+1]);
        for(int i=qx[v]+1;i<=n;++i)MIN(lg[i],lg[i-1]),MIN(rg[i],rg[i-1]);
        for(int i=1;i<=qx[v];++i)
            while(i+sz<=n&&min(rg[i],rg[i+sz])+min(lg[i],lg[i+sz])-1>sz)
                ++sz;
    }
    for(int i=1;i<=q;++i)
        printf("%d\n",ans[i]);
    return0;
}
View Code

 

原文：http://www.cnblogs.com/117208-/p/5342950.html

内容总结

以上是互联网集市为您收集整理的codeforces480E Parking Lot全部内容，希望文章能够帮你解决codeforces480E Parking Lot所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1217232.html

来源：【匿名】