Problem 2159 WuYou

Accept: 16    Submit: 64

Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

有两个正整数A和B，这两个数的位数相同且不含前缀0。A的一些位不能够确定，用‘?’代替。已知A是满足 A < B 的最大的A。求A 。

Input

第一行一个整数T（T<=1000），表示有T组数据。

每组数据两行，第一行为A，第二行为B（0 < A,B <= 10^10000）。

Output

对于每组数据，输出满足A<B的最大的A。如果不存在，输出-1。

Sample Input

3

1

9

?

8

?1

11

Sample Output

1

7

-1

 

 一开始做，思路都是错的。

思路：对于？而言，假如前面已经有数字不同了，那我不管就取9.

　　　　　　　　　假如前面是相同的，那么我要看后面的满足是否有满足小于的，有则去于另一个数字对应位置相同；否则，取另一个数字对应位-1 。

两种方式写。

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 using namespace std; 6  7 char a[100005]; 8 char b[100005]; 9 int alen,blen;10 struct node11 {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=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                 else52                 {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
           
          
         
        
       

 搜索

 

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 using namespace std; 6  7 char a[100002]; 8 char b[100002]; 9 int alen,blen;10 bool end_min;11 12 void dfs(bool front_min,int i)13 {14     if(a[i]=='\0') return;15     if(a[i]!='?')16     {17         if(a[i]!=b[i])18             front_min=true;19     }20     dfs(front_min,i+1);21     if(a[i]=='?')22     {23         if(front_min==true)24         {25             a[i]='9';26         }27         else if(front_min==false && end_min==true)28         {29             a[i]=b[i];30         }31         else if(front_min==false && end_min==false)32         {33             if(b[i]=='0')34             {35                 a[i]='9';36                 end_min=false;37             }38             else39             {40                 a[i]=b[i]-1;41                 end_min=true;42             }43         }44     }45     else if(a[i]!='?')46     {47         if(a[i]
           
            b[i])50             end_min=false;51     }52 }53 int main()54 {55     int T;56     scanf("%d",&T);57     while(T--)58     {59         scanf("%s%s",a,b);60         alen=strlen(a);61         blen=strlen(b);62         if(alen