P12660题解

· · 题解

前情：打了三天， A 掉心情激昂，遂写题解。

P12260 题解

很好的题，使我大脑成为根节点。

题意

要你在一个 n 行 n 列的方格中放 k 个格子（有的能放有的不能），使其恰好形成两个连通块，求方案数。

解题

发现 n 和 k 都很小，猜测是状压。

想先要维护什么：

一行一行来看，可以分成不能拓展的连通块和还能再拓展的，要考虑当前放了几个，还要考虑当前行的状态。

考虑怎么转移到下一行时，发现有点难，因为只看当前行状态的话，有可能看上去是分开的，实际上在同一连通块内。

怎么办呢，你考虑抛弃传统的二进制状态，把每一位处于哪一个连通块压进去，这样子就好办了，枚举完下一行的状态时，就可以建图得出联通状态，计算一下不能再往下拓展的，就好办了。

但是有一个很大的雷需要避开，就是不要以为当前可以拓展的连通块最多只有 2 个，他们后面可能会合并起来（我就因为这个想了很久）。

代码

本人实现冗长，马蜂丑陋，客观地喷。

#include <bits/stdc++.h>
#define infile(s) freopen(#s".in","r",stdin)
#define outfile(s) freopen(#s".out","w",stdout)
#define fre(s) freopen(#s".in","r",stdin);freopen(#s".out","w",stdout)
#define ll long long
using namespace std;
template<typename T> bool read (T& x)
{
    x=0;
    T w=1;
    char ch=getchar();
    if(ch==EOF)return 0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')w=-w;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    if(w==-1)x=-x;
    return 1;
}
template<typename T, typename... Args> void read(T& x,Args& ...args)
{
    read(x);
    read(args...);
}
const int N=9;
const int M=400000;
int n,k;
char s[N][N];
int f[2][N][3][M];
int tot[1<<N];
int has[M];
int fa[3*N];
int p[N]{1};
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
bitset<M>vis[N][N][3];
vector<int>v[N][N][3];
int main()
{
    read(n,k);
    for(int i=1;i<=n;i++)
    {
        p[i]=p[i-1]*5;
    }
    int zt=pow(5,n)-1;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s[i]+1);
    }
    for(int i=0;i<=(1<<n)-1;i++)
    {
        if(i)tot[i]=tot[i^(i&-i)]+1;
    }
    f[0][0][0][0]=1;
    v[0][0][0].push_back(0);
    for(int i=1;i<=n;i++)
    {
        for(int use=0;use<=k;use++)
        {
            for(int sum=0;sum<=2;sum++)
            {
                for(auto lst:v[i-1][use][sum])
                {
                    for(int j=0;j<=(1<<n)-1;j++)
                    {
                        if(use+tot[j]>k)continue;
                        int bj=0;
                        for(int ii=1;ii<=n;ii++)
                        {
                            if((j&(1<<(ii-1)))&&s[i][ii]=='#'){bj=1;break;}
                        }
                        if(bj)continue;
                        for(int ii=1;ii<=2*n+4;ii++)
                        {
                            fa[ii]=ii;
                        }
                        int now[9];
                        now[0]=0;
                        for(int ii=1;ii<=n;ii++)
                        {
                            now[ii]=(lst%p[ii])/p[ii-1];
                            if(now[ii])fa[ii]=2*n+now[ii];
                        }
                        for(int ii=1;ii<=n;ii++)
                        {
                            if(j&(1<<ii-1)&&now[ii])
                            {
                                int fx=find(ii),fy=find(ii+n);
                                if(fx!=fy)fa[fy]=fx;
                            }
                            if(j&(1<<ii-1)&&(ii!=1&&j&(1<<ii-2)))
                            {
                                int fx=find(ii+n),fy=find(ii+n-1);
                                if(fx!=fy)fa[fy]=fx;
                            }
                            if(now[ii]&&now[ii-1])
                            {
                                int fx=find(ii),fy=find(ii-1);
                                if(fx!=fy)fa[fy]=fx;
                            }
                        }
                        vector<int>of[2*n+5];
                        for(int ii=1;ii<=2*n;ii++)
                        {
                            if(ii<=n&&now[ii]==0)continue;
                            if(ii>n&&!(j&(1<<(ii-n-1))))continue;
                            of[find(ii)].emplace_back(ii);
                        }
                        int d=0;
                        int fin=0,old=0;
                        for(int ii=1;ii<=2*n+4;ii++)
                        {
                            if(of[ii].empty())continue;
                            int bj=0;
                            for(auto x:of[ii])
                            {
                                if(x>n&&x<=2*n)
                                {
                                    bj=1;
                                    break;
                                }
                            }
                            if(!bj)
                            {
                                for(auto x:of[ii])
                                    if(x<=n){old++;break;}
                                continue;
                            }
                            d++;
                            for(auto x:of[ii])
                            {
                                if(x>n&&x<=2*n)
                                {
                                    fin+=p[(x-n-1)]*d;
                                }
                            }
                        }
                        if(sum+old<=2)
                        {
                            f[i%2][use+tot[j]][sum+old][fin]+=f[(i-1)%2][use][sum][lst];
                            if(!vis[i][use+tot[j]][sum+old][fin])
                            {
                                v[i][use+tot[j]][sum+old].push_back(fin);
                                vis[i][use+tot[j]][sum+old][fin]=1;
                            }
                        }
                    }
                }
                for(auto lst:v[i-1][use][sum])
                {
                    f[(i-1)%2][use][sum][lst]=0;
                }
            }
        }
    }
    ll ans=0;
    for(int i=0;i<=zt;i++)
    {
        int mx=0;
        for(int ii=1;ii<=n;ii++)
        {
            mx=max(mx,(i%p[ii])/p[ii-1]);
        }
        if(mx<=2&&f[n%2][k][2-mx][i])
        {
            ans+=f[n%2][k][2-mx][i];
        }
    }
    printf("%lld\n",ans);
}