Throne

序列更新

给定两个长度为n 的序列$ 𝑎_0,𝑎_1,…,𝑎_{𝑛−1}$ 和 $𝑏_0,𝑏_1,…,𝑏_{𝑛−1}$

你需要依次执行q次操作，每次操作将会给出一个整数$k(0≤𝑘<𝑛)$，对于每个$ 𝑖 (0≤𝑖<𝑛)$，你需要将 $𝑎𝑖$ 更新为 $max⁡(𝑎_𝑖,𝑏_{𝑖+𝑘}\ mod\ 𝑛)。$为了证明你确实维护了a序列，请在每次操作之后输出 $\sum_{i=0}^{i<n}a_i $的值。

迟来的第一周总结…

第一周一共四场比赛：总的来说还有很多东西没学，或者学的不深，个人感觉八月之前应该在不停的学新东西了，八月之后得对算法加深一些理解和掌握。比赛得时候，签到和能出得思维大家都一样，后期就看谁知识点学过或者掌握的更深了…

sdf dsf

学习了一下强连通分量，整理一下：

最近的一些比赛中经常用到树上$lca$的常见模型，整理一下：

Problem - I - step

题目Problem - B. Countless Me- Codeforces：

题目（Problem - D2. Reverse Card (Hard Version）- Codeforces）：

vector<PII>e[N];
int n,m,c,minn,dist[N];
bool st[N];
void Dijkstra(int u){
	minn=1e18;
	for(int i=1;i<=n;i++)dist[i]=1e18,st[i]=0;
	priority_queue<PII,vector<PII>,greater<PII> >q;
	dist[u]=0;
	q.push({dist[u],u});
	while(q.size()){
		auto [dis,ver]=q.top();
		q.pop();
		if(st[ver])continue;
		st[ver]=1;
		for(auto [v,w]:e[ver]){
			if(v==u)minn=min(minn,dis+w);
			if(st[v])continue;
			if(dist[v]>dis+w){
				dist[v]=dis+w;
				q.push({dist[v],v});
			}
		}
	}
}
void solve(){
	cin>>n>>m>>c;
	int ans=0;
	for(int i=1;i<=m;i++){
		int u,v,z;cin>>u>>v>>z;
		e[u].pb({v,z});
		if(z<=c)ans=1;
	}
	for(int i=1;i<=n;i++){
		Dijkstra(i);
		if(minn<=c){ans=2;break;}
	}
	cout<<ans<<"\n";
}

Problem - 1946DBirthday Gift

题面：

分析：

对于区间位运算容易想到拆位，对x进行从高位到低位拆位分析：

1.当$i$位为0时如果数组所有元素的第i位一共有奇数个1,那么无论怎么分配，总有一个段内有奇数个1，异或后结果为1，显然导致整体大于x。

2.当i位为0时如果有偶数个1，此时只能就近两两一组去保证异或为0还有组数最多，同时。

3.当i位为1时如果有奇数个1，此时不做任何处理，只能一段一个1.

4.当i位为1时如果有偶数个1，那么两两一组既能保证异或为0，还能保证组数最多，并且此时分组个数可以直接作为答案的一种取max，当然如果每个单独一组不做处理那么数组间异或结果为1，虽然此时不能当作答案，但是之后的数组的分配可能有更多的答案个数，所以也要把不做处理的情况传递下取去。

因为在第4个情况的时候，我们总是不做处理传递下去，并没有真正的处理x当前位相等的情况。所以我们对x进行+1，那么即使传递下去相等情况，那么也可以取答案。

代码：