题意：给你两个串，A串和B串，其中A串有些不确定。叫你求 A < B的最大A串
做法：一开始做错了。去问小坤子，他讲了一下他的思路。就是开一个 f 数组。f[i]表示从第i位开始存不存在方案，如果前面都相等的话。从n-1位开始扫
然后再从第0位开始扫，if( f[i] == 1 ) ，则s[i] = ch[i]; if( f[i] == 0 )的话，就看这一位是不是'0'，不是'0'的话，s[i] = ch[i] - 1，就可以break了，后面的问号都可以变成9。如果是'0'的话，s[i] = '0'，继续向后扫。如果s[i] < ch[i]了，就break，后面的问号都可以填9。具体看代码吧
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 9 using namespace std;10 11 #define inf 1e1612 #define eps 1e-613 #define LL long long14 #define ULL unsigned long long15 #define MP make_pair16 #define pb push_back17 #define mod 100000000918 #define lson l, m, rt<<119 #define rson m+1, r, rt<<1|120 #define mnx 20005021 22 char s[mnx], ch[mnx];23 bool check(){24 int n = strlen( s );25 if( s[0] == '0' ) return false;26 for( int i = 0; i < n; ++i ){27 if( s[i] > ch[i] ) return false;28 if( s[i] < ch[i] ) return true;29 }30 return false;31 }32 int f[mnx];33 int main(){34 int cas;35 scanf( "%d", &cas );36 while( cas-- ){37 scanf( "%s", s );38 scanf( "%s", ch );39 int n = strlen( s );40 f[n] = 0;41 for( int i = n-1; i >= 0; --i ){42 if( s[i] == '?' ){43 if( ch[i] > '0' ) f[i] = 1;44 else f[i] = f[i+1];45 }46 else if( ch[i] > s[i] )47 f[i] = 1;48 else if( ch[i] == s[i] )49 f[i] = f[i+1];50 else f[i] = 0;51 }52 int cur;53 for( int i = 0; i < n; ++i ){54 if( s[i] == '?' ){55 if( f[i+1] == 1 )56 s[i] = ch[i];57 else{58 if( ch[i] == '0' ) s[i] = '0';59 else {60 s[i] = (char)( ch[i] - 1 ), cur = i + 1; break;61 }62 }63 }64 else{65 if( s[i] < ch[i] ){66 cur = i + 1; break;67 }68 }69 }70 for( int i = cur; i < n; ++i ){71 if( s[i] == '?' )72 s[i] = '9';73 }74 if( check() ) printf( "%s\n", s );75 else puts( "-1" );76 }77 return 0;78 }