这题卡常，可以通过 111

Acerkaio · 2025-08-08 18:05:44 · 题解

我们先写一个 O(2^{n^2}) 的顺序填写的暴力搜索，发现跑的非常慢。

然后我们考虑使用可撤销并查集快速维护联通块数量，我们按秩合并将并查集复杂度看成 O(1)，这样判断合法就是 O(1) 的。

然后我们剪枝，考虑发现你每填一个点那么联通块的数量至多减少一，这启发我们判断若联通块的数量大于剩下未填的点的数量加二就可以直接退出了（因为最后要求剩下两个连通块）。

实测最大点 2.83s。

#include<bits/stdc++.h>
#define ll long long
#define reg register
#define rep(i,a,b) for(reg int i=a;i<=b;++i)
#define drep(i,a,b) for(reg int i=a;i>=b;--i)
#define pb push_back
#define ins insert
#define il inline
#define rint reg int
using namespace std;
int n,k,res,sum,tot;
int fa[65],sz[65];
bitset<10>a[10],b[10],vis[10];
int dir[4][2]{{1,0},{-1,0},{0,1},{0,-1}};
int ltk=0;
il int find(rint x){
    if(fa[x]==x)return x;
    return find(fa[x]);
}
stack<tuple<int,int,int>>stk;
il bool merge(rint x,rint y){
    rint X=find(x),Y=find(y);
    if(X==Y)return 0;
    ltk--;
    if(sz[X]>sz[Y])swap(X,Y);
    fa[X]=Y;
    stk.push({X,Y,sz[Y]});
    sz[Y]+=sz[X];
    return 1;
}
il void poop(){
    // cerr<<stk.size()<<'\n';
    auto &[X,Y,SZ]=stk.top();
    stk.pop();++ltk;
    fa[X]=X,sz[Y]=SZ;
}
il int val(rint x,rint y){
    return (x-1)*n+y;
}
il bool check(){
    return (sum+ltk)==2;
}
il void dfs(rint x,rint y){
    if((sum+ltk)>(k-sum)+2)return ;
    if(sum==k){res+=check();return;}
    if(y>n)return;
    if(x>n){dfs(1,y+1);return;}
    if(a[x][y]){
        b[x][y]=1;
        rint cnt=0;
        if(y!=1&&a[x][y-1]&&b[x][y-1]){
            cnt+=merge(val(x,y),val(x,y-1));
        }
        if(x!=1&&a[x-1][y]&&b[x-1][y]){
            cnt+=merge(val(x,y),val(x-1,y));
        }
        sum++;
        dfs(x+1,y);
        rep(i,1,cnt)poop();
        sum--;
        b[x][y]=0;
    }
    dfs(x+1,y);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    rep(i,1,64)fa[i]=i,sz[i]=1;
    rint sudssm=0;
    rep(i,1,n)rep(j,1,n){char c;cin>>c;a[i][j]=(c=='.');sudssm+=a[i][j];}

    dfs(1,1);cout<<res<<'\n';
    return 0;
}