题意：给你两个串，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 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<cmath> 6 #include<vector> 7 #include<queue> 8 9 using namespace std; 10 11 #define inf 1e16 12 #define eps 1e-6 13 #define LL long long 14 #define ULL unsigned long long 15 #define MP make_pair 16 #define pb push_back 17 #define mod 1000000009 18 #define lson l, m, rt<<1 19 #define rson m+1, r, rt<<1|1 20 #define mnx 200050 21 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 }
原文：http://www.cnblogs.com/LJ-blog/p/4363650.html
