题解 P1590 【失踪的7】
dbxxx
·
·
题解
原来的题解因为叙说很云里雾里，代码过于追求简短而忽略可读性，现重写此篇题解。
我的思路是这样的：
首先对于给定的数的某一位，引入一个概念：贡献值。（自己创造的概念，并非官方）
设这一位所在位数为 x（从低位到高位数），上面的值为 v，那么这一位的贡献值：
- 如果 v < 7，那么这一位的贡献值为 v \times 9^{x-1};
- 如果 v > 7，那么这一位的贡献值为 (v - 1) \times 9^{x-1}
做出了如上定义之后，一个不含 7 的数字对应的答案就是每一位的贡献值之和。
接下来以 n = 5482 为例（注意 n 中不可含有 7，含有 7 的情况稍后会处理），说明该算法是如何工作的。
首先我们运用位值原理，将 5482 拆分为 5000 + 400 + 80 + 2
那么实际上，1 \sim 5482 中所有 Pascal 数的总数，第一步就被我们拆分为：0 \sim 4999；5000 \sim 5399；5400 \sim 5479；5480 \sim 5481。
不知道到了这里你会不会萌生这样一个困惑：你是不是多算了一个 0 呀？你是不是少算了一个 5482 呀？
事实上，0 是 Pascal 数，5482 也是 Pascal 数，少算一个，多算一个，最后统计出的数据仍然是准确的。
解答你的疑惑后，我们继续再来分步处理这些部分：
**考虑使用乘法原理**：$5 \times 9 \times 9 \times 9$。这就是$0 \sim 4999$ Pascal 数的数量了。
那么，$5000 \sim 5399$ Pascal 数的数量是多少呢？第一个数只能取 $5$，不用考虑（或者考虑为 $1$ 种情况，最后乘法时不影响）；第二个数可以从 $0$ 取到 $3$，总共有 $4$ 种情况；第三个数 $9$ 种；第四个数 $9$ 种。
最后就是 $3 \times 9 \times 9$。
不知道你发没发现这样一个规律：分步考虑后，每一位（值为 $v$）对应区间内 Pascal 数的数量其实就是：$v$（从 $0$ 取到 $v - 1$ 共 $v$种情况），乘上后面位数数量的 $9$。也就应了刚刚那个**贡献值的第一个式子**。
现在你明白了吗？所谓贡献值其实就是每一位对应区间内 Pascal 数的数量。这个区间的映射关系，是通过拆分实现的。
到第三位开始情况有了变化：变化在于这一位上是 $8$，但这一位的取值范围不再是 $0 \sim 8$，**因为 $7$ 也是需要扣去的！！**
最后第一位就变成了 $v - 1$ 种情况，乘法原理时相应也需要是 $v - 1$ 与那么多 $9$ 相乘。应了刚刚**贡献值的第二个式子**。
第四位后面就没有位数了，所以直接就是 $v$，不用乘 $9$，也可以说是乘 $9^0$（ $=1$ ）。
最后把每一位的贡献值相加，自然就是最终结果啦。
---
什么？结束了吗？
不要忘了，数里边含有 $7$ 的情况，我们还需要拯救一下！
事实上，只需要在事前加这样一个小特判：**从最高位往下扫，如果遇到 $7$，那么这一位变成 $6$，之后所有位都变成 $9$。**
事实上道理也很简单，举个简单例子便可说明：**$1 \sim 5700700$ 的所有 Pascal 数的数量其实和 $1 \sim 5699999$ 是一样的。毕竟，$5700000 \sim 5700700$ 的所有数都不是 Pascal 数。**
---
代码：
```cpp
#include <bits/stdc++.h>//万能头
int T;
std :: string s;
//这道题推荐字符串存储，因为要取的是每一位的值，且不涉及到整个数字的数字运算
int main() {
std :: scanf("%d", &T);
while (T--) { //多组数据测试时推荐这么写！
std :: cin >> s;
//特判开始
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '7') {
s[i] = '6';//先把这一位标记为6
for (int j = i + 1; j < s.length(); ++j)
s[j] = '9';//之后所有标记为9
break; //跳出特判循环，这个 break 实际上很重要，不可省略
//因为 700700 要变成 699999 而不是 699699
}
}
//特判结束，正片开始
int ans = 0; //初始化ans
for (int i = s.length() - 1, atr = 1; i >= 0; --i, atr *= 9)
ans += atr * (s[i] - '0') - (s[i] - '0' > 7 ? atr : 0);
//重头戏！s[i] - '0' 就是 i 这一位代表的数字。
//先根据贡献原理加贡献，然后再判断是否大于7
//如果大于 7，那么扣除 atr，总体也就相当于 (s[i] - '0' - 1) * atr，合理
//如果不大于 7，那么扣除 0，也就是不扣除。
std :: printf("%d\n", ans); //输出答案
}
return 0;
}
```