P7034 Sol

· · 题解

一个带前导 0 的数字位数为 w 的加法竖式的相邻笔画被压到了一起，求一个合法的原竖式。

行太长了，不如对列考虑。每一列的选法是否合法仅跟上一列怎么选有关。

设 dp_{i,s} 表示目前确定了前 i 列数，且第 i 列的三个数可被表示为状态 s_0,s_1,s_2 时上一个是从哪来的。没有就 -1。

这里的状态 s 分为两种：(s_0+s_1)\bmod 10=s_2；(s_0+s_1+1)\bmod 10=s_2。即是否需要一个进位才能合法。

对于每个 i，枚举这两种状态的 s，首先看如果这一列取 s 本身会不会和输入的结果冲突（即没有输入的一位是 0 而 s 中对应的位是 1），如果不会就枚举上一个状态 s'，且 s' 需要满足在加上 s 这列的进位之后是合法的。如果和 s' 组合起来之后前面几列和输入结果一模一样，而且 dp_{i-1,s'}\neq -1，就可以转移过去。最后找到一个合法 dp_{n,s} 一路跑回来。

有一个坑点是最后一列的判定，不是跟前面的列一样不冲突就行，而是必须恰好和输入的最后一列一样，因为这时没有剩下的列用来补齐没对上的结果了。否则会 WA on test 11。

const string ini[5]={
" 1  0  1  1  0  1  1  1  1  1 ",
"1 10 10 10 11 11 01 00 11 11 1",
" 0  0  1  1  1  1  1  0  1  1 ",
"1 10 11 00 10 10 11 10 11 10 1",
" 1  0  1  1  0  1  1  0  1  1 "
};
void dec(int a,int *b) { b[0]=a%10,b[1]=a%100/10,b[2]=a/100; }
int n,ans[3][N],dp[N][K];
char tup[K][9][3];
vector<int> t[2];
string str[9];
void mian() {
    memset(dp,-1,sizeof(dp));
    scanf("%d",&n),getline(cin,str[0]);
    for (int i=0;i<9;i++) getline(cin,str[i]);
    for (int s=0;s<1000;s++) {
        int tmp[3];
        dec(s,tmp);
        for (int i=0;i<3;i++) for (int j=0;j<5;j++) for (int k=0;k<3;k++)
            tup[s][i*2+j][k]=max(tup[s][i*2+j][k],ini[j][tmp[i]*3+k]);
        for (int i=0;i<9;i++) for (int j=0;j<3;j++) if (!tup[s][i][j]) tup[s][i][j]=' ';
    }
    for (int s=0;s<1000;s++) {
        int tmp[3];
        dec(s,tmp);
        if ((tmp[0]+tmp[1])%10==tmp[2]) t[0].pb(s);
        else if ((tmp[0]+tmp[1]+1)%10==tmp[2]) t[1].pb(s);
    }
    t[0].pb(1000);
    dp[0][1000]=0;
    for (int c=1;c<=n;c++) {
        for (int d=0;d<2;d++) for (int s:t[d]) if (s<1000) {
            int flg=1,tmp[3];
            dec(s,tmp);
            for (int i=0;i<9&&flg;i+=2) if (tup[s][i][1]!=str[i][c*2-1]) flg=0;
            for (int i=1;i<9&&flg;i+=2) if (tup[s][i][2]>str[i][c*2]) flg=0;
            if (flg) {
                for (int ss:t[(tmp[0]+tmp[1]+d)/10]) if (~dp[c-1][ss]) {
                    int flg=1;
                    for (int i=1;i<9&&flg;i+=2) if (max(tup[ss][i][2],tup[s][i][0])!=str[i][c*2-2]) flg=0;
                    if (flg) { dp[c][s]=ss; break; }
                }
            }
        }
    }
    for (int s:t[0]) if (~dp[n][s]) {
        int flg=1;
        for (int i=1;i<9&&flg;i+=2) if (tup[s][i][2]!=str[i][n*2]) flg=0;
        if (flg) {
            for (int tmp[3],j=n;j;j--) {
                dec(s,tmp);
                for (int i=0;i<3;i++) ans[i][j]=tmp[i];
                s=dp[j][s];
            }
            for (int i=0;i<3;i++,cout<<"\n") for (int j=1;j<=n;j++) cout<<ans[i][j];
            return;
        }
    }
    cout<<"NO";
}