#广搜，深搜#洛谷 1822 魔法指纹

本文主要是介绍#广搜，深搜#洛谷 1822 魔法指纹，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

将$n$按十进制顺序写下来，依次对相邻两个数写下差的绝对值。这样，得到了一个新数，去掉前导0，则定义为$magic(n)$。若$n$为一位数，则$magic(n)=n$。

---

分析

首先肯定是从7开始搜索，然后对于每一个可能的结果，枚举差的绝对值，深搜求解

---

代码

#include <cstdio>
#include <queue>
#define rr register
using namespace std;
int l,r,ans; queue<int>q;
inline void dfs(int x,long long y,int pows){if (y>r) return;if (!x){rr int last=y/(pows/10);if (!last) return;dfs(x,y+(long long)last*pows,pows*10);if (y>=l&&y<=r) ++ans;if (pows<r) q.push(y);return;}rr int last=y/(pows/10),next=x%10;x/=10;if (last>=next) dfs(x,y+(long long)pows*(last-next),pows*10);if (next&&last+next<10) dfs(x,y+(long long)pows*(last+next),pows*10);
}
signed main(){scanf("%d%d",&l,&r);q.push(7);if (l<=7&&r>=7) ++ans;while (q.size()){for (rr int i=0;i<10;++i)dfs(q.front(),i,10);q.pop();}return !printf("%d",ans);
} 

这篇关于#广搜，深搜#洛谷 1822 魔法指纹的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---