E. Final Countdown

题目描述：E. Final Countdown

解题思路

解题思路

1、题目大意：给一个数字(如 $12345$)，每次将其 $-1$，每次的代价为发生变化的数位个数，如 $12340$ 发生变化变为 $12339$ 时，代价为 $2$。求出数字变为 $0$ 之前的总代价
2、分析可知，以 $12345$ 为例：其个位变化了 $12345$ 次，十位变化了 $1234$ 次，百位变化了 $123$ 次……所以总代价为 $12345 + 1234 + 123 + 12 + 1 = 13715$
3、但题目的数据范围较大，直接相加会超出数据范围。此时可能会想到用高精度，但高精度每次计算都是 $O(n)$，又有 $n$ 次运算，复杂度达到 $O(n^2)$ 会超时
4、找到规律：如果将要加的数按照竖式右对齐列出，则不难发现答案中，个位 $= 1 + 2 + 3 + 4 + 5$，十位 $= 1 + 2 + 3 + 4$，以此类推。显然，如果将 $n$ 从高位向低位编号，答案的第 $i$ 位 = $n$ 从第 $1$ 位到第 $i$ 位的各数位数字之和，这样的区间和可以使用前缀和 $sum[1, i]$ 优化
5、再类比高精度的思想，$\bmod 10$ 保留第 $i$ 位的结果，$\div10$ 向上一位进位，其余按照高精度的方式操作即可

代码实现

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 4e5 + 10;

int prefix[N]; // 即 sum[1, i]

void solve()
{
    int n;
    cin >> n;
    char s[N]; // 存储数字
    for (int i = 1; i <= n; i++)
        cin >> s[i];

    // 处理前缀和
    prefix[0] = 0;
    for (int i = 1; i <= n; i++)
        prefix[i] = prefix[i - 1] + s[i] - '0'; // 统计从第 1 位到第 i 位的各数位数字之和

    // 类比高精度，处理进位和数位
    for (int i = n; i >= 1; i--)
    {
        prefix[i - 1] += prefix[i] / 10;
        prefix[i] %= 10;
    }

    // 输出答案
    bool flag = false;
    for (int i = 0; i <= n; i++)
    {
        if (prefix[i] || flag)
        {
            flag = true;
            cout << prefix[i];
        }
    }
    cout << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

题目描述：E. Final Countdown

解题思路

代码实现

页底评论