Problem

题目地址

Talk

压行会遭报应的，今天就遭报应了。再压行我 TM 扇自己十个耳光。

引入《圣经 - 马保国章》改编

这个 OIer\(^1\) 为了方便，不讲码德。来骗，来压行，这正常的代码！这好吗？这不好。我劝，这个 OIer \(How's\ the\ whether,think\ better\)，以后不要再放这样的聪明，小聪明啊。写代码，要以和为贵，要讲码德，不要搞窝里斗。谢谢朋友们。

OIer\(^1\)：指博主本人。

最后特别感谢 ygt 大佬帮我写了一份 judge！！！

直接上代码吧，模拟加DP即可。

Code

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 10;
int L[N][N],t[N][N];
int s[N][N][N],ts[N][N][N];
void Init() {
	for(int i=0;i<10;++i) {
		for(int j=1;j<=5;++j) L[i][j] = 1;
	}
	L[0][3] = 0; t[0][2] = t[0][4] = 1;
	L[1][1] = L[1][3] = L[1][5] = 0;
	L[2][4] = 0; t[2][4] = 1;
	//
	L[4][1] = L[4][5] = 0; t[4][2] = 1;
	L[5][2] = 0; t[5][2] = 1;
	L[6][2] = 0; t[6][2] = t[6][4] = 1;
	L[7][3] = L[7][5] = 0;
	t[8][2] = t[8][4] = 1;
	t[9][2] = 1;
	
	/*
	for(int i=0;i<=9;++i) {
		printf("%d\n",i);
		for(int j=1;j<=5;++j) printf("%d %d\n",t[i][j],L[i][j]);
		puts("");
	}
	*/
	
	for(int x=0;x<=9;++x) {
		for(int y=0;y<=9;++y) {		
			for(int z=0;z<=9;++z) {
				int res_s = 0, res_ts = 0;
				for(int j=1;j<=5;++j) {
					res_s |= (L[x][j] << (j-1));
					res_s |= (L[y][j] << (j-1+2));
					res_s |= (L[z][j] << (j-1+4));
					res_ts |= (t[x][j] << (j-1));
					res_ts |= (t[y][j] << (j-1+2));
					res_ts |= (t[z][j] << (j-1+4));
				}
				s[x][y][z] = res_s; ts[x][y][z] = res_ts;
			}
		}
	}
}
const int maxn = 107;
int w;
int val[maxn];
bool f[maxn][N][N][N];
typedef pair<int,int> PII;
pair<PII,int> pre[maxn][N][N][N];
#define mp make_pair
#define fi first
#define se second
void Print(int i,int x,int y,int z);
string ansx,ansy,ansz;
void test();
int main()
{
	freopen("digital.in","r",stdin);
	freopen("digital.out","w",stdout);
	Init();
	w = read();
	for(int i=1;i<=9;++i) {
		if(i&1) {
			for(int j=w;j>=1;--j) {
				int x = read();
				val[j] |= (x << (i-1));
			}
		} else {
			for(int j=w+1;j>=1;--j) {
				int x = read();
				val[j] |= (x << (i-1));
			}
		}
	}
	for(int x=0;x<=9;++x) {
		for(int y=0;y<=9;++y) {
			if(w == 1) {
				int z = (x + y);
				if(z > 9) continue;
				int now = s[x][y][z];
				int ed = ts[x][y][z];
				if(now==val[w] && ed==val[w+1]) f[w][x][y][z] = 1; //pre[w][x][y][z] = mp(mp(a,b),c);
			} else {
				int z = (x + y) % 10;
				if(s[x][y][z] == val[1]) {
					f[1][x][y][z] = 1;
				}
			}
		}
	}
	for(int i=2;i<w;++i) {
		for(int a=0;a<=9;++a) {
			for(int b=0;b<=9;++b) {
				for(int c=0;c<=9;++c) {
					if(!f[i-1][a][b][c]) continue;
					for(int x=0;x<=9;++x) {
						for(int y=0;y<=9;++y) {
							int z = (x + y + (c<a+b ? 1 : 0)) % 10;
							int now = s[x][y][z] | ts[a][b][c];
							if(now == val[i]) {
								f[i][x][y][z] = 1; pre[i][x][y][z] = mp(mp(a,b),c);
							}
						}
					}
				}
			}
		}
	}
	for(int a=0;a<=9;++a) {
		for(int b=0;b<=9;++b) {
			for(int c=0;c<=9;++c) {
				if(!f[w-1][a][b][c]) continue;
				for(int x=0;x<=9;++x) {
					for(int y=0;y<=9;++y) {
						int z = (x + y + (c<a+b ? 1 : 0));
						if(z > 9) continue;
						int now = s[x][y][z] | ts[a][b][c];
						int ed = ts[x][y][z];
						/*if(x==2 && y==0 && z==2) {
							printf("test: %d %d\n",now,val[w]);
						}*/
						if(now==val[w] && ed==val[w+1]) {
							f[w][x][y][z] = 1; pre[w][x][y][z] = mp(mp(a,b),c);
						}
					}
				}
			}
		}
	}
	bool flag = 0;
	for(int x=0;x<=9;++x) {
		for(int y=0;y<=9;++y) {
			for(int z=0;z<=9;++z) {
				if(f[w][x][y][z] == 1) {
					Print(w,x,y,z); flag = 1; break;
				}
			}
			if(flag) break;
		}
		if(flag) break;
	}
	if(flag) {
		//puts("YES"); return 0;
		cout << ansx << endl;
		cout << ansy << endl;
		cout << ansz << endl;
	} else puts("NO");
	//test();
	return 0;
}
void Print(int i,int x,int y,int z) {
	if(i == 0) return ;
	pair<PII,int> tmp = pre[i][x][y][z];
	int a = tmp.fi.fi, b = tmp.fi.se, c = tmp.se;
	Print(i-1,a,b,c);
	ansx = (char)(x+48) + ansx;
	ansy = (char)(y+48) + ansy;
	ansz = (char)(z+48) + ansz;
}
void test() {
	printf("%d\n",val[w]);
	printf("%d\n",s[2][0][2]);
	printf("%d\n",ts[7][1][9]);
	printf("%d\n",s[2][0][2]|ts[7][1][9]);
	printf("%d\n",f[w][2][0][2]);
}
/*
10
  1 1 1 1 1 1 1 1 1 1 
0 1 1 1 1 1 1 1 1 1 1 
  1 0 1 1 1 1 1 1 1 0 
1 1 1 1 1 1 1 1 1 1 1 
  1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 
  1 1 1 1 1 1 1 1 1 0 
1 1 1 1 1 1 1 1 0 1 1 
  1 1 1 1 1 1 1 1 1 0

7799999597
0488888694
8288888291
*/

Summary

• 具体错因：压行后 if 后原来要接 f[w][x][y][z] = 1; pre[w][x][y][z] = mp(mp(a,b),c);,但是只接一句话，转移路径在 if 外。总之：

不要压行！！！