[洛谷1822]魔法指纹 题解

[洛谷1822]魔法指纹 题解

题目地址:洛谷:【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到109之间每\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;
}


发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据