洛谷题目连接:魔法指纹
题目描述
对于任意一个至少两位的正整数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]中有多少个数是幸运数。
输入输出格式
输入格式：
输入两行，每行一个数。第一行是A，第二行表示B。
输出格式：
输出[A,B]中有多少个数是幸运数。
输入输出样例
输入样例#1：
1
9
输出样例#1：
1
说明
数据范围：
对30%数据，B≤10000。
对100%数据，0<A≤B≤1,000,000,000。
一句话题意: 根据描述的方法来转换数字,最后转换到只剩下个位的时候判断这个数字是否能计入答案.
题解: 首先看这数据范围,10个亿??这显然是一个玄学的复杂度.我们先考虑如何暴力来算.
- 最朴素的算法,直接枚举\(a\)~\(b\)的每一个数字验证,复杂度\(O(n*len)\),\(len\)为数字最大位数,也就是10.
- 考虑优化一下暴力,加上一个记忆化搜索, 复杂度\(O(n*k)\), k是一个小于等于10的常数.
显然如果要枚举的话,得到的复杂度至少也是\(O(n)\)的,所以才说这个小于\(O(n)\)的复杂度很玄学,所以我们还得再优化.
正解:分块+打表
可以考虑直接将整块内的答案通过另一个程序打出来,然后暴力统计不在整块内的,直接加整块内的答案.
打表的话就直接用一个什么暴力算一下就可以了.
#include<bits/stdc++.h>
using namespace std;
int block;
int n, num[20], ans[40000] = {/*这里实在是太多了就不贴了*/};
int magic(int x){
if(x < 10) return x == 7 ? 1 : -1;
int cnt = 0, res = 0;
for(;x;x/=10) num[++cnt] = x%10;
for(int i=1;i<=cnt/2;i++) swap(num[i], num[cnt-i+1]);
for(int i=2;i<=cnt;i++) res = res*10+abs(num[i]-num[i-1]);
return magic(res);
}
int B(int pos){return (pos-1)/block+1;}//计算一个位置属于哪个块
int main(){
//freopen("data.in", "r", stdin);
//freopen("zuoti.out", "w", stdout);
int a, b, res = 0; cin >> a >> b;
block = 31662+1;//对10亿开根的结果
for(int i=a;i<=min(b, B(a)*block);i++)
if(magic(i) == 1) res++;
for(int i=B(a)+1;i<=B(b)-1;i++) res += ans[i];
for(int i=(B(b)-1)*block+1;i<=b && B(a) != B(b);i++)
if(magic(i) == 1) res++;
printf("%d\n", res);
return 0;
}