menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[插头DP]HHHOJ167【俄罗斯方块】题解
apps HHHOJ
local_offer 查看标签
comment 0 条评论

解题报告

肯定是插头DP,不过如果把每个俄罗斯方块考虑过去,会累死的……这时候我们就要利用俄罗斯方块的性质:所有大小为 $4​$ 的连通块都是一个俄罗斯方块!

所以根本就不用管俄罗斯方块,只需要考虑如何用大小为 $4​$ 的连通块拼出整个棋盘就行了。

斯波想法是只记录四种插头:连通块大小为 $0,1,2,3$ 的插头。但是有两种很恶心的情况:

  1. 无法进行统计:

    OXX  XX  XXX  XXX
    XXO  XO  XOO  OXO
         XO

    比如上面几种,不管选择哪个X都统计不了。

  2. $2\times 2$ 的俄罗斯方块:会统计多次。

经过若干次重写和打补丁QAQ,我发现可以再加上 $3$ 种插头:$4$ 表示连通块大小为 $2$ 的拐角插头(同时将 $2$ 插头的定义改为没有拐角的连通块大小为 $2$ 的插头),$5$ 表示定向插头(不能在当前格子拐弯),$6$ 表示终止插头(当前格子不能连出去)。

然后怎么解决前面两个问题呢?

  1. 用 $5$ 插头和 $6$ 插头确定 $L$ 型俄罗斯方块两端的长度,用两个 $6$ 插头构造出丁字形俄罗斯方块。
  2. 强制 $A=4,B=1$ 的时候统计 $2\times 2$ 的俄罗斯方块。

大力分类讨论就行了。

示例程序

#include<cstdio>
using namespace std;
const int maxn=30,maxm=7,maxs=25000,HA=99971,MOD=1e9+7;

int n,m,K;bool pic[maxn+5][maxm+5];
struct Hashmap{
    int E,lnk[HA],son[maxs+5],nxt[maxs+5],w[maxs+5];
    inline void Clear() {for (int i=0;i<HA;i++) lnk[i]=0;E=0;}
    inline void Add(int x,int y) {son[++E]=y;w[E]=0;nxt[E]=lnk[x];lnk[x]=E;}
    inline int& operator [] (const int &x){
        for (int j=lnk[x%HA];j;j=nxt[j]) if (son[j]==x) return w[j];
        Add(x%HA,x);return w[E];
    }
}f[2];

#define pos(s,i) ((s)>>((i)*3)&7)
#define val(i,j) ((j)<<((i)*3))
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d",&n,&m,&K);for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) pic[i][j]=1;
    for (int i=1,x,y;i<=K;i++) scanf("%d%d",&x,&y),pic[x+1][y+1]=0;f[0][0]=1;
    for (int i=1,c=1;i<=n;i++){
        int F;f[c].Clear();for (int e=1;e<=f[c^1].E;e++) if (F=f[c^1].w[e]) f[c][f[c^1].son[e]<<3]=F;
        for (int j=(f[c^1]=f[c],1);j<=m;j++,c^=1)
            for (int e=(f[c].Clear(),1);e<=f[c^1].E;e++){
                F=f[c^1].w[e];if (!F) continue;int s=f[c^1].son[e],A=pos(s,j-1),B=pos(s,j);
                if (!pic[i][j]) {if (!A&&!B) AMOD(f[c][s],F);}
                else if (!A&&!B){
                    if (pic[i][j+1]) AMOD(f[c][s^val(j,1)],F);
                    if (pic[i+1][j]) AMOD(f[c][s^val(j-1,1)],F);
                    if (pic[i][j+1]&&pic[i+1][j]){
                        AMOD(f[c][s^val(j-1,5)^val(j,6)],F);
                        AMOD(f[c][s^val(j-1,6)^val(j,5)],F);
                    }
                } else if (!A&&B==1){
                    if (pic[i][j+1]) AMOD(f[c][s^val(j,1)^val(j,4)],F);
                    if (pic[i+1][j]) AMOD(f[c][s^val(j,1)^val(j-1,2)],F);
                    if (pic[i][j+1]&&pic[i+1][j]) AMOD(f[c][s^val(j,1)^val(j-1,6)^val(j,6)],F);
                } else if (!A&&B==2){
                    if (pic[i][j+1]) AMOD(f[c][s^val(j,2)^val(j,3)],F);
                    if (pic[i+1][j]) AMOD(f[c][s^val(j,2)^val(j-1,3)],F);
                } else if (!A&&B==3) AMOD(f[c][s^val(j,3)],F);
                else if (!A&&B==4){
                    if (pic[i][j+1]) AMOD(f[c][s^val(j,4)^val(j,3)],F);
                    if (pic[i+1][j]) AMOD(f[c][s^val(j,4)^val(j-1,3)],F);
                } else if (!A&&B==5) {if (pic[i+1][j]) AMOD(f[c][s^val(j,5)^val(j-1,3)],F);}
                else if (!A&&B==6) AMOD(f[c][s^val(j,6)],F);
                else if (A==1&&!B){
                    if (pic[i][j+1]) AMOD(f[c][s^val(j-1,1)^val(j,2)],F);
                    if (pic[i+1][j]) AMOD(f[c][s^val(j-1,1)^val(j-1,4)],F);
                    if (pic[i][j+1]&&pic[i+1][j]) AMOD(f[c][s^val(j-1,1)^val(j-1,6)^val(j,6)],F);
                } else if (A==1&&B==1){
                    if (pic[i][j+1]) AMOD(f[c][s^val(j-1,1)^val(j,1)^val(j,3)],F);
                    if (pic[i+1][j]) AMOD(f[c][s^val(j-1,1)^val(j,1)^val(j-1,3)],F);
                } else if (A==1&&B==2) AMOD(f[c][s^val(j-1,1)^val(j,2)],F);
                else if (A==1&&B==5) AMOD(f[c][s^val(j-1,1)^val(j,5)],F);
                else if (A==2&&!B){
                    if (pic[i][j+1]) AMOD(f[c][s^val(j-1,2)^val(j,3)],F);
                    if (pic[i+1][j]) AMOD(f[c][s^val(j-1,2)^val(j-1,3)],F);
                } else if (A==2&&B==1) AMOD(f[c][s^val(j-1,2)^val(j,1)],F);
                else if (A==3&&!B) AMOD(f[c][s^val(j-1,3)],F);
                else if (A==4&&!B){
                    if (pic[i][j+1]) AMOD(f[c][s^val(j-1,4)^val(j,3)],F);
                    if (pic[i+1][j]) AMOD(f[c][s^val(j-1,4)^val(j-1,3)],F);
                } else if (A==4&&B==1) AMOD(f[c][s^val(j-1,4)^val(j,1)],F);
                else if (A==5&&!B) {if (pic[i][j+1]) AMOD(f[c][s^val(j-1,5)^val(j,3)],F);}
                else if (A==5&&B==1) AMOD(f[c][s^val(j-1,5)^val(j,1)],F);
                else if (A==6&&!B) AMOD(f[c][s^val(j-1,6)],F);
            }
    }printf("%d\n",f[n*m&1][0]);return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up