自动搬运

查看原文

来自洛谷，原作者为

	I4ever 他将蔑视命运，唾斥生死，超越一切的情理，排斥一切的疑惑，执着他的不可能的希望。

搬运于2025-08-24 23:00:22，当前版本为作者最后更新于2024-10-17 14:57:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P10697 [SNCPC2024] 消失的数字

题目分析

• 统计 $1 \sim n$ 中所有不包含 x 的数字个数，任何一位都不可以有。数据范围给的很大，已经爆 int 了所以不考虑使用暴力求解，看到很多题解包括标签都是数位 dp ，本蒟蒻不会那么高深的算法，那么开始模拟找规律这道题与P1590 失踪的7可以说是一摸一样，是个双倍经验。

• 先手模找规律

1  2  3  4  5  6  8  9  10
11 12 13 14 15 16 18 19 20
21 22 23 24 25 26 28 29 30
31 32 33 34 35 36 38 39 40
41 42 43 44 45 46 48 49 50
51 52 53 54 55 56 58 59 60
61 62 63 64 65 66 68 69 80
81 82 83 84 85 86 88 89 80
91 92 93 94 95 96 98 99 100

这是 $1 \sim 100$ 的消失 $7$ 的表格，共有 $81$ 个数字。

而 $1 \sim 10$ 的有 $9$ 个数字。（自己算）

那么可以将 $100$ 分成 $10$ 个 $1 \sim 10$ ，因为其中有 $70 \sim 79$ 以及每一个 $1 \sim 10$ 中会有一个 $7$ 不符合条件，所以 $100 \rightarrow 9\times9=81$。

则可推出 $1000 \rightarrow 81\times9=729$。

那么就可以手动计算将其存贮到数组中，打个比方，将 $abcdefg$ 变成 $a\times1000000 + b\times100000 + c\times10000 + d\times1000 + e\times100 + f\times10 + g\times1$，对于每一位数字单独进行计算，最后累加即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
template <typename T> void read(T &x) {
	int f = 1;
	x = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) {
		if (c == '-') {
			f = -f;
		}
	}
	for (; isdigit(c); c = getchar()) {
		x = x * 10 + c - '0';
	}
	x *= f;
}
//预处理每个数位上所代表的数字个数
ll a[19] = {1, 9, 81, 729, 6561, 59049, 531441, 4782969, 43046721, 387420489, 3486784401, 31381059609, 282429536481, 2541865828329, 22876792454961, 205891132094649, 1853020188851841, 16677181699666569, 150094635296999121};
ll T, n, x, ans, dep;
int main() {
	read(T);
	while (T--) {
		ans = dep = 0;
		read(n);
		read(x);
		while (n) {//逐位计算
			int num = n % 10;
			n /= 10;
			if (num < x) {
				ans += num * a[dep];
			} else {
				ans += (num - 1) * a[dep];
			}
			dep++;
		}
		printf("%lld\n", ans + 1);
	}
	return 0;
}