P8172

Inui_Sana · 2024-11-01 14:17:00 · 题解

魔怔题。太不牛了。

下文 W\to n,H\to m。

首先考虑 m\le 10^3 怎么做。考虑一个状压（其实本质上是插头）dp：设 dp_{i,j,S} 表示当前前 i-1 行和第 i 行的前 j 个位置已经填完，S 的前 j 位表示 (i+1,1) 到 (i+1,j) 是否被填，后 n-j 位表示 (i,j+1) 到 (i,n) 是否被填。

转移分四种情况讨论。

以上转移还需要判断是否合法，也是容易的，不多讲。

这样就能得到一个 O(nm2^n) 的 dp。

考虑 m 变大怎么办。下文称一个初始有格子被填的行为关键行。一个很自然的想法是用类似矩阵快速幂的方法处理两个关键行之间空的若干行，但是这样复杂度大概至少是 O((2^n)^3)，显然难以通过。

然后充分发挥想象力，首先手玩一下，发现除了转移一之外的所有转移，在经过 6 行之后都可以变回原来的状态，加上转移一，感性理解也是类似的。

然后观察（或打表）发现对于一个状态，它能转移到的状态根据行数是指数级增长的。于是大胆猜测：如果两个关键行间距离较远，则删去 6x 行是不影响最后可以到达的状态的，剩下至少 6 行大概就足够转移到所有可行状态。

具体地，考虑两个相邻的关键行是 x,y，则令 y=x+\min(y-x,(y-x-1)\bmod 6+7)，这样相当于删掉若干行，最多剩下 12k 行，对这些再做上面那个暴力即可。

时间复杂度 O(nk2^n)。具体的正确性证明不是很会，可能打表观察是最好的方法，可以参考一下官方题解。

code：

int n,m,k,X[M],Y[M],a[17][M],f[17][N],dp[N];
vector<int> g;
map<int,int> id;
void Yorushika(){
    read(n,m,k);
    int s=0;
    rep(i,1,k){
        read(X[i],Y[i]);
        g.eb(Y[i]);
    }
    g.eb(m),g.eb();
    sort(g.begin(),g.end());
    g.erase(unique(g.begin(),g.end()),g.end());
    int lst=0;
    for(int i:g){
        id[i]=id[lst]+min(i-lst,((i-lst-1)%6+13));
        lst=i,m=id[i];
    }
    rep(i,1,k){
        a[X[i]][id[Y[i]]]=1;
        if(Y[i]==1){
            s|=1<<(X[i]-1);
        }
    }
    dp[s]=1;
    const int mx=1<<n;
    cerr<<m<<'\n';
    rep(i,1,m-1){
        mems(f,0);
        rep(S,0,mx-1){
            f[0][S]=dp[S];
        }
        rep(j,0,n-1){
            rep(S,0,mx-1){
                if(!f[j][S]){
                    continue;
                }
                int x=S>>j&1,y=S>>(j+1)&1;
                if(j<n-1&&x&&!y&&!a[j+1][i+1]&&!a[j+2][i+1]){
                    int T=S|(1<<j)|(1<<(j+1));
                    f[j+2][T]|=f[j][S];
                }
                if(j<n-1&&!x&&y&&!a[j+1][i+1]&&!a[j+2][i+1]){
                    int T=S|(1<<j)|(1<<(j+1));
                    f[j+2][T]|=f[j][S];
                }
                if(j<n-1&&!x&&!y&&!a[j+1][i+1]){
                    int T=S|(1<<j)|((a[j+2][i+1])<<(j+1));
                    f[j+2][T]|=f[j][S];
                }
                if(j<n-1&&!x&&!y&&!a[j+2][i+1]){
                    int T=S|(1<<(j+1))|((a[j+1][i+1])<<j);
                    f[j+2][T]|=f[j][S];
                }
                if(j<n-2&&!x&&!y&&!(S>>(j+2)&1)&&!a[j+1][i+1]&&!a[j+2][i+1]&&!a[j+3][i+1]){
                    int T=S|(1<<j)|(1<<(j+1))|(1<<(j+2));
                    f[j+3][T]|=f[j][S];
                }
                if(x){
                    int T=(S^(1<<j))|(a[j+1][i+1]<<j);
                    f[j+1][T]|=f[j][S];
                }
            }
        }
        rep(S,0,mx-1){
            dp[S]=f[n][S];
        }
    }
    puts(dp[mx-1]?"YES":"NO");
}
signed main(){
    int t=1;
    //read(t);
    while(t--){
        Yorushika();
    }
}

upd：被 hack 了，原因是 id[i]=id[lst]+min(i-lst,((i-lst-1)%6+7)); 中间留的行数不够。看官方题解似乎是要留 11 行？