[洛谷P1822]魔法指纹

题目传送门

这道题事实上解并不多，所以我们倒过来从$7$开始搜索。主过程中为广搜，而函数深搜进行拓展。其实是对于前导$0$删去的情况也要考虑，否则只有$20pts$。

最后别忘了判断$7$在不在$[A,B]$。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define rep(i, a, b) for (register int i = a; i <= b; ++i)
 6 
 7 int A, B, ans, pw[10], dB = 0;
 8 
 9 queue< pair<int, int> > q;
10 
11 void dfs(int v, int s, int dep, int max_dep, int last) {
12     if (dep > dB+1) return;
13     if (dep == max_dep) {
14         if (s <= B && last) {
15             q.push(make_pair(s, dep));
16             if (s >= A) 
17                 ans++;
18         }
19         return;
20     }
21     int bit = v % 10;
22     if (bit+last < 10) dfs(v / 10, s + (bit+last) * pw[dep], dep+1, max_dep, bit+last);
23     if (last-bit >= 0 && bit != 0) dfs(v / 10, s + (last-bit) * pw[dep], dep+1, max_dep, last-bit);
24 }
25 
26 int main() {
27     scanf("%d%d", &A, &B)
28     if (A <= 7 && 7 <= B) ans++;
29     q.push(make_pair(7, 1));
30     pw[0] = 1;
31     rep(i, 1, 9) {
32         pw[i] = pw[i-1] * 10;
33         if (B > pw[i]) dB = i;
34     }
35 
36     while (!q.empty()) {
37         pair<int, int> h = q.front(); q.pop();
38         rep(i, 0, 9)
39             dfs(h.first, i, 1, h.second+1, i);
40         if (h.second <= dB) q.push(make_pair(h.first, h.second+1));
41     }
42 
43     printf("%d", ans);
44     return 0;
45 }

这道题如果要打表也可以，就是表会很大。