【题解】AT_abc192_d [ABC192D] Base n
YuYuanPQ
·
·
题解
洛谷 AT_abc192_d 题解
66pts
其实我也不知道为什么考场上会想出 dfs 这种做法（严格来说应该不算），但是最后的分数还是比较可观的。
主要思路
首先，将 X 视为一个 n 进制数 X'。
枚举 n 进制，从字符串 X 中的最大数字加 1 开始。在此过程中，如果 X' 比 M 大就输出。
评测结果
$29$ `AC`，$14$ `TLE`，$1$ `WA`；
$66pts$。
### Code1
[云剪贴板链接](https://www.luogu.com.cn/paste/y1ioga6l)
### 时间复杂度
~~我**不会**算~~
貌似**算不了**。
如有人会算，欢迎[私信我](https://www.luogu.com.cn/chat?uid=1029900)。
## $91 pts
考试之后，我对于 66pts 很不满足，于是在教练讲之前，随便瞎改，得到了 77pts。
讲完，我觉得不服，没打正解。随后，在原来 66pts 的基础上，加了对于个位数以及其他的特判，得到了 91pts。
特判的原因
这是为了避免超时。
因为第 1 行的数，如果是个位数，且 M 比第 1 行的数要大。那么此时无论如何，在 n 进制下的数值都是它本身，dfs 就会由于 n 进制可以无限大，而超时。
感谢zhangzhengyan0831的反馈。
评测结果
$40$ `AC`，$4$ `TLE`；
$91pts$。
### 时间复杂度
~~我**不会**算~~
貌似还是**算不了**。
如有人会算，欢迎[私信我](https://www.luogu.com.cn/chat?uid=1029900)。
### Code2
[云剪贴板链接](https://www.luogu.com.cn/paste/8x02vc09)
## $100 pts
后来，看到那无药可救的 TLE。
我陷入了沉思......
于是，按照教练讲的正解思路：二分，打了 1 遍，然后过了。
主要思路
首先，套个二分模板。
然后，判断将 n 进制数 X 转为 10 进制后是否小于或者等于 M；
如果小了，就往大的进制走，也就是 left=mid；
如果大了，就往小的进制走，也就是 right=mid-1；
全剧终。
评测结果
$44$ `AC`；
共 $100pts$。
### Code3
[云剪贴板链接](https://www.luogu.com.cn/paste/08nyy772)
### 时间复杂度
$O{( \log{M} \times \left| X \right| )}$。
### 成功抢到[**最优解**](https://www.luogu.com.cn/record/list?pid=AT_abc192_d&orderBy=1&status=&page=1)
[](https://www.luogu.com.cn/record/list?pid=AT_abc192_d&orderBy=1&status=&page=1)
# 另附
- 前 $2$ 种非正解解法的评测结果在我校评测平台上，正解评测结果在洛谷和我校评测平台均有。
- [题目链接](https://www.luogu.com.cn/problem/AT_abc192_d)
- 如有**更好**做法，欢迎[私信我](https://www.luogu.com.cn/chat?uid=1029900)。
- [我的提交记录](https://www.luogu.com.cn/record/list?pid=AT_abc192_d&user=1029900)
- 这是我第 $7$ 次写题解，如有错误请**指出**。