[dfs] 洛谷 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]中有多少个数是幸运数。

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

1
9

输出样例#1：

说明

数据范围：

对30%数据，B≤10000。

对100%数据，0<A≤B≤1,000,000,000。

题解

首先，我们可以反过来从7开始
我们可以考虑枚举个位，然后十位与个位的差的绝对值就是7对吧，这样的话我们就可以拓展出两个数
以此类推，那么确定十位就会有百位也是拓展出两个数，这样的话最多就是拓展出2^n个数
但是这不可能拓展满，因为对于有些数拓展后可能上一位的数字会不在[0...9]范围内
那么对于这个过程，我们可以用dfs来实现

代码

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #define ll long long
 5 using namespace std;
 6 int A,B,Q[40010],ans,head,tail;
 7 void dfs(int x,ll y,int k)
 8 {
 9     if (y>B) return;
10     if (x==0)
11     {
12         int last=y/(k/10);
13         if (!last) return;
14         dfs(x,y+(ll)last*k,k*10);
15         if (y>=A&&y<=B) ans++;
16         if (k<B) Q[tail++]=y;
17         return;
18     }
19     int last=y/(k/10),p=x%10;
20     x/=10;
21     if (last-p>=0) dfs(x,y+k*(last-p),k*10);
22     if (p&&last+p<10) dfs(x,y+k*(last+p),k*10);
23 }
24 int main()
25 {
26     scanf("%d%d",&A,&B),Q[tail++]=7;
27     if (A<=7&&B>=7)    ans++;
28     do
29         for (int i=0;i<10;i++) dfs(Q[head],i,10);
30     while (++head<tail);
31     printf("%d",ans);
32 }