E. Final Countdown - 题解

比赛与标签

比赛: Codeforces Round 927 (Div. 3) 标签: implementation, math, number theory, *1600 难度: *1600

题目大意喵~

有一台由 n 个数字指示器组成的倒计时器，初始显示一个大数 S。当倒计时从 x 变为 x-1 时，所花费的时间等于 x 和 x-1 之间发生变化的数字位数。比如说，从 42 变到 41，只有个位数变了，所以花费 1 秒。但是从 2300 变到 2299，有三位数字都变了（百位、十位、个位），所以要花费 3 秒。

我们的任务是，计算出从当前显示的数字 S 倒计时到 0，总共需要花费多少时间，的说喵~

思路分析喵~

这道题看起来有点复杂，但只要我们静下心来分析一下，就会发现其中的规律，呐！

1. 核心思想

问题的核心是计算从 S 到 0 的总耗时。总耗时就是把从 S 减到 S-1，再从 S-1 减到 S-2，...，一直到从 1 减到 0 的所有耗时加起来。

总时间 = $\sum_{i=1}^{S} \text{cost}(i \to i-1)$

所以，我们首先要搞清楚 cost(i -> i-1) 是怎么计算的，喵~

2. 关键观察

让我们来观察一下数字变化带来的耗时：

如果一个数 i 的个位数不是 0（比如 123），那么 i-1（就是 122）只改变了个位数。所以耗时是 1。
如果一个数 i 的个位数是 0（比如 120），那么 i-1（就是 119）会发生连锁反应。个位的 0 变成 9，十位的 2 变成 1。这里有两位变化了，耗时是 2。
如果一个数 i 的末尾有 k 个 0（比如 2300，末尾有 2 个 0），那么 i-1（就是 2299）会改变末尾的 k 个 0（都变成 9），以及前面的那一位数字。总共有 k+1 位数字变化了，耗时就是 k+1。

总结一下，cost(i -> i-1) 其实就等于 1 + (数字 i 末尾 0 的个数)。

那么总时间就是： $\text{TotalTime} = \sum_{i=1}^{S} (1 + \text{数字 i 末尾 0 的个数})$

这个公式可以拆成两部分： $\text{TotalTime} = \sum_{i=1}^{S} 1 + \sum_{i=1}^{S} (\text{数字 i 末尾 0 的个数})$

第一部分 $\sum_{i=1}^{S} 1$ 很简单，就是 S 本身嘛。第二部分 $\sum_{i=1}^{S} (\text{数字 i 末尾 0 的个数})$ 是什么呢？

末尾至少有一个 0 的数，是 10 的倍数。在 1 到 S 之间有 $\lfloor S/10 \rfloor$ 个。
末尾至少有两个 0 的数，是 100 的倍数。在 1 到 S 之间有 $\lfloor S/100 \rfloor$ 个。
...以此类推。

所以，第二部分的总和就是 $\lfloor S/10 \rfloor + \lfloor S/100 \rfloor + \lfloor S/1000 \rfloor + \dots$

把两部分加起来，总时间就是： $\text{TotalTime} = S + \lfloor S/10 \rfloor + \lfloor S/100 \rfloor + \dots$

喵~！这个形式是不是很眼熟？如果 S 是一个字符串 "s_0s_1...s_{n-1}"，那么：

S 就是数字 "s_0s_1...s_{n-1}"
$\lfloor S/10 \rfloor$ 就是把 S 的最后一位去掉，也就是数字 "s_0s_1...s_{n-2}"
$\lfloor S/100 \rfloor$ 就是把 S 的最后两位去掉，也就是数字 "s_0s_1...s_{n-3}"
...

所以，总时间就是 S 的所有前缀代表的数字之和！例如 S = 123，总时间就是 123 + 12 + 1。

3. 算法流程

既然 S 的长度可以达到 4 * 10^5，这显然是一个超大的数，我们不能用 long long 直接存。必须使用高精度加法来处理，的说。

我们要计算 S 的所有前缀之和。就像我们做小学竖式加法一样，把所有要加的数对齐，从右往左一列一列地加，喵~

举个例子，S = "4567"。我们要计算 4567 + 456 + 45 + 4。

  4567
+  456
+   45
+    4
-------

我们来按列相加：

个位：7 + 6 + 5 + 4 = 22。这一列的和就是 S 的所有数字之和。
十位：6 + 5 + 4 = 15。这一列的和是 S 从第一位到倒数第二位数字之和。
百位：5 + 4 = 9。
千位：4 = 4。

我们可以发现一个规律：

第 k 列（从右往左，0-indexed）的数字和，等于 S 的前 n-k 个数字的和。
为了方便计算，我们可以先预处理出 S 的数字前缀和数组 prefix_sums，其中 prefix_sums[i] 表示 S 的前 i+1 个数字的和。

算法步骤如下：

读入字符串 S 和它的长度 n。
计算数字前缀和数组 prefix_sums。prefix_sums[i] = digit(S[0]) + ... + digit(S[i])。
模拟手动加法。我们从右到左（从个位开始）计算结果。
- 设置一个进位 carry = 0。
- 循环 i 从 n-1 到 0：
  - 当前列的总和是 prefix_sums[i] + carry。
  - 结果的这一位是 (prefix_sums[i] + carry) % 10。
  - 新的进位是 (prefix_sums[i] + carry) / 10。
  - 把计算出的结果位加到一个结果字符串中（注意这时结果是反的）。
循环结束后，如果 carry 还有值，也要加到结果字符串的末尾。
最后，把结果字符串反转过来，就得到正确的答案啦！
输出前要去掉可能存在的前导零（虽然这题基本不会有，但这是高精度计算的好习惯）。

这样，我们就能在 O(n) 的时间内解决这个问题了，是不是很巧妙呀，喵~

代码实现

cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

// 处理单个测试用例的函数，喵~
void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    // 计算数字字符串s的前缀和
    // prefix_sums[i] 存储从 s[0] 到 s[i] 的数字之和
    std::vector<long long> prefix_sums(n);
    prefix_sums[0] = s[0] - '0';
    for (int i = 1; i < n; ++i) {
        prefix_sums[i] = prefix_sums[i - 1] + (s[i] - '0');
    }

    std::string result_rev = ""; // 用来反向存储结果字符串
    long long carry = 0; // 进位

    // 总时间是 S 所有前缀所代表的数字之和。
    // 我们用竖式加法来模拟这个过程，从右往左一列一列地加。
    // 从右边数第 k+1 列 (k=0,1,...) 的数字和，正好是 s 的前 n-k 个数字的和，也就是 prefix_sums[n-1-k]。
    // 我们让 i 从 n-1 减到 0，就相当于从右往左遍历每一列。
    for (int i = n - 1; i >= 0; --i) {
        long long current_col_sum = prefix_sums[i] + carry;
        result_rev += std::to_string(current_col_sum % 10); // 当前位是总和模10
        carry = current_col_sum / 10; // 新的进位是总和除以10
    }

    // 处理最后可能剩下的进位
    while (carry > 0) {
        result_rev += std::to_string(carry % 10);
        carry /= 10;
    }

    // 结果是反着构造的，所以需要反转一下得到最终答案
    std::reverse(result_rev.begin(), result_rev.end());
    
    // 去掉最终结果可能存在的前导零
    // 题目保证了输入不为0，所以结果肯定大于0
    size_t first_digit_pos = result_rev.find_first_not_of('0');
    if (std::string::npos != first_digit_pos) {
        std::cout << result_rev.substr(first_digit_pos) << "\n";
    } else {
        // 这个分支在题目限制下其实是走不到的
        // 为了代码的健壮性，如果结果是 "0" 或 "00..."，就输出 "0"
        std::cout << "0\n";
    }
}

int main() {
    // 快速 I/O，让程序跑得更快一点，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

时间复杂度: O(N) 的说。其中 N 是数字字符串的长度。我们需要 O(N) 的时间来计算前缀和，O(N) 的时间来进行竖式加法，处理最后的进位和反转字符串的时间都小于等于 O(N)。所以总的时间复杂度是线性的，非常高效！
空间复杂度: O(N) 的说。我们需要 O(N) 的空间来存储输入的字符串 s，O(N) 的空间来存储前缀和数组 prefix_sums，以及 O(N) 的空间来存储结果字符串。

知识点总结

解决这个问题，我们主要用到了这些可爱的知识点，的说喵~

数学观察/问题转化: 将复杂的耗时计算规则，通过分析和归纳，转化为一个简洁的数学形式（所有前缀之和）。
前缀和: 一个非常实用的小技巧，可以快速计算任意区间的和。在这里，它帮助我们快速得到每一列的数字总和。
高精度加法: 当数字大到无法用标准整型存储时，用字符串和模拟手动计算的方式来进行运算。

希望这篇题解能帮到你，一起享受解题的乐趣吧，喵~！

E. Final Countdown - 题解 ​

比赛与标签 ​

题目大意喵~ ​

思路分析喵~ ​

1. 核心思想 ​

2. 关键观察 ​

3. 算法流程 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​