[CF 534F] Simplified Nonogram

作法：

一開始看到題目的範圍大概就知道是某種很暴力的爆搜題，而 n<=5 大概是要用來狀態壓縮的。考慮用切一半的方法處理，把盤面切成左右兩半，但這樣就會沒辦法知道左右兩半的每一列分別要有幾陀黑格，所以必須再多加一些條件。假設現在切成的是第 1 ~ mid 行和第 mid+1 ~ m 行，那麼如果我們確定了第 mid 行和第 mid+1 行的每一格的顏色，就可以知道在每一列中，左邊的黑色陀數加上右邊的黑色陀數的值了。而因為兩邊的寬度都不超過m/2，所以他內部的陀數不會超過 m/4 ，所以可以每種情況都枚舉一次，這樣會花至多 2^n * 6^(m/4) 的時間來跑遍每一種情形。所以接下來的問題就變成了必需要快速的獲得這個切割後的小問題的答案：對於一個 n * k 的矩形( k <= m/2 ) ，給定第 k 行中那 n 格的顏色，還有每行每列的黑格陀數，問是否有辦法達成。如果有辦法則輸出一組解。

這個小問題就可以用DP來解了，設 dp[ i ][ j ] 代表第 1 ~ i 行都滿足行的陀數限制，那麼狀態 j 有沒有辦法被達到，其中 j 裡面把好幾個東西壓在一起：目前的這 n 列分別有幾陀黑格，加上第 i 行的黑白狀態。因為黑格陀數不會超過 5 ，所以可以用六進制把前面壓起來，再把他乘 32 加上黑白狀態，這樣總共會有 10 * 6^5 * 32 種狀態，記憶體是夠的。而轉移算是顯然的，只是有點繁複，六進制那邊要小心處理就是了。但題目還要求輸出解，所以只記錄一個狀態可不可行是不夠的，而這只要多記錄 dp[ i ][ j ] 是從 dp[ i-1 ] 的哪一個狀態轉移過來的，就可以一路逆推回去了。另外一個小細節是，當在轉移的時候似乎要枚舉 2^n 種情況，但實際上滿足「這行的陀數為給定的值」的行的黑白狀態不會太多，例如當 n=5 時就最多只有 15 個，因此一個狀態實際上只會轉移到 <= 15 個狀態，可以先把每行的符合要求的數字先預處理出來。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=20+2,stnum=250000 ;
 
void decode(int *v,int x)
{
    for(int i=0;i<5;i++)
        v[i]=x%6 , x/=6 ;
}
int encode(int *v)
{
    int ret=0 ;
    for(int i=4;i>=0;i--) ret=ret*6+v[i] ;
    return ret ;
}
 
vector<int> v[maxn] ;
int n,m,a[maxn],b[maxn] ;
void pre_cal()
{
    for(int i=1;i<=m;i++)
    {
        int num=b[i] ;
        for(int j=0;j<(1<<n);j++)
        {
            int num2=0 ;
            for(int k=0;k<n;k++) if(j&(1<<k))
                if(k==0 || (!(j&(1<<(k-1))))) num2++ ;
            if(num==num2) v[i].push_back(j) ;
        }
    }
}
 
int fa[maxn][stnum] ;
int st[maxn][stnum],cnt[maxn] ;
int tmp[5] ;
bool dfs(int now,int S1,int S2,int *num)
{
    if(now==n)
    {
        memset(tmp,0,sizeof(tmp)) ;
        for(int i=0;i<n;i++) tmp[i]=num[i] ;
        if(fa[m/2][32*encode(tmp)+S1]==-1) return 0 ;
        for(int i=0;i<n;i++)
        {
            tmp[i]=a[i]-num[i] ;
            if((S1&(1<<i)) && (S2&(1<<i))) tmp[i]++ ;
            if(tmp[i]>5 || tmp[i]<0) return 0 ;
        }
        if(fa[m/2+1][32*encode(tmp)+S2]==-1) return 0 ;
        return 1 ;
    }
    for(int i=0;i<6;i++)
    {
        num[now]=i ;
        if(dfs(now+1,S1,S2,num)) return 1 ;
    }
    return 0 ;
}
 
char ans[maxn][maxn] ;
void find_ans(int S1,int S2,int *num)
{
    int st1,st2 ;
    memset(tmp,0,sizeof(tmp)) ;
    for(int i=0;i<n;i++) tmp[i]=num[i] ;
    st1=32*encode(tmp)+S1 ;
 
    for(int i=0;i<n;i++)
    {
        tmp[i]=a[i]-num[i] ;
        if((S1&(1<<i)) && (S2&(1<<i))) tmp[i]++ ;
    }
    st2=32*encode(tmp)+S2 ;
 
    for(int i=m/2,now=st1;i>=1;i--)
    {
        for(int j=0;j<n;j++) ans[j][i]=((now&(1<<j)) ? '*' : '.') ;
        now=fa[i][now] ;
    }
    for(int i=m/2+1,now=st2;i<=m;i++)
    {
        for(int j=0;j<n;j++) ans[j][i]=((now&(1<<j)) ? '*' : '.') ;
        now=fa[i][now] ;
    }
}
 
main()
{
    scanf("%d%d",&n,&m) ;
    for(int i=0;i<n;i++) scanf("%d",&a[i]) ;
    for(int i=1;i<=m;i++) scanf("%d",&b[i]) ;
    if(m==1)
    {
        for(int i=0;i<n;i++) printf("%c\n",a[i]?'*':'.') ;
        return 0 ;
    }
    pre_cal() ;
 
    memset(fa,-1,sizeof(fa)) ;
    st[0][++cnt[0]]=0 ;
    st[m+1][++cnt[m+1]]=0 ;
    for(int i=m,i0=m+1;;)
    {
        for(int j=1;j<=cnt[i0];j++)
        {
            int val=st[i0][j]/32 , S=st[i0][j]%32 ;
            for(auto S2 : v[i])
            {
                decode(tmp,val) ;
                for(int k=0;k<n;k++) if(!(S&(1<<k)) && (S2&(1<<k)))
                    tmp[k]++ ;
                int newval=32*encode(tmp)+S2 ;
                if(fa[i][newval]==-1)
                    st[i][++cnt[i]]=newval ,
                    fa[i][newval]=st[i0][j] ;
            }
        }
        if(i==(m+1)/2) break ;
        if(i>m/2) i=m+1-i , i0=i-1 ;
        else i=m-i , i0=i+1 ;
    }
 
    int num[5] , found=0 ;
    for(auto i : v[m/2])
    {
        for(auto j : v[m/2+1]) if(dfs(0,i,j,num))
        {
             found=1 ;
             find_ans(i,j,num) ;
             break ;
        }
        if(found) break ;
    }
    for(int i=0;i<n;i++) printf("%s\n",ans[i]+1) ;
}