poj 3340给定两个字符串：s跟t，长度一样，均不超过10，但t只包含数字，而s除了数字还可能含有"?"，问将问号变成数字后得到的数字中，有多少个数是大于t的。
很明显用搜索找出所有符合要求的数字即可。
搜索从s的第一个字符s[0]开始，每次向下递归都检查s的下一个字符s[level]。根据当前字符有一下几种搜索方向：
1. s[level]=='?'， 设当前值为now，则下一个值可以是now*10+i, 0<=i<=9，只要这个值大于等于t[0~level]所表示的数字，则进入下一层递归：
dfs(now*10+i, level+1)。
2. s[level]是一个数字要分两种情况讨论：若now*10+s[level]-'0'>=t[0~level]表示的数字，则dfs(now*10+s[level]-'0', level+1)；否则就返回0，表示s跟t从0
到level这一段不符合要求。
搜索的时候要注意优化，否则当s=“????????", t="00000000"时就要算很久。优化是当now*10+i > t[0~level]时，则j>i的情况都不用再递归计算了，因为dfs( now*10+{i+1 ,..., 9}, level+1)的结果跟dfs(now*10+i, level+1)的结果是一样的。只要乘上9-i就可以了。
1 #include <iostream>
2
3 using namespace std;
4
5 char s[11],t[11];
6 int tt[11];
7 int fact[11];
8 int cnt;
9 int len;
10
11 __int64 dfs(int now,int level)
12 {
13 if(level==len){
14 if(now>tt[level-1]) return 1;//cnt+=(now%fact[level-1]-tt[level-1]%fact[level-1]);
15 return 0;
16 }
17 // 用0~9十个数字来代替?
18 if(s[level]=='?'){
19 int i=0;
20 while(i<10 && now*10+i<tt[level]) i++;
21 __int64 tmp=dfs(now*10+i,level+1);
22 if(i+1<10) tmp+=(9-i)*dfs(now*10+i+1,level+1);
23 return tmp;
24 }else if(now*10+s[level]-'0'>=tt[level]){
25 return dfs(now*10+s[level]-'0',level+1);
26 }else{
27 return 0;
28 }
29 }
30
31 void solve()
32 {
33 int i,j,k;
34 len=strlen(s);
35 tt[0]=t[0]-'0';
36 for(i=1;i<len;i++) tt[i]=tt[i-1]*10+t[i]-'0';
37 cnt=0;
38 printf("%I64d\n",dfs(0,0));
39 }
40
41 int main()
42 {
43 fact[0]=1;
44 for(int i=1;i<=10;i++) fact[i]=fact[i-1]*10;
45 while(true){
46 scanf("%s",s);
47 if(s[0]=='#') return 1;
48 scanf("%s",t);
49 solve();
50 }
51 }
52