A.Move Brackets

https://qycode64.com/course/6a478a5569fcccaa3fd46c88/exam/6a771c5f205105c2c1b0a20c/problem/CF1374C?lang=zh

题意：给定一个长度为n的括号序列s，且s中恰好2/n个左括号 (和n/2个右括号 )输出s变为合法括号序列所需的最少操作次数。

思路：合法括号序列的充要条件：左右括号数量相等（题目已满足）任意前缀中左括号数 ≥ 右括号数（即前缀和永远非负）操作的本质：将括号移到开头，相当于在最前面插入一个括号（左括号或右括号）将括号移到结尾，相当于在最后面插入一个括号

关键结论：

最少操作次数 = 最小前缀和（负值）的绝对值

即 ans = -min_prefix_sum

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,b=0,mn=0;
		string s;
		cin>>n>>s;
		for(int i=0;i<n;i++){
			if(s[i]=='(')b++;
			else b--;
			mn=min(mn,b);
		}
		cout<<-mn<<"\n";
	}
	return 0;
}

B.And It's Non-Zero

https://qycode64.com/course/6a478a5569fcccaa3fd46c88/exam/6a771c5f205105c2c1b0a20c/problem/CF1615B?lang=zh

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	vector<vector<int>>p(31,vector<int>(200006,0));
	for(int b=0;b<31;b++){
		for(int i=1;i<=200006;i++){
			p[b][i]=p[b][i-1]+((i>>b)&1);
		}
	}
	int t;
	cin>>t;
	while(t--){
		int l,r;
		cin>>l>>r;
		int zx=r-l+1,mx=0;
		for(int b=0;b<31;b++){
			int cnt=p[b][r]-p[b][l-1];
			mx=max(mx,cnt);
		}
		cout<<zx-mx<<"\n";
	}
	return 0;
}

C.Iva & Pav

https://qycode64.com/course/6a478a5569fcccaa3fd46c88/exam/6a771c5f205105c2c1b0a20c/problem/CF1878E

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	int t;cin>>t;
	while(t--){
		int n;
		cin>>n;
		vector<int>a(n+1);
		for(int i=1;i<=n;i++)cin>>a[i];
		vector<vector<int>>p(31,vector<int>(n+1,0));
		for(int b=0;b<31;b++){
			for(int i=1;i<=n;i++)p[b][i]=p[b][i-1]+((a[i]>>b)&1);
		}
		int q;cin>>q;
		while(q--){
			int l,k;
			cin>>l>>k;
			int z=l,y=n,ans=-1;
			while(z<=y){
				int mid=(z+y)/2,asval=0;
				for(int b=0;b<31;b++){
					if(p[b][mid]-p[b][l-1]==mid-l+1){
						asval |= (1<<b);
					}
				}
				if(asval>=k){
					ans=mid;
					z=mid+1;
				}
				else y=mid-1;
			}
			cout<<ans<<" ";
		}
		cout<<"\n";
	}
	return 0;
}

D.Number of Ways

https://qycode64.com/discuss/6a784404205105c2c1b0ecda/edit

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	vector<long long>a(n+1),s(n+1);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	if(s[n]%3){
		cout<<0;
		return 0;
	}
	long long t=s[n]/3,ans=0,c=0;
	for(int i=1;i<n;i++){
		if(s[i]==t*2)ans+=c;
		if(s[i]==t)c++;
	}
	cout<<ans;
	return 0;
}

E.Xor-Subsequence (easy version)

https://qycode64.com/course/6a478a5569fcccaa3fd46c88/exam/6a771c5f205105c2c1b0a20c/problem/CF1720D1

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		vector<int>a(n);
		for(int i=0;i<n;i++)cin>>a[i];
		vector<int>dp(n,1);
		int ans=1;
		for(int i=0;i<n;i++){
			for(int j=max(0,i-300);j<i;j++){
				if((a[j]^i)<(a[i]^j)){
					dp[i]=max(dp[i],dp[j]+1);
				}
			}
			ans=max(ans,dp[i]);
		}
		cout<<ans<<"\n";
	}
	return 0;
}

F.Shuffling Songs

https://qycode64.com/course/6a478a5569fcccaa3fd46c88/exam/6a771c5f205105c2c1b0a20c/problem/CF1950G

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--){
		int n;cin>>n;
		vector<string>g(n),w(n);
		for(int i=0;i<n;i++)cin>>g[i]>>w[i];
		vector<vector<int>>e(n,vector<int>(n,0));
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				if(g[i]==g[j]||w[i]==w[j])e[i][j]=e[j][i]=1;
			}
		}
		vector<vector<int>>dp(1<<n,vector<int>(n,-1));
		int ans=0;
		for(int i=0;i<n;i++){
			dp[1<<i][i]=1;
			ans=max(ans,1);
		}
		for(int i=0;i<(1<<n);i++){
			for(int j=0;j<n;j++){
				if(dp[i][j]==-1)continue;
				ans=max(ans,dp[i][j]);
				for(int k=0;k<n;k++){
					if(i&(1<<k))continue;
					if(e[j][k])dp[i|(1<<k)][k]=max(dp[i|(1<<k)][k],dp[i][j]+1);
				}
			}
		}
		cout<<n-ans<<"\n";
	}
	return 0;
}