1、http://acm.fzu.edu.cn/problem.php?pid=2159
这么一道中等难度的题目都做了好几天了，终于是AC了。。。
2、题目大意：
roblem 2159 WuYou
Accept: 59 Submit: 304
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
319?8?111
Sample Output
17-1
3、解题思路：
首先这道题目题意很容易理解，仔细看题目就会发现情况特别多
1、如果a[i]==b[i]不处理
2、if(a[i]<b[i]) return 1;说明找到这样的数a满足a<b;对于a后边的？都换成9即可
3、if(a[i]>b[i]) 就要分情况讨论了
如果这之前没有出现过?，那么直接return 0就行，这已经说明a>b
如果之前出现过?，就要倒着走所有的?，看能不能比b小1
这时也要注意首位置不能为0，其余位置也要<=0;
4、AC代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char a[1000005];
char b[1000005];
int c[1000005];
int k;
int compare(int l)
{int flag=0;//判断?前是否有a[i]<b[i]k=0;for(int i=0; i<l; i++){if(a[i]==b[i])continue;if(a[i]!='?' && a[i]>b[i] && k==0)//第一个？前有a>breturn 0;else if(a[i]!='?' && a[i]>b[i] && k!=0)//前边出现过?{
// for(int j=k-1;j>=0;j--)
// {
// if(c[j]!=0 && a[c[j]]-'0'-1>=0)
// {
// a[c[j]]=a[c[j]]-1;
// return 1;
// }
// else if(c[j]==0 && a[0]-'0'-1>0)
// {
// a[0]=a[0]-1;
// return 1;
// }
// //???1 2000这组样例这样处理不对else{return 0;}
// }return -1;}else if(a[i]!='?' && a[i]<b[i])//比较出A<B,后边？改成9{return 1;}else if(a[i]=='?'){c[k++]=i;a[i]=b[i];}}return -1;
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%s%s",a,b);int l=strlen(a);int flag=compare(l);if(flag==1)//找到A比B小{for(int i=0; i<l; i++){if(a[i]!='?')printf("%c",a[i]);elseprintf("9");}printf("\n");}else if(flag==0){printf("-1\n");}else{//printf("*****\n");int flag=0;for(int i=k-1; i>0; i--){//printf("%c\n",a[c[i]]);if(a[c[i]]-'0'-1>=0){flag=1;a[c[i]]=a[c[i]]-1;break;}else{//??? 910这组样例需要这样处理for(int p=i; p>0; p--){if(c[p]-1==c[p-1]){if(c[p-1]!=0 && a[c[p-1]]-'0'-1>=0){a[c[p-1]]=a[c[p-1]]-1;for(int q=i; q>p-1; q--){a[c[q]]='9';}flag=1;break;}else if(c[p-1]==0 && a[c[p-1]]-'0'-1>0){a[c[p-1]]=a[c[p-1]]-1;for(int q=i; q>p-1; q--){a[c[q]]='9';}flag=1;break;}}elsebreak;}}if(flag==1)break;}if(flag==1){for(int i=0; i<l; i++){if(a[i]=='?')printf("9");elseprintf("%c",a[i]);}printf("\n");//printf("%s\n",a);}else{if(c[0]==0 && a[0]-'0'-1>0){a[0]=a[0]-1;for(int i=0; i<l; i++){if(a[i]=='?')printf("9");elseprintf("%c",a[i]);}printf("\n");}else if(c[0]!=0){if(a[c[0]]-'0'-1>=0){a[c[0]]=a[c[0]]-1;//?2? 900 这个样例表明得分别打印，如果直接打印字符串a,中会有？for(int i=0; i<l; i++){if(a[i]=='?')printf("9");elseprintf("%c",a[i]);}printf("\n");//printf("%s\n",a);}else{printf("-1\n");}}else{printf("-1\n");}}}}return 0;
}
/*
10
???
800
???1
2000
?2?
900*/
/*
3
???
910
????1?
111010
?10?1?
111010
*/
/*
3
1
9
?
8
?1
1120
?123
2123
?123
1124
123?
1234
123?
1230
123?7??
124567810
123
123
124
123
?123?2
11230210
?
1
?1
1030
???
100
???
123
???
236
??3
124
?2?
131
?2?
133
???
101
??1
10130
123?45?
1233442
?
2
???1
1000
???1
2000*/
第一次错的代码：、wrong answer代码
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char a[10005];
char b[10005];
int c[10005];
int k;
int compare(int l)
{int flag=0;//判断?前是否有a[i]<b[i]k=0;for(int i=0;i<l;i++){if(a[i]==b[i])continue;if(a[i]!='?' && a[i]>b[i] && k==0)//第一个？前有a>breturn 0;else if(a[i]!='?' && a[i]>b[i] && k!=0)//前边出现过?{for(int j=k-1;j>=0;j--){if(c[j]!=0 && a[c[j]]-'0'-1>=0){a[c[j]]=a[c[j]]-1;return 1;}else if(c[j]==0 && a[0]-'0'-1>0){a[0]=a[0]-1;return 1;}else{return 0;}}}else if(a[i]!='?' && a[i]<b[i])//比较出A<B,后边？改成9{return 1;}else if(a[i]=='?'){c[k++]=i;a[i]=b[i];}}return -1;
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%s%s",a,b);int l=strlen(a);int flag=compare(l);if(flag==1)//找到A比B小{for(int i=0;i<l;i++){if(a[i]!='?')printf("%c",a[i]);elseprintf("9");}printf("\n");}else if(flag==0){printf("-1\n");}else{int flag=0;for(int i=k-1;i>0;i--){if(a[c[i]]-'0'-1>=0){flag=1;a[c[i]]=a[c[i]]-1;break;}}if(flag==1){printf("%s\n",a);}else{if(c[0]==0 && a[0]-'0'-1>0){a[0]=a[0]-1;printf("%s\n",a);}else if(c[0]!=0){if(a[c[0]]-'0'-1>=0){a[c[0]]=a[c[0]]-1;printf("%s\n",a);}else{printf("-1\n");}}else{printf("-1\n");}}}}return 0;
}
/*
3
1
9
?
8
?1
1120
?123
2123
?123
1124
123?
1234
123?
1230
123?7??
124567810
123
123
124
123
?123?2
11230210
?
1
?1
1030
???
100
???
123
???
236
??3
124
?2?
131
?2?
133
???
101
??1
1013
123?45?
1233442*/
通过
？？？
910这组样例改正后的代码，虽然样例过了，仍然是wrong answer
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char a[10005];
char b[10005];
int c[10005];
int k;
int compare(int l)
{int flag=0;//判断?前是否有a[i]<b[i]k=0;for(int i=0;i<l;i++){if(a[i]==b[i])continue;if(a[i]!='?' && a[i]>b[i] && k==0)//第一个？前有a>breturn 0;else if(a[i]!='?' && a[i]>b[i] && k!=0)//前边出现过?{for(int j=k-1;j>=0;j--){if(c[j]!=0 && a[c[j]]-'0'-1>=0){a[c[j]]=a[c[j]]-1;return 1;}else if(c[j]==0 && a[0]-'0'-1>0){a[0]=a[0]-1;return 1;}else{return 0;}}}else if(a[i]!='?' && a[i]<b[i])//比较出A<B,后边？改成9{return 1;}else if(a[i]=='?'){c[k++]=i;a[i]=b[i];}}return -1;
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%s%s",a,b);int l=strlen(a);int flag=compare(l);if(flag==1)//找到A比B小{for(int i=0;i<l;i++){if(a[i]!='?')printf("%c",a[i]);elseprintf("9");}printf("\n");}else if(flag==0){printf("-1\n");}else{int flag=0;for(int i=k-1;i>0;i--){//printf("%c\n",a[c[i]]);if(a[c[i]]-'0'-1>=0){flag=1;a[c[i]]=a[c[i]]-1;break;}else{//??? 910这组样例需要这样处理for(int p=i;p>1;p--){if(c[p]-1==c[p-1]){if(a[c[p-1]]-'0'-1>=0){a[c[p-1]]=a[c[p-1]]-1;for(int q=i;q>p-1;q--){a[c[q]]='9';}flag=1;break;}}elsebreak;}}if(flag==1)break;}if(flag==1){printf("%s\n",a);}else{if(c[0]==0 && a[0]-'0'-1>0){a[0]=a[0]-1;printf("%s\n",a);}else if(c[0]!=0){if(a[c[0]]-'0'-1>=0){a[c[0]]=a[c[0]]-1;printf("%s\n",a);}else{printf("-1\n");}}else{printf("-1\n");}}}}return 0;
}
/*
3
???
910
*/
/*
3
1
9
?
8
?1
1120
?123
2123
?123
1124
123?
1234
123?
1230
123?7??
124567810
123
123
124
123
?123?2
11230210
?
1
?1
1030
???
100
???
123
???
236
??3
124
?2?
131
?2?
133
???
101
??1
1013
123?45?
1233442*/
又有几组测试用例检测出错误，改正后仍wrong 的代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char a[1000005];
char b[1000005];
int c[1000005];
int k;
int compare(int l)
{int flag=0;//判断?前是否有a[i]<b[i]k=0;for(int i=0;i<l;i++){if(a[i]==b[i])continue;if(a[i]!='?' && a[i]>b[i] && k==0)//第一个？前有a>breturn 0;else if(a[i]!='?' && a[i]>b[i] && k!=0)//前边出现过?{
// for(int j=k-1;j>=0;j--)
// {
// if(c[j]!=0 && a[c[j]]-'0'-1>=0)
// {
// a[c[j]]=a[c[j]]-1;
// return 1;
// }
// else if(c[j]==0 && a[0]-'0'-1>0)
// {
// a[0]=a[0]-1;
// return 1;
// }
// //???1 2000这组样例这样处理不对else{return 0;}
// }return -1;}else if(a[i]!='?' && a[i]<b[i])//比较出A<B,后边？改成9{return 1;}else if(a[i]=='?'){c[k++]=i;a[i]=b[i];}}return -1;
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%s%s",a,b);int l=strlen(a);int flag=compare(l);if(flag==1)//找到A比B小{for(int i=0;i<l;i++){if(a[i]!='?')printf("%c",a[i]);elseprintf("9");}printf("\n");}else if(flag==0){printf("-1\n");}else{//printf("*****\n");int flag=0;for(int i=k-1;i>0;i--){//printf("%c\n",a[c[i]]);if(a[c[i]]-'0'-1>=0){flag=1;a[c[i]]=a[c[i]]-1;break;}else{//??? 910这组样例需要这样处理for(int p=i;p>0;p--){if(c[p]-1==c[p-1]){if(c[p-1]!=0 && a[c[p-1]]-'0'-1>=0){a[c[p-1]]=a[c[p-1]]-1;for(int q=i;q>p-1;q--){a[c[q]]='9';}flag=1;break;}else if(c[p-1]==0 && a[c[p-1]]-'0'-1>0){a[c[p-1]]=a[c[p-1]]-1;for(int q=i;q>p-1;q--){a[c[q]]='9';}flag=1;break;}}elsebreak;}}if(flag==1)break;}if(flag==1){printf("%s\n",a);}else{if(c[0]==0 && a[0]-'0'-1>0){a[0]=a[0]-1;printf("%s\n",a);}else if(c[0]!=0){if(a[c[0]]-'0'-1>=0){a[c[0]]=a[c[0]]-1;printf("%s\n",a);}else{printf("-1\n");}}else{printf("-1\n");}}}}return 0;
}
/*
10
???
800
???1
2000
*/
/*
3
???
910
????1?
111010
?10?1?
111010
*/
/*
3
1
9
?
8
?1
1120
?123
2123
?123
1124
123?
1234
123?
1230
123?7??
124567810
123
123
124
123
?123?2
11230210
?
1
?1
1030
???
100
???
123
???
236
??3
124
?2?
131
?2?
133
???
101
??1
10130
123?45?
1233442
?
2
???1
1000
???1
2000*/