P3684

Forever1507 · 2022-10-14 17:08:26 · 题解

大杂烩好题 (bushi

首先，每个格子为中心的正方形的最大边长可以提前二位前缀和出井号的数量然后二分求出。

然后因为要是最小答案最大，这里排除二分（反正这个 check 我除了 bfs 就不会了）后可以考虑最大生成树以实现最大的目的。至于建边，就是一个点向上下左右不是障碍物的建边了，边权应当是两个点的最大边长（点 i 的最大正方形边长记为 d_i）。

注意一点，这个生成树可能是森林，要分别 LCA。

树上求简单路径我选择倍增，具体就是在 LCA 里面多维护一个 dis[i][j] 表示 点 i 向上走 2^j 步能够取到的最小边长。

初始值显然就是 dp[cur][0]=min(d[cur],d[fa/*父亲节点*/])，在 LCA 的时候一起维护即可。

码量较大，代码如下：

#include<bits/stdc++.h>
using namespace std;
int n;
char mp[1005][1005];
int sum[1005][1005],d[1005][1005];
int q;
bool check(int x,int y,int r){
    if(r>=x||r>=y||r+x>n||r+y>n)return 0;
    if(sum[x+r][y+r]-sum[x-r-1][y+r]-sum[x+r][y-r-1]+sum[x-r-1][y-r-1]>=1)return 0;
//  cout<<"Check: "<<x<<' '<<y<<' '<<r<<'\n';
    return 1;
}
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int tot;
int calc(int x,int y){
    return (x-1)*n+y;
}
int X(int x){
    return (x-1)/n+1;
}
int Y(int x){
    return (x%n==0)?n:x%n;
}//以上三个函数实现了坐标与编号的互换 
struct node{
    int u,v,w;
}e[4000005];
int fa[1000005];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void unionn(int x,int y){
    int a=find(x),b=find(y);
    if(a!=b)fa[a]=b;
    return;
}
bool cmp(node a,node b){
    return a.w>b.w;
}
int _d[1000005],dp[1000005][21],dis[1000005][21];
vector<node>nbr[1000005];
void before(int cur,int fa){
    _d[cur]=_d[fa]+1;
    dp[cur][0]=fa;
    dis[cur][0]=min(d[X(cur)][Y(cur)],d[X(fa)][Y(fa)]); 
    for(int i=1;i<=20;++i)dp[cur][i]=dp[dp[cur][i-1]][i-1],dis[cur][i]=min(dis[cur][i-1],dis[dp[cur][i-1]][i-1]);
    for(int i=0;i<nbr[cur].size();++i){
        node to=nbr[cur][i];
        if(fa==to.v)continue;
//      dis[to.v][0]=to.w;
        before(to.v,cur);
    }
    return;
}
int LCA(int u,int v){
    int lens=d[X(u)][Y(u)],_lens=d[X(v)][Y(v)];
    if(_d[u]>_d[v])swap(u,v);
    for(int i=20;i>=0;i--){
        if((1<<i)<=_d[v]-_d[u])_lens=min(_lens,dis[v][i]),v=dp[v][i];
    }
    if(u==v)return min(lens,_lens);
    for(int i=20;i>=0;i--){
        if(dp[u][i]!=dp[v][i]){
            lens=min(lens,dis[u][i]);
            _lens=min(_lens,dis[v][i]);//一定要先维护距离，不然u/v的值就改了 
            u=dp[u][i];
            v=dp[v][i];
        }
    }
    return min(lens,_lens);
}
void MST(){
    for(int i=1;i<=n*n;++i)fa[i]=i;
    sort(e+1,e+tot+1,cmp);
    for(int i=1;i<=tot;++i){
        int x=e[i].u,y=e[i].v;
        if(find(x)==find(y))continue;
        nbr[x].push_back({x,y,e[i].w});
        nbr[y].push_back({y,x,e[i].w});
//      cout<<"W: "<<x<<' '<<y<<' '<<X(x)<<' '<<Y(x)<<' '<<X(y)<<' '<<Y(y)<<' '<<e[i].w<<'\n';
//      cout<<x<<' '
        unionn(x,y);
    }
    return;
}
int main(){
    memset(dis,0x3f,sizeof(dis));
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cin>>mp[i][j];
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
            if(mp[i][j]=='#')sum[i][j]++;       
            //二位前缀和 
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            int lt=-1,rt=n/2;
            while(lt+1<rt){
                int mid=lt+rt>>1;
                if(check(i,j,mid))lt=mid;
                else rt=mid;
            }
            d[i][j]=2*lt+1;//懒得保证奇数了，只二分一半的距离 
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            for(int k=0;k<=3;++k){
                int x=i+dx[k],y=j+dy[k];
                if(x>=1&&y>=1&&x<=n&&y<=n&&mp[x][y]=='.'&&mp[i][j]=='.'){
                    e[++tot]={calc(i,j),calc(x,y),min(d[i][j],d[x][y])};
                }
            }
        }
    }
    MST();
    for(int i=1;i<=n*n;++i)if(!_d[i]&&mp[X(i)][Y(i)]=='.')before(i,0);//可能是森林！ 
    cin>>q;
    for(int i=1;i<=q;++i){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        if(find(calc(x1,y1))!=find(calc(x2,y2))){
            cout<<0<<'\n';//可能不连通，判无解 
            continue;
        }
        cout<<LCA(calc(x1,y1),calc(x2,y2))<<'\n';
    }
    return 0;
}