T11 Square (HDU5079)

· · 个人记录

T11 Square (HDU5079)

HDU传送门

题意简述

给出一个 N \times N 的网格，其中有一些格子可以涂色，有一些格子已经损坏（即固定为黑色）。

定义一个网格的优美度为其中最大的白色子正方形边长。

对于 1 ~ n 中的每个 i ，求优美度为 i 的涂色方案数。

数据范围
1 \leq T \leq 10 1 \leq n \leq 8
题解

思路

跟T10很相似（还是有些不同）

首先n才8，大概又要考虑状压了

求最大正方形边长是某个定值，肯定不如有大小关系的方便

于是记 ans[i] 为 最大白色子正方形边长小于 i 的方案数（至于为什么是小于等会就知道了）

于是只要输出 ans[i+1]-ans[i] (0 \leq i \leq n) 即可

$ans[n+1]=2^{unbroken}$（无论怎么涂都可以）

所以只用考虑 i=2 ~ n即可

先来想想最大白色子正方形边长怎么判定

还记得吗？以前我们是按点用dp来判定的

但要是仿照T10，这个dp矩阵似乎有点过于庞大（超时）

所以干脆来直接考虑边

假设我们现在考虑的是边长不超过 siz 的正方形

那一行里就会有可能作为正方形底边的 n-siz+1 条边：

1$ ~ $siz$ , $2$ ~ $siz+1$ , $3$ ~ $siz+2$ , $\dots$ , $n-siz+1$ ~ $n

可以转移的是什么呢？

是从每条边开始，最多能向上延伸k行

或者说从每条边开始，能往上画出一个 siz \times k 的白色矩形

或者说这个边中的每一列向上延伸的连续正方形的最小值为k

(再不理解的去看看这个题解吧 QaQ)

这东西状态就比较少了，但显然不是二进制的

显然当 k>=siz 的时候，就已经形成了一个 siz \times siz 的白色正方形了

所以就要舍掉~

所以会发现每一位都是 0 ~ siz-1，也就是siz进制的

所以刚开始的时候设的是小于 siz ，而不是小于等于。不然这里每一位都是 1 ~ siz ，不好处理了

做法

dp就好办了，设 f[i][mac] 为第i行，状态为mac的方案数

来暴力一点

从i-1行转移到第i行的时候，先枚举mac（ siz^{n-siz+1} ）

再枚举第i行的涂色 ( 2^n )

枚举 j ~ j+siz-1 ，只要这里面的涂色有黑格，那就意味着上面无论什么正方形都被破坏掉了，new_mac的这一位变成 0

没有黑格，那 new_mac的这一位就等于 mac 的这一位 +1

只要符合条件（没有一位超过 siz ），就可以把 f[i-1][mac] 的值加进 f[i][new_mac]

外面还要套一层枚举 ans 的 n ，枚举 i 的 n

总时间复杂度 O(n^2 2^n \sum\limits_{siz=1}^nsiz^{n-siz+1})

于是还会发现，因为有些格子已被损坏，固定为黑格，其实不用枚举 2^n 个

不过不优化这个也能过啦

（值得一提，1s是有可能超的，但卡卡常还是挺快的）

注意事项

AC代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int t,n,siz;
bool a[10][10];
int f[10][1100],ans[10];
int ksm(int a,int x){int sum=1; while(x) {if(x&1) sum=sum*1LL*a%mod; a=a*1LL*a%mod,x>>=1;} return sum;}
//快速幂不解释
void go(int r,int mac){
    int m[9]={},tmp[9]={};
    int q=mac;
    for(int i=1;i<=n-siz+1;i++) m[i]=q%siz,q/=siz;//把mac拆开 
    for(int i=0;i<=(1<<n)-1;i++){//枚举格子涂色 
        int p[9]={},s[9]={}; bool flag=0;
        for(int j=1;j<=n;j++){
            p[j]=(i>>(j-1))&1;
            if(p[j]==0 && a[r][j]==1){//只要有损坏的格子涂了白 
                flag=1;
                break;
            } 
            s[j]=s[j-1]+p[j];//前缀和，方便统计是否有黑格 
        }
        if(flag) continue;
        for(int j=1;j<=n-siz+1;j++) tmp[j]=m[j];//tmp即新mac 
        for(int j=1;j<=n-siz+1;j++){
            if(s[j+siz-1]-s[j-1]==0){//如果没有黑格 
                tmp[j]++;
                if(tmp[j]>=siz){
                    flag=1;
                    break;
                }
            }
            else tmp[j]=0;//如果有黑格 
        }
        if(flag) continue;
        int new_mac=0;
        for(int j=n-siz+1;j>=1;j--) new_mac=new_mac*siz+tmp[j];//把新mac压好 
        f[r][new_mac]=(f[r][new_mac]+f[r-1][mac])%mod;//转移 
    }
}
void solve(){
    memset(f,0,sizeof(f));//清空f
    f[0][0]=1;//初始化 
    int t=pow(siz,n-siz+1)-1;//计算的先拿出来算 
    go(1,0);//第一层一次就好 
    for(int i=2;i<=n;i++)
        for(int j=0;j<=t;j++)
            go(i,j);
    for(int mac=0;mac<=t;mac++)
        ans[siz]=(ans[siz]+f[n][mac])%mod;
}
int main(){
    scanf("%d",&t);
    while(t--){
        memset(ans,0,sizeof(ans));
        memset(a,0,sizeof(a));
        scanf("%d",&n);
        int tot=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                char c;cin>>c;
                if(c=='*') a[i][j]=1;//a[i][j]表示该格是否已被损坏 
                else tot++;//统计unbroken个数 
            }
        ans[1]=1,ans[n+1]=ksm(2,tot);
        for(int i=2;i<=n;i++) siz=i,solve();
        for(int i=0;i<=n;i++) printf("%d\n",(ans[i+1]+mod-ans[i])%mod);
    }
}