题解 P1822 【魔法指纹】

_rqy · 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;
}