题意：小朋友进行了n（n<=10000）场考试，每场考试有一个满分fi和他自己的分数wi（fi,wi<=10^50），小朋友很不老实，他要修改分数来骗他的爸爸妈妈，他有一个单个数字互相转化的表，他想要将他的分数该成单调不降且总和最大
题解：
floyd+贪心构造
先用floyd求出数字之间能否转化
每次构造取now=Min(fi,wi+1)
1、若now的长度比wi小，则无解
2、若now的长度比wi大，则wi直接每一位取最大值
3、若now的长度和wi相等，则每一位尽量取最大，策略如下：
设：a=now，b=wi
α：保证前面的合法，若当前位bi取最大也比ai小，则后面的只管取大
β：保证前面的合法，若当前位bi能取到和ai相等，那么需要检验后面的是否可以填满
γ：保证前面的合法，若当前位怎么取都不合法，则无解
注意不能有前导零，第一位要特判一下，代码中把第一位的情况单独拿出来写了，可以避免一下过于复杂的讨论
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #define ll long long 8 #define un unsigned 9 using namespace std; 10 11 const int N = 100010; 12 13 int n; 14 char ans[N][55],f[N][55],w[N][55],now[55]; 15 int g[15][15]; 16 17 int gi() { 18 int x=0,o=1; char ch=getchar(); 19 while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); 20 if(ch=='-') o=-1,ch=getchar(); 21 while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); 22 return o*x; 23 } 24 25 void solve1(char *a, char *b) { 26 for(un int i=0; i<strlen(b); i++) { 27 for(int k=9; k>=0; k--) { 28 if(g[b[i]-'0'][k]) {b[i]=k+'0';break;} 29 } 30 } 31 memcpy(a,b,55); 32 } 33 34 void solve2(char *a, char *b) { 35 char tmp[55]; bool bj=0; 36 memset(tmp,0,sizeof(tmp)); 37 for(int k=a[0]-'0'; k>=1; k--) { 38 if(g[b[0]-'0'][k]) { 39 if(k==a[0]-'0' && strlen(b)>1) { 40 bool flg=1; 41 for(un int i=1; i<strlen(b); i++) { 42 for(int j=a[i]-'0'-1; j>=0; j--) { 43 if(g[b[i]-'0'][j]) {flg=1;goto tp1;} 44 } 45 if(!g[b[i]-'0'][a[i]-'0']) {flg=0;goto tp1;} 46 } 47 tp1:if(!flg) continue; 48 } 49 tmp[0]=k+'0';break; 50 } 51 } 52 if(!(tmp[0]>='1' && tmp[0]<='9')) puts("NO"),exit(0); 53 if(tmp[0]<a[0]) bj=1; 54 for(un int i=1; i<strlen(b); i++) { 55 if(bj) { 56 for(int k=9; k>=0; k--) 57 if(g[b[i]-'0'][k]) {tmp[i]=k+'0';break;} 58 } 59 else { 60 for(int k=a[i]-'0'; k>=0; k--) { 61 if(g[b[i]-'0'][k]) { 62 if(k==a[i]-'0' && i+1!=strlen(b)) { 63 bool flg=1; 64 for(un int l=i+1; l<strlen(b); l++) { 65 for(int j=a[l]-'0'-1; j>=0; j--) { 66 if(g[b[l]-'0'][j]) {flg=1;goto tp;} 67 } 68 if(!g[b[l]-'0'][a[l]-'0']) {flg=0;goto tp;} 69 } 70 tp:if(!flg) continue; 71 } 72 tmp[i]=k+'0';break; 73 } 74 } 75 if(!(tmp[i]>='0' && tmp[i]<='9')) puts("NO"),exit(0); 76 if(tmp[i]<a[i]) bj=1; 77 } 78 } 79 memcpy(a,tmp,55); 80 } 81 82 void Min(char *a, char *b) { 83 if(strlen(a)<strlen(b)) return; 84 else if(strlen(a)>strlen(b)) {memcpy(a,b,55);return;} 85 else { 86 for(un int i=0; i<strlen(a); i++) { 87 if(a[i]<b[i]) return; 88 else if(a[i]>b[i]) {memcpy(a,b,55);return; 89 } 90 } 91 } 92 } 93 94 int main() { 95 n=gi(); 96 for(int i=1; i<=n; i++) { 97 scanf("%s%s", f[i],w[i]); 98 } 99 for(int i=0; i<=9; i++) 100 for(int j=0; j<=9; j++) 101 g[i][j]=gi(); 102 for(int i=0; i<=9; i++) g[i][i]=1; 103 for(int k=0; k<=9; k++) 104 for(int i=0; i<=9; i++) 105 for(int j=0; j<=9; j++) 106 if(g[i][k] && g[k][j]) g[i][j]=1; 107 memcpy(now,f[n],55); 108 for(int i=n; i>=1; i--) { 109 Min(now,f[i]); 110 if(strlen(now)<strlen(w[i])) {puts("NO");return 0;} 111 if(strlen(now)>strlen(w[i])) solve1(now,w[i]); 112 else solve2(now,w[i]); 113 memcpy(ans[i],now,55); 114 } 115 puts("YES"); 116 for(int i=1; i<=n; i++) { 117 printf("%s ", ans[i]); 118 } 119 return 0; 120 }