Final Countdown

题面翻译

你有一个 $n$ 位显示屏，现在上面显示一个 $n$ 位数 $k$，每次 $k$ 减少 $1$。

但是由于显示屏沉迷于舒克贝塔而十分颓废，所以从 $k$ 变成 $k-1$ 时，每一位的变化都需要分别花费 $1$ 的时间，换句话说，从 $k$ 变成 $k-1$，需要的时间被定义为发生变化的数位数量。如 $23000$ 变为 $22999$ 需要的时间为 $4$，$10$ 变为 $09$ 的时间为 $2$。

$t$ 组数据，每一组数据给定 $n$ 和 $k$，求出 $k$ 达到 $0$ 需要的时间。

$t \le 10^4$，$\sum n \le 4 \times 10^5$。

题目描述

You are in a nuclear laboratory that is about to explode and destroy the Earth. You must save the Earth before the final countdown reaches zero.

The countdown consists of $ n $ ( $ 1 \le n \le 4 \cdot 10^5 $ ) mechanical indicators, each showing one decimal digit. You noticed that when the countdown changes its state from $ x $ to $ x-1 $ , it doesn’t happen in one move. Instead, each change of a single digit takes one second.

So, for example, if the countdown shows 42, then it will change to 41 in one second, because only one digit is changed, but if the countdown shows 2300, then it will change to 2299 in three seconds, because the three last digits are changed.

Find out how much time is left before the countdown reaches zero.

输入格式

The first line of input contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Then the descriptions of the test cases follow.

The first line of each test case contains a single integer $ n $ ( $ 1\le n\le 4\cdot 10^5 $ ).

The second line contains a string of $ n $ digits, the current state of the countdown. It is guaranteed that at least one digit is not zero.

The sum of $ n $ for all tests does not exceed $ 4\cdot 10^5 $ .

输出格式

For each test case, print a single integer without leading zeroes, the number of seconds left before the countdown reaches zero. Note that this number may be huge.

样例 #1

样例输入 #1

5
2
42
5
12345
2
99
4
0005
27
456480697259671309012631002

样例输出 #1

46
13715
108
5
507200774732968121125145546

提示

In the first example, there are four changes that take 2 seconds: 40 to 39, 30 to 29, 20 to 19, and 10 to 09, other changes take 1 second each. So the total time is $ 2\cdot 4 + 1\cdot(42-4) = 46 $ .

可以发现，数上每一位可以算贡献，比如12345，最高位的贡献是1，第二位的贡献是12，第三位的贡献是123，最后一位的贡献是12345，那么就是1+12+123+1234+12345，所以就是

12345
..1234
....123
......12
........1

这样加起来，先求前缀和，从最低位开始，ans加上当前的前缀和，就是这一位的贡献，这一位先%10存到答案数组，再除10，留给下一位

const int N = 4e5 + 10;
int a[N];
char os[N];
void solve()
{
    int n; cin >> n;
    string s; cin >> s;
    s = " " + s;
    for (int i = 1; i <= n; i++)
    {
        a[i] = a[i - 1] + s[i] - '0';
    }
    int ans = 0;
    for (int i = n; i >= 1; i--)
    {
        ans += a[i];
        os[i] = (char)('0' + (ans % 10));
        ans /= 10;
    }
    string ss = to_string(ans);
    if (ans)
    {
        cout << ss;
        for (int i = 1; i <= n; i++) cout << os[i];
        cout << '\n';
    }
    else
    {
        int ok = 0;
        for (int i = 1; i <= n; i++)
        {
            if (os[i] != '0') ok = 1;
            if (ok) cout << os[i];
        }
        cout << '\n';
    }
    for (int i = 1; i <= n; i++) a[i] = 0;
}