自动搬运

查看原文

来自洛谷，原作者为

	CarroT1212 chrono::system_clock::now().time_since_epoch().count()

搬运于2025-08-24 22:26:03，当前版本为作者最后更新于2024-03-05 17:48:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

$1 \le w \le 100$。

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

设 $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";
}