AtCoder Beginner Contest 379
Rated： \(770\)
-
A - Cyclic
简单模拟。
-
B - Strawberries
字符串模拟，
substr函数秒了 -
C - Repeating
中等模拟。
思路：判断是否合法很简单，重点在计算花费。
假设我们是 \(0\) 号点有 \(N\) 个棋子，然后移动到每个点上，显然花费为 \(\frac{N(N+1)}{2}\)
但是现在棋子不在 \(0\) 好点上，如果有一个 \(A_i\) 这个地方有 \(B_i\) 个棋子，那么就会省去 \(A_i \times B_i\) 的花费。
接下来排序，简单模拟即可。 -
D - Home Garden
priority_queue + lazy_tag
-
E - Sum of All Substrings
拆贡献法，第 \(i\) 个数的数为 \(a_i\)，那么它左边选择的值会增加 \(i\) 种情况，而右边对答案产生 \(10^0+10^1+10^2+\cdots+10^{n-i}\) 的贡献，
第 \(i\) 位的总花费就是 \(\sum_{j=1}^{N-i}i\times 10^j \times a_i\) 相当于给高精度的数 \(0 \sim N-i\) 位加上 \(i\times a_i\)
差分处理，再处理一下进位即可点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n;
long long ans[300001],c[200001];
char s[200001];
bool st;
int main(){
scanf("%d%s",&n,s + 1);
for(int i = 1;i <= n;i ++){
c[i] = i * (s[i] - '0');
}
for(int i = n;i;i --){
ans[i] = ans[i + 1] + c[n - i + 1];//差分
}
for(int i = 1;i < 300000;i ++){//进位
ans[i + 1] += ans[i] / 10;
ans[i] = ans[i] % 10;
}
for(int i = 300000;i;i --){
if(ans[i]){//去除前导零
st = true;
}
if(st){
printf("%lld",ans[i]);
}
}
return 0;
}
```