fuz 2159 WuYou

 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 }