传送门：洛谷 Vlad and a Sum of Sum of Digits | Codeforces C. Vlad and a Sum of Sum of Digits

更佳的阅读体验：CF1926C 题解

简要题意：给定多个 $n$，询问 $1$ 到 $n$ 的所有数字的数位之和。

如果我们对于每次询问都暴力地求解，那么时间消耗将非常巨大。不难想到，对于每个 $n$，它的答案都是唯一的。

注意到，$1$ 到 $n$ 的所有数字的数位和，一定是 $1$ 到 $n - 1$ 的所有数字的数位和，加上 $n$ 的数位和，答案具有显然的递推关系。

考虑递推预处理。由于 $n$ 的范围只有 $2 \times 10^5$，在程序开始时暴力地计算 $n$ 的值为 $1$ 到 $2 \times 10^5$ 的答案进行预处理即可。

#include <iostream>
using namespace std;
using ll = long long;

const int N = 2e5 + 10;
int t, n, a[N], sum, tmp;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    for (int i = 1; i < N; ++i) {
        tmp = i, sum = 0;
        while (tmp) sum += tmp % 10, tmp /= 10;
        a[i] += a[i - 1] + sum;
    } for (cin >> t; t; --t) {
        cin >> n;
        cout << a[n] << '\n';
    } return 0;
}