题解 P7274 草地

· · 题解

Orz EA!

首先你发现，向上流和向下流实际上是一样的，左右同理，并且操作顺序是没有关系的，所以一定存在一种最优策略是下移 A 次后右移 B 次，此时一个点会向右向下延伸出一个 (A+1) \times (B+1) 的矩形。

考虑两个黑点 (x,y) \to (x',y') 啥时候能联通（不妨 x<x', y<y'），那就是 A \ge x'-x-1，B \ge y'-y-1 的时候。最暴力的想法是，把两黑点间连一条权值为二元组 (x'-x-1,y'-y-1) 的边，那我们就要求的是 \max x + \max y 的 MST。

一种求法是枚举 \max x 然后计算 \max y 的最小值。具体而言，将所有 M 条边按照 x 从小到大排序，逐条加入进来，同时 LCT 维护 y 这维的 MST，可以 O(M \log n)。当然也可以 O(M \log^2 M) 整体二分，比较好写。

黑点数较多时 M 可以到 O(n^2m^2) 的级别，但其实有很多边是不需要的：以两个黑点 p,q 为对角的矩形内，如果还存在其他黑点，则这条边就不需要了，因为可以由这两条较短的边“拼合”起来得到。这样连边的话，显然同一行内的点连出的边是 O(m) 级别，故总边数是 O(nm) 级别的。套用上面求 MST 的做法，我们就以 O(nm \log nm) 的复杂度解决了这道题。

可能会卡常，但显而易见这个 O(nm) 的边数很难卡到很满。有一个有力的剪枝：一开始存在于一个连通块的黑点可以直接缩起来。

这份代码是 O(nm \log n \log m) 的整体二分，可以比较快跑过去。

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a,i##i=b;i<=i##i;++i)
#define ROF(i,a,b) for(int i=a,i##i=b;i>=i##i;--i)
using namespace std;
const int N=1e3+7,M=3*N*N;
int n,m,C=1,lm,ct[M],T,ans[N],h[N],id[N],res=M,X[N],Y[N],g;
char s[N];
struct mem{int t,p,v;};
struct unf{
    int a[M],C=0;mem f[M];
    int& operator[](int x){return a[x];}
    void st(int x,int v){f[++C]={T,x,a[x]},a[x]=v;}
    void rbk(int t){for(;C&&f[C].t>=t;--C)a[f[C].p]=f[C].v;}
}fa,rk;
int rbk(int t){return fa.rbk(t),rk.rbk(t),T=t-1;}
int fd(int x){return fa[x]==x?x:fd(fa[x]);}
int merge(int x,int y){
    x=fd(x),y=fd(y);
    if(x!=y){
        if(rk[x]<rk[y])swap(x,y);
        ct[T+1]=ct[T]-1,++T,fa.st(y,x);
        if(rk[x]==rk[y])rk.st(x,rk[x]+1);
    }
    return ct[T]==1;
}
struct edge{
    int u,v,x,y;
    void mtn(){
        u=fd(u),v=fd(v);
        if(u==v)x=m+1,y=n+1;
    }
    int add(int o){return x<=o?merge(u,v):0;}
}x[M],y[M];
void solve(int l,int r,int L,int R){
    if(L==R)FOR(i,l,r)ans[i]=L;
    if(l>r||L>R)return;
    int d=(l+r)/2,G,t=T+1,p=R;
    FOR(i,X[l],X[d+1]-1)if(x[i].y<L)x[i].add(M);
    G=T+1;
    FOR(i,Y[L],Y[R+1]-1)if(y[i].add(d)){p=y[i].y;break;}
    ans[d]=p,rbk(G),solve(d+1,r,L,p),rbk(t);
    FOR(i,Y[L],Y[p]-1)y[i].add(l-1);
    solve(l,d-1,p,R);
}
void link(int i,int j){
    if(id[i]&&id[j])++C,x[C]=y[C]={id[i],id[j],max(j-i-1,0),max(abs(h[j]-h[i])-1,0)};
}
signed main(){
    scanf("%d%d",&n,&m),lm=max(n,m);
    FOR(i,1,n){
        scanf("%s",s+1),s[m+1]='1';
        int w=1;
        FOR(j,1,m)if(s[j]=='1'){
            if(id[j])++C,x[C]=y[C]={ct[0]+1,id[j],0,i-h[j]-1};
            g=h[j],id[j]=++ct[0],h[j]=i;
            for(int p=j-1,k=g;p>=w;--p)if(h[p]>k)k=h[p],link(p,j);
            for(int p=j+1,k=g;s[p]<'1';++p)if(h[p]>k)k=h[p],link(j,p);
            w=j;
        }
    }
    FOR(i,1,ct[0])fa[i]=i;
    FOR(i,1,C)if(!x[i].y)x[i].add(0);
    FOR(i,1,C)x[i].mtn(),y[i].mtn();
    sort(x+1,x+C+1,[](edge a,edge b){return a.x<b.x;});
    sort(y+1,y+C+1,[](edge a,edge b){return a.y<b.y;});
    while(x[C-1].y>n)--C;
    ROF(i,C,1)X[x[i].x]=Y[y[i].y]=i;
    ROF(i,m,1)if(!X[i])X[i]=X[i+1];
    ROF(i,n,1)if(!Y[i])Y[i]=Y[i+1];
    Y[n+2]=C+1,X[m+2]=C+1,solve(0,m,0,n+1);
    FOR(i,0,m)if(ans[i]<=n)res=min(res,i+ans[i]);
    printf("%d",res);
    return 0;
}