P2540. 靠谱的车

解题思路

从 A 进制到九进制

假设这种特殊的进制规则（逢 4 跳过）我们将其称之为 A 进制。

容易发现，在 A 进制 中，每一个数位实际上只有 9 个数字，即 0-3 和 5-9。 对于 九进制 而言，我们每一个数位也只有 9 个数字，即 0-8。

另外，A 进制 是 逢 9 进位（但逢 4 跳过），九进制 是 逢 8 进位。

显然，A 进制 和 九进制 之间映射关系是非常明显的：

• A 进制 的 0-3 对应着 九进制 的 0-3
• A 进制 的 5-9 对应着 九进制 的 4-8

因此，如果我们想令 A 进制 转化为 九进制 的话，只需要枚举每一个数位 digit，当这个数位 digit 大于等于 5 时，将其 -1 即可变成 九进制 的数位。即：

从九进制到十进制

2024/01/20 真题讲解中对于题目【模拟】2024D-来自异国的客人，我对进制转换做了比较详细的介绍。

当我们已经得到了该数字在 九进制 下的结果后，再将其转化为 十进制 就非常轻松了。 根据算法题中常用数学概念、公式、方法汇总中的相关概念，我们知道如果要将 m 进制 转化为 十进制，需要将 m 进制 下给定的数字 按权展开，每一位乘以对应位置的权重。比如将 九进制 下的 1230 转化为 十进制 的 918：

由于权重的幂是从低位开始从 0 不断增加，所以我们可以先对原 九进制 的数字进行 反转 再 正序遍历，就实现了从低位遍历了。即：

最终输出 ans 即可。

复杂度分析 设 L 为计费表读数的位数（输入字符串 num_str 的长度）。算法先把字符串反转以便从低位开始处理，O(L)；然后用一个 for 循环从低位到高位逐位处理，每一位做的事情是：取出数字、按「A 进制转九进制」的映射规则对大于等于 5 的数位减一、再乘上权重 9i 累加进答案，循环共执行 L 次。若把每次幂运算 9i 记为常数操作，总时间复杂度就是 O(L)；严格来说 9**i 的计算量会随 i 增大而增加，把这部分也计入的话上界约为 O(L²)，但计费表读数的位数很小，实际完全可以当作线性。整个算法的瓶颈就在这个逐位换算的循环上，没有嵌套循环，也不需要额外的数据结构。空间方面，反转字符串会生成一个长度为 L 的新串，空间复杂度为 O(L)，此外只用了 ans、digit 等常数个变量。