fuz 2159 WuYou

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

Sample Output

-1

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

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

　　　　　　　　　假如前面是相同的，那么我要看后面的满足是否有满足小于的，有则去于另一个数字对应位置相同；否则，取另一个数字对应位-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("
");
63     }
64     else printf("-1
");
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
");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 }

搜索

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<cstdlib>
 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]=='') 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             else
39             {
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])
48             end_min=true;
49         else 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<blen){printf("-1
");continue;}
63 
64         end_min=false;
65         dfs(false,0);
66         if(a[0]!='0' && strcmp(a,b)<0)
67         {
68             printf("%s
",a);
69         }
70         else printf("-1
");
71     }
72     return 0;
73 }