首页 > 其他 > 详细

fuz 2159 WuYou

时间:2014-03-25 08:42:24      阅读:477      评论:0      收藏:0      [点我收藏+]
Problem 2159 WuYou

Accept: 16    Submit: 64
Time Limit: 1000 mSec    Memory Limit : 32768 KB

bubuko.com,布布扣 Problem Description

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

bubuko.com,布布扣 Input

第一行一个整数T(T<=1000),表示有T组数据。

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

bubuko.com,布布扣 Output

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

bubuko.com,布布扣 Sample Input

3
1
9
?
8
?1
11

bubuko.com,布布扣 Sample Output

1
7
-1
 
 
bubuko.com,布布扣
 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 }
bubuko.com,布布扣

 

fuz 2159 WuYou,布布扣,bubuko.com

fuz 2159 WuYou

原文:http://www.cnblogs.com/tom987690183/p/3622145.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!