洛谷 AT_abc192_d 题解
\(66pts\)
其实我也不知道为什么考场上会想出 dfs 这种做法（严格来说应该不算），但是最后的分数还是比较可观的。
主要思路
首先，将 \(X\) 视为一个 \(n\) 进制数 \(X'\)。
枚举 \(n\) 进制，从字符串 \(X\) 中的最大数字加 \(1\) 开始。在此过程中，如果 \(X'\) 比 \(M\) 大就输出。
评测结果
\(44\) 测试点；
\(29\) AC，\(14\) TLE，\(1\) WA；
\(66pts\)。
Code1
时间复杂度
我不会算
貌似算不了。
如有人会算，欢迎私信我。
\(91 pts\)
考试之后，我对于 \(66pts\) 很不满足，于是在教练讲之前，随便瞎改，得到了 \(77pts\)。
讲完，我觉得不服，没打正解。随后，在原来 \(66pts\) 的基础上，加了对于个位数以及其他的特判，得到了 \(91pts\)。
特判的原因
这是为了避免超时。
因为第 \(1\) 行的数，如果是个位数，且 \(M\) 比第 \(1\) 行的数要大。那么此时无论如何，在 \(n\) 进制下的数值都是它本身，dfs 就会由于 \(n\) 进制可以无限大，而超时。
感谢zhangzhengyan0831的反馈。
评测结果
\(44\) 测试点；
\(40\) AC，\(4\) TLE；
\(91pts\)。
时间复杂度
我不会算
貌似还是算不了。
如有人会算，欢迎私信我。
Code2
\(100 pts\)
后来，看到那无药可救的 TLE。
我陷入了沉思......
于是，按照教练讲的正解思路：二分，打了 \(1\) 遍，然后过了。
主要思路
首先，套个二分模板。
然后，判断将 \(n\) 进制数 \(X\) 转为 \(10\) 进制后是否小于或者等于 \(M\)；
如果小了，就往大的进制走，也就是 left=mid；
如果大了，就往小的进制走，也就是 right=mid-1；
全剧终。
评测结果
\(44\) 测试点；
\(44\) AC；
共 \(100pts\)。
Code3
时间复杂度
\(O{( \log{M} \times \left| X \right| )}\)。
成功抢到最优解
