JZ初中OJ 1566. [GDKOI]幸运锁

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int readint() {
 4     int x = 0;
 5     char c = getchar();
 6     for (; c <  ‘0‘ || c >  ‘9‘; c = getchar());
 7     for (; c >= ‘0‘ && c <= ‘9‘; c = getchar()) x = (x * 10) + (c - ‘0‘);
 8     return x;
 9 }
10 long long toVal(string s) {
11     long long sum = 0;
12     for (int i = 0; s[i]; ++i)
13         sum = (sum * 10) + (s[i] - ‘0‘);
14     return sum;
15 }
16 const int MAXN = 170000 + 5;
17 int x, y, hd, tl, len, ans;
18 string s, d[MAXN];
19 void dfs(int pos)
20 {
21     long long tmp = 0;
22     if (pos == len)
23     {
24         tmp = toVal(s);
25         int addnum = 0;
26         for (; tmp <= y;)
27         {
28             d[++tl] = s;
29             if (tmp >= x && tmp <= y) ++ans;
30             
31             s = s[0] + s;
32             ++addnum;
33             tmp = toVal(s);
34         }
35         s.erase(0, addnum);
36         return;
37     }
38     tmp = (s[pos] - ‘0‘) + (d[hd][pos] - ‘0‘);
39     if (tmp <= 9)
40     {
41         s += (char)(tmp + ‘0‘);
42         dfs(pos + 1);
43         s.erase(pos + 1, 1);
44     }
45     tmp = s[pos] - d[hd][pos];
46     if (tmp >= 0 && d[hd][pos] != ‘0‘)
47     {
48         s += (char)(tmp + ‘0‘);
49         dfs(pos + 1);
50         s.erase(pos + 1, 1);
51     }
52 }
53 int main()
54 {
55     freopen("lucky.in", "r", stdin);
56     freopen("lucky.out", "w", stdout);
57     x = readint();
58     y = readint();
59     d[tl = 1] = "7";
60     if (x <= 7 && y >= 7) ++ans;
61     for (; hd < tl;)
62     {
63         len = d[++hd].size();
64         for (char c = ‘1‘; c <= ‘9‘; ++c) {
65             s = c;
66             dfs(0);
67         }
68       }
69     printf("%d\n", ans);
70     fclose(stdin);
71     fclose(stdout);
72     return 0;
73 }