P8431 「WHOI-2」彗星蜜月

__ryp__ · 2024-06-30 19:40:03 · 个人记录

知道两个做法。

第一个做法好想，我们设 g(x) 表示 [1, x] 中最大的翻转数，g 单增显然，并且可以构造出来，类似数位 DP。然后二分就可了。

第二个做法，把原问题转化为找最小的 k 使得 f(k) \gt n，答案就是 k - 1。这个好构造。我们考虑 f(k) 一定是某一位比 n 恰好大一，否则不优，然后这一位下面的所有数都是零；同时，最后一位必须不是零。

我们枚举这一位，然后算一下就可以了。