统计有几个’?’,然后二分检测取满足条件的最小的数就可以了. 注意没有问号的时候也要检测一下….
E. Restoring Increasing Sequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Peter wrote on the board a strictly increasing sequence of positive integersa1,a2,…,an. Then Vasil replaced some digits in the numbers of this sequence by question marks. Thus, each question mark corresponds to exactly one lost digit.
Restore the the original sequence knowing digits remaining on the board.
Input
The first line of the input contains integern(1≤n≤105) — the length of the sequence. Nextnlines contain one element of the sequence each. Each element consists only of digits and question marks. No element starts from digit0. Each element has length from 1 to 8 characters, inclusive.
Output
If the answer exists, print in the first line "YES" (without the quotes). Nextnlines must contain the sequence of positive integers — a possible variant of Peter’s sequence. The found sequence must be strictly increasing, it must be transformed from the given one by replacing each question mark by a single digit. All numbers on the resulting sequence must be written without leading zeroes. If there are multiple solutions, print any of them.
If there is no answer, print a single line "NO" (without the quotes).
Sample test(s)
input
3?181?
output
YES11819
input
2???
output
NO
input
51222412??512226?0000?00000
output
YES12224122251222620000100000
/* ***********************************************Author:CKbossCreated Time :2015年03月14日 星期六 00时09分50秒File Name:CF490E_2.cpp************************************************ */#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <cmath>#include <cstdlib>#include <vector>#include <queue>#include <set>#include <map>using namespace std;char str[11];int nine[10]={0,9,99,999,9999,99999,999999,9999999,99999999,999999999};int len,ni;vector<int> vi;bool flag=true;int fenjie[11],fn;int getNUMBER(int mid){int tmid=mid;fn=0;if(mid==0) fenjie[fn++]=0;while(mid){fenjie[fn++]=mid%10;mid/=10;}for(int i=fn;i<ni;i++) fenjie[fn++]=0;reverse(fenjie,fenjie+fn);int ret=0,nx=0;for(int i=0;i<len;i++){int cs=0;if(str[i]!='?') cs=str[i]-'0';else if(nx<fn) cs=fenjie[nx++];ret=ret*10+cs;}return ret;}int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int T_T;vi.push_back(0);scanf("%d",&T_T);while(T_T–){scanf("%s",str);len=strlen(str);if(flag==false) continue;/// find ?ni=0;for(int i=0;i<len;i++) if(str[i]=='?') ni++;bool FUCK = false;if(str[0]=='?') FUCK=true;if(ni==0){int nb=0;for(int i=0;i<len;i++)nb=nb*10+(str[i]-'0');if(nb>*(–vi.end())) vi.push_back(nb);else flag=false;}else{int low=0,high=nine[ni],ans=-1;int lastnumber=*(–vi.end());if(FUCK) low=(int)(pow(10,ni-1));while(low<=high){int mid=(low+high)/2;int num=getNUMBER(mid);if(num>lastnumber) { ans=num; high=mid-1; }else low=mid+1;}if(ans==-1) flag=false;else vi.push_back(ans);}}if(flag){puts("YES");for(int i=1,sz=vi.size();i<sz;i++) printf("%d\n",vi[i]);}else puts("NO");return 0;}
，人生不如意十之八-九，与其诅咒黑暗，倒不如在生命中点燃一盏灯
