[洛谷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;
}