「SiR-1」Popsicle

Hisaishi_Kanade · 2023-05-15 21:39:11 · 题解

Problem

因为是 A 题还是写一下吧。

• 给你一个数 n。
• 一次操作给 n 的某个数位 -1，并立刻去掉所有前导 0。
• 一次 trick 在某个时刻改变 n 的某个数位。
• 对于所有可能的 trick 情况，求最优策略下把 n 删完的操作次数的最大值。
• 多组数据，1 \leq T \leq 3333，1 \leq n \leq 10^{13} - 1。
• 嗯对，搬的讲评。

Solution

事实上，在没有 trick 的时候，样例解释已经给出了提示，答案为 n 的数位和。

如果有 trick，要求最优策略下最大，显然 trick 尽可能会让 0 \rightarrow 9，这样答案会 +9。

这样过了第一组样例，但是没过第二组样例。怎么会事呢？

注意到无论怎么删都肯定会在最后一步产生一个 1，所以 trick 带来的贡献至少是 1 \rightarrow 9 即 8。

由于时刻删除前导 0，可以选择从前往后每次只删最高位，这样 在原数没有 \bm 0 时 不可能在过程中产生任何 0。

在这时给答案 +8 即可。

时间复杂度 \mathcal O(T\log n)。