自动搬运

查看原文

来自洛谷，原作者为

	_rqy **

搬运于2025-08-24 21:30:42，当前版本为作者最后更新于2017-12-26 13:09:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

不明白为什么这题会被扔到“分块”里。

说一下我的做法（顺带一提，目前AC代码中除了打表的之外只有两个，另一个既看不明白有编译不过）。

首先写个暴力，可以发现$A=1,B=10^7$的时候答案也只有三万多。

我们考虑如果有一个图，每个顶点有一个数，然后从$magic[x]$到$x$连边，那么显然某个数的魔法指纹是$7$当且仅当从$7$可以到达它。那么我们从$7$开始广搜（图并不用实际建出来）。

广搜每次拓展时我们需要从$a$出发拓展出所有$magic[b]=a$的$b$。考虑枚举$b$的个位，那么因为$b$的十位与个位差的绝对值是$a$的个位，所以$b$的十位至多有两种可能；同理，确定$b$的十位后，其百位数至多有两种可能...如此做下去，最后最多拓展出$2^l$个数，其中$l$是$a$的位数。但实际上几乎不可能有那么多数，因为许多选择会使某一位上的数不在$[0,9]$范围内（实际上，如果$b$的前两位不等，容易证明$magic[b]\leq10^l\Rightarrow b\leq 10^{l+1}$，于是平均每个数能扩展出$10$个数）。这个过程可以$dfs$实现。

不过要注意一点：由于求$magic[b]$的定义是相邻两项取绝对值再去掉前导零，所以由$magic[b]$求$b$的时候可能要把$b$的最高位重复几遍，这样求出的$magic$不变（因为只是多了前导零）。

代码：

#include <algorithm>
#include <cstdio>
typedef long long LL;
bool mm[10000050];
int p[10], A, B;
int queue[40000], num, head, tail;
void dfs(int x, LL y, int p10) {
  if (y > B) return;
  if (x == 0) {
    int last = y / (p10 / 10);
    if (!last) return;
    dfs(x, y + (LL)last * p10, p10 * 10);
    if (y >= A && y <= B) ++num;
    if (p10 < B) queue[tail++] = y;
    return;
  }
  int last = y / (p10 / 10), nxt = x % 10;
  x /= 10;
  if (last - nxt >= 0) dfs(x, y + p10 * (last - nxt), p10 * 10);
  if (nxt && last + nxt < 10) dfs(x, y + p10 * (last + nxt), p10 * 10);
}
int main() {
  scanf("%d%d", &A, &B);
  head = tail = num = 0;
  queue[tail++] = 7;
  if (A <= 7 && B >= 7) ++num;
  do
    for (int i = 0; i < 10; ++i)
      dfs(queue[head], i, 10);
  while (++head < tail);
  printf("%d\n", num);
  return 0;
}