CF244B Undoubtedly Lucky Numbers 题解
myster1ous
·
·
题解
题目传送门
题目大意
如果一个数仅包含由 x,y 构成则称这个数为幸运数字。（x 可以等于 y，0 \le x, y \le 9，幸运数字不包含前导零，幸运数字均为正整数。）
问有多少个幸运数字不超过 n。
数据范围
## 题目解法
最朴素的解法就是直接枚举 $i = 1 \to n$，判断 $i$ 是否是幸运数字，判断一次时间复杂度为 $\mathcal{O}(\log_{10} n)$，总时间复杂度 $\mathcal{O}(n \log_{10} n)$，明显过不了。
可以发现，幸运数字其实在 $n = 10^9$ 时很稀疏，实际 $10^9$ 以内只有不到 $5 \times 10^4$ 的幸运数字。
所以，我们可以构造幸运数字。
首先枚举 $x,y$，然后再深搜，每一次深搜都要搜到小于等于 $n$ 且仅有 $x,y$ 组成的幸运数字。
深搜时，记录现在构造出的幸运数字 $m$，如果 $m$ 已经超过了 $n$ 则返回，否则继续向 $m \times 10 + x$ 和 $m \times 10 + y$ 深搜。
小细节：因为 $x,y$ 和 $y,x$ 构造出的幸运数字完全一样，所以我们默认 $y \le x$。
如果 $x = y = 0$ 就无法构造出任何合法的幸运数字。
该算法时间复杂度为 $\mathcal{O}(k)$，$k$ 是幸运数字的个数，之所以是这个复杂度是因为几乎每次进入深搜函数都可以搜出来一个幸运数字。
注意，因为 $n$ 为 $10^9$ 量级时，有可能会爆 `int`，出现负数，然后就会死循环。如果不开 `int64/ll` 的话会在 $\#6$ 超时。
## 完整代码
```cpp
// CF244B Code by luogu|528472
#include <algorithm>
#include <iostream>
#include <unordered_set>
#define int int64_t
int n, ans;
std::unordered_set<int> s; // 为了判重用了 unordered_set
void Search(int, int, int);
signed main() {
std::cin >> n;
for (int x = 0; x <= 9; x++)
for (int y = 0; y <= x; y++)
if (x != y or y != 0)
Search(x, y, 0);
std::cout << s.size() << "\n";
return 0;
}
void Search(int n, int m, int now) {
if (now > ::n)
return ;
if (now != 0) {
s.insert(now);
Search(n, m, now * 10 + n);
Search(n, m, now * 10 + m);
} else { // 如果现在搜出来的幸运数字等于零，也就是还没有开始搜索，就只能进入到没有前导零的分支中去。
if (n != 0)
Search(n, m, now * 10 + n);
if (m != 0)
Search(n, m, now * 10 + m);
}
}
```