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
AC代码：
#include<stdio.h>
#include<string.h>
char last[100010],next[100010];
int not_equal[100010],len;
void work()
{
int i;
bool flag=0;
for(i=len-1;i>=0;i--)
{
if(last[i]!='?')
{
if(last[i]<next[i])
flag=1;
else if(last[i]>next[i])
flag=0;
}
else if(last[i]=='?')
{
if(not_equal[i]==1)
{
last[i]='9';
}
else if(not_equal[i]==0 && flag==1)
{
last[i]=next[i];
}
else if(not_equal[i]==0 && flag==0)
{
if(next[i]=='0')
{
last[i]='9';
flag=0;
}
else
{
last[i]=next[i]-1;
flag=1;
}
}
}
}
if(last[0]!='0' && strcmp(last,next)<0)
{
printf("%s\n",last);
}
else printf("-1\n");
}
int main()
{
//freopen("b.txt","r",stdin);
int t,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%s",last);
scanf("%s",next);
memset(not_equal,0,sizeof(not_equal));
bool flag=0;
len=strlen(last);
for(i=0;i<len;i++)
{
if(last[i]!='?'&&last[i]!=next[i])
flag=1;
if(flag)
{
not_equal[i]=1;
}
}
work();
}
return 0;
}
下面这个为写挫的。。（整个人都不好啦！！！
）
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main() {
int T;
char a[10005], b[10005];
scanf("%d", &T);
while(T--) {
scanf("%s %s", a, b);
int la = strlen(a), lb = strlen(b);
if(la > lb) { printf("-1\n"); continue; }
else if(la < lb) {
for(int i=0; i<la; i++) {
if(a[i] == '?') printf("9");
else printf("%c", a[i]);
}
putchar(10); continue;
}
else if(la == lb) {
int index = -1;
for(int i=0; i<la; i++) {
if(a[i] != b[i] && a[i] != '?') {
index = i; break;
}
}
if(index != -1 && a[index] < b[index]) {
for(int i = 0; i <= index; i++) {
if(a[i] == '?') printf("%c", b[i]);
else printf("%c", a[i]);
}
for(int i = index + 1; i < la; i++) {
if(a[i] == '?') printf("9");
else printf("%c", a[i]);
}
putchar(10); continue;
}
else if(index != -1 && a[index] >= b[index]) {
int index2 = -1;
for(int i = index-1; i >= 0; i--) {
if(a[i] == '?' && b[i] != '0') {
index2 = i; break;
} else if(a[i] == '?' && b[i] == '0') a[i] = '0';
}
if(index2 == -1 || (index2 == 0 && b[0] == '1') ) {
printf("-1\n"); continue;
} else {
a[index2] = b[index2] - 1;
}
for(int i = 0; i <= index; i++) {
if(a[i] == '?') printf("%c", b[i]);
else printf("%c", a[i]);
}
for(int i = index + 1; i < la; i++) {
if(a[i] == '?') printf("9");
else printf("%c", a[i]);
}
putchar(10); continue;
}
else if(index == -1) {
int index2 = -1;
for(int i = la - 1; i >= 0; i--) {
if(a[i] == '?' && b[i] != '0') {
index2 = i; break;
} else if(a[i] == '?' && b[i] == '0') a[i] = '0';
}
if(index2 == -1 || (index2 == 0 && b[0] == '1')) {
printf("-1\n"); continue;
} else a[index2] = b[index2] - 1;
for(int i=0; i<la; i++) {
if(a[i] == '?') printf("%c", b[i]);
else printf("%c", a[i]);
}
putchar(10); continue;
}
}
}
return 0;
}
原文：http://blog.csdn.net/u014355480/article/details/43547111