题目传送门:E - Σ[k=0..10^100]floor(X/10^k) (atcoder.jp)
题目大意
顾名思义,求这么一坨东西。

思路
看到这个数据肯定要想用高精度。
而且不能用暴力算法去算这个东西,要想一个O(N)复杂度可以解决的,这就要去找规律了。
我们将所有要加起来的东西竖着写,会得到一个“阵”,暂且叫数阵吧。
这个数阵是沿着副对角线对称的,而每一位上(比如个位,十位)的和,是有递推关系的,可以考虑从后往前(从个位到最高位),以此加入到高精度数组中,再进行一次进位后输出。

代码
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e6 + 10, N = 1e6 + 5; int a[maxn], pa = 0; signed main() { string s;cin >> s; int sum = 0; for(auto& i : s)sum += i - '0'; int len = s.length(); for(int i = len - 1;i >= 0; -- i) { a[++ pa] = sum; sum -= s[i] - '0'; } for(int i = 1;i <= N; ++ i) { if(a[i] > 9) { a[i + 1] += a[i] / 10; a[i] %= 10; } } for(int i = N, f = 0;i >= 1; -- i) { if(a[i]) f = 1; if(f)printf("%lld",a[i]); } return 0; }
Comments NOTHING