atcoder 专项2

有些题其实都挺有价值的，搞得我都想每个都单独建随笔，但是这样还是太多太乱了，之前那个难度较低，部分题甚至可以直接删除，遂新开一个 2 记录更高质量的题目。

[ABC379E] Sum of All Substrings

看到有思路但是想到要用高精度就头疼，但是这题并没有用到很复杂的高精度，相反甚至更像是一个技巧性的东西。

第i位的数会在这位计算 \(i\) 次，在之后也会再作为每一位计算 \(i\) 次，所以我们数组每一位存储前缀和，这一位的和的结果就是 \(f_i%10\)，然后我们再进位。

#include <bits/stdc++.h>
#define int long long
#define re register 
const int N=2e5+100;
using namespace std;
int n;
string s;
int a[N]; 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
	cin>>n;
	cin>>s;
	for(int i=0;i<n;i++){
		int x=s[i]-'0';
		a[i]+=a[i-1];
		a[i]+=x*(i+1);
	}
	string ans="";
	int sum=0;
	for(int i=n-1;i>=0||sum>0;i--){
		sum+=a[i];
		ans+=sum%10+'0';
		sum/=10;
	}
	for(int i=ans.size()-1;i>=0;i--){
		cout<<ans[i];
	}
	return 0;
}

[ABC379C] Sowing Stones

仔细读题啊！！每个位置都只有一个石子，不能有多余，然后唐的没边，这样的话就可以从后向前填然后等差数列区间快速填，真是无语了。

[ABC380D] Strange Mirroring

还得是找规律题啊，我还是看不出来，给你你看看能看出来吗，aB、Ab、AbaB、AbaBaBAb，不可以看出下标为 \(i\) 的字符经过 \(k\) 次变化为 \(i-n\times 2^{k-1}\) 的字符取反。

然后这就是个倍增题了，不断乘 \(2\) 直到大于下标，

[ABC378F] Add One Edge 2

感觉是个套路题，以后可能会遇到吗，要求连边的两个端点度数必须为 \(2\)，两点之间的点的度数必须为 \(3\)，度数为 \(3\) 的点组成一个连通分量，连通分量连接的所有点都可以相互到达，好了没了。

[ARC159D] LIS 2

其实挺简单，想到了，甚至感觉贪心可做，其实就只有重叠和比他小的右两种情况，直接值域线段树即可秒掉。

如果没有顺序就确实可以贪心，但是有顺序就要用到无后效性的 dp 了。

[ABC353G] Merchant Takahashi

虽然并不难，但是挺有教育意义的，终点是按顺序到达，所以我们可以从这个位置之前和之后来到 \(f_i\)，所以维护线段树即可转移过来，区间最大值和单点修改。

感觉好像 dp 具有顺序性，其实也叫无后效性？？？

F - Bread

陷入正向思维误区了，总是想如何分，没想到如何合并，其实就是合并果子的模板题，剩下的面包额外看成一个人。

[AGC008B] Contiguous Repainting

结论题，最后总有一段长度为 \(k\) 的区间染成黑色或白色，其余颜色随便填，这样就很好做了，但我以为是 dp，发现 dp 根本不可做。

维护前缀正数和后缀正数和及前缀和求区间。