hdu 2410 Barbara Bennett's Wild Numbers

　　挺好玩的一道题目。这道题的意思是给出一个模糊值以及一个确定值，要求求出模糊值中大于确定值的个数有多少。

　　这题我是直接用dfs的方法搜索的，对于每一位如果之前位置的形成的数比确定值当前形成的数小，之后就不可能形成满足要求的值了。如果是大于的，之后的所有问号都可以填入0~9任何一个数字。如果是等于，就要继续搜索下一位。

代码如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 char str1[15], str2[15];
10 
11 LL dfs(int pos, LL cur1, LL cur2) {
12     LL ret = 0;
13     if (cur1 < cur2) return 0;
14     if (cur1 > cur2) {
15         ret = 1;
16         while (str1[pos]) {
17             if (str1[pos] == '?') ret *= 10;
18             pos++;
19         }
20         return ret;
21     }
22     if (str1[pos] == 0 || str2[pos] == 0) return 0;
23     if (str1[pos] == '?') {
24         for (int i = 0; i <= 9; i++) {
25             if (i < str2[pos] - '0') continue;
26             ret += dfs(pos + 1, cur1 * 10 + i, cur2 * 10 + str2[pos] - '0');
27         }
28     } else {
29         ret += dfs(pos + 1, cur1 * 10 + str1[pos] - '0', cur2 * 10 + str2[pos] - '0');
30     }
31     return ret;
32 }
33 
34 int main() {
35 //    freopen("in", "r", stdin);
36     while (cin >> str1 && str1[0] != '#') {
37         cin >> str2;
38         cout << dfs(0, 0, 0) << endl;
39     }
40     return 0;
41 }

View Code

——written by Lyon