题目地址：洛谷：【P1822】魔法指纹 – 洛谷

题目描述

对于任意一个至少两位的正整数n，按如下方式定义magic(n)：将n按十进制顺序写下来，依次对相邻两个数写下差的绝对值。这样，得到了一个新数，去掉前导0，则定义为magic(n)。若n为一位数，则magic(n)=n。
例如：magic(5913)=482，magic(1198)=081=81，magic(666)=00=0。
对任意一个数n，序列n，magic(n)，magic(magic(n))，…迟早会变成一个一位数。最后的这个值称为数n的magic指纹。
例如，对于n=5913，我们得到序列：5913，482，46，2。所以5913的magic指纹为2。
若一个数的magic指纹为7，则认为这个数是个幸运数。
现在，给定A，B，计算出[A,B]中有多少个数是幸运数。

题意简述

一个magic(n)为对一个数求相邻数位之间的差组成的不含前导0的新数。连续对一个数做magic操作会得到一个一位数，求区间[A, B]中连续magic操作后得到的一位数是7的数的个数。

输入输出格式

输入格式：
输入两行，每行一个数。第一行是A，第二行表示B。

输出格式：
输出[A,B]中有多少个数是幸运数。

输入输出样例

输入样例#1：

1
9

输出样例#1：

1

说明

数据范围：
对30%数据，B≤10000。
对100%数据，0<A≤B≤1,000,000,000。

题解

参考资料：P1822 魔法指纹 题解
拿到这个题的时候除了暴力以外就没什么思路，那就打表呗。但是表太大内存装不下，那就分块呗。计算出1到10⁹之间每\sqrt{10^9}个区间的答案，区间以外的就暴力验证，每次验证的时间是O(\log_{10} n)，总复杂度也不高。
不过神犇rqy发现直接BFS套DFS时间也是可以接受的。具体做法就是，从7开始反向BFS找到可以magic操作一次得到7的数字，反向扩展的过程用DFS实现。DFS过程中，下一位只有两种选择，加上差值或者减去差值，无效状态也很多，时间上是能够接受的。需要注意的是，可以将最高位重复若干次，这样会产生前导0，magic一次就消去了。
下面的代码是BFS套DFS版本的。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

LL a, b, ans;
std::queue<LL> que;

inline void dfs(LL magic, LL real, LL digit) {
    if(real > b) return;
    if(!magic) {
        int lst = real * 10 / digit;
        if(!lst) return;
        dfs(magic, real + lst * digit, digit * 10);
        if(real >= a && real <= b) ans++;
        if(digit < b) que.push(real);
        return;
    }
    int lst = real * 10 / digit, nxt = magic % 10;
    if(lst - nxt >= 0) dfs(magic / 10, real + (lst - nxt) * digit, digit * 10);
    if(nxt && lst + nxt <= 9) dfs(magic / 10, real + (lst + nxt) * digit, digit * 10);
}

int main() {
    a = readint(); b = readint();
    if(a <= 7 && b >= 7) ans++;
    que.push(7);
    while(!que.empty()) {
        for(int i = 0; i <= 9; i++) {
            dfs(que.front(), i, 10);
        }
        que.pop();
    }
    printf("%lld", ans);
    return 0;
}