有两个正整数A和B,这两个数的位数相同且不含前缀0。A的一些位不能够确定,用‘?’代替。已知A是满足 A < B 的最大的A。求A 。
第一行一个整数T(T<=1000),表示有T组数据。
每组数据两行,第一行为A,第二行为B(0 < A,B <= 10^10000)。
对于每组数据,输出满足A<B的最大的A。如果不存在,输出-1。
1 #include<iostream> 2 #include<stdio.h> 3 #include<cstring> 4 #include<cstdlib> 5 using namespace std; 6 7 char a[100005]; 8 char b[100005]; 9 int alen,blen; 10 struct node 11 { 12 bool front_min; 13 }f[100005]; 14 15 void Init(int n) 16 { 17 int i; 18 for(i=0;i<=n;i++) 19 { 20 f[i].front_min=false; 21 } 22 } 23 void solve() 24 { 25 int i; 26 bool end_min=false; 27 for(i=alen-1;i>=0;i--) 28 { 29 if(a[i]!=‘?‘) 30 { 31 if(a[i]<b[i]) end_min=true; 32 else if(a[i]>b[i]) end_min=false; 33 } 34 else if(a[i]==‘?‘) 35 { 36 if(f[i].front_min==true) 37 { 38 a[i]=‘9‘; 39 } 40 else if(f[i].front_min==false && end_min==true) 41 { 42 a[i]=b[i]; 43 } 44 else if(f[i].front_min==false && end_min==false) 45 { 46 if(b[i]==‘0‘) 47 { 48 a[i]=‘9‘; 49 end_min=false; 50 } 51 else 52 { 53 a[i]=b[i]-1; 54 end_min=true; 55 } 56 } 57 } 58 } 59 if(a[0]!=‘0‘ && strcmp(a,b)<0) 60 { 61 for(i=0;i<alen;i++) printf("%c",a[i]); 62 printf("\n"); 63 } 64 else printf("-1\n"); 65 } 66 int main() 67 { 68 int i,T; 69 bool front_min; 70 scanf("%d",&T); 71 getchar(); 72 while(T--) 73 { 74 scanf("%s%s",a,b); 75 alen=strlen(a); 76 blen=strlen(b); 77 if(alen<blen){printf("-1\n");continue;} 78 Init(alen); 79 front_min=false; 80 for(i=0;i<alen;i++) 81 { 82 if(a[i]!=‘?‘ && a[i]!=b[i]) 83 { 84 front_min=true; 85 } 86 if(front_min==true) 87 f[i].front_min=true; 88 } 89 solve(); 90 } 91 return 0; 92 }
原文:http://www.cnblogs.com/tom987690183/p/3622145.html