[开发测试]codeforces round #738

A. Mocha and Math

题目大意：
给一个数组，可以取任意一个子区间，对区间内的所有数做按位与运算，求最后整个数组的最小值。
解析：贪心算法，直接求所有数的按位与。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
int main(){
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		int ans=0;
		cin>>ans;
		for( int i=1;i<=n-1;i++){
			int temp;
			cin>>temp;
			ans=ans&temp;
		}
		cout<<ans<<endl;
	}

B. Mocha and Red and Blue

题目大意：
给定一个字符串，其中包含B和R两个状态，还有？带表没有确定的状态，将？改为确定状态，使最后RR和BB子串的数量最少
解析：
贪心算法，前一个使R后一个就是B；前一个是B后一个就是R

#include<bits/stdc++.h>
using namespace std;
#define N 200100
int t;
int main(){
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		string s;
		cin>>s;
		int cnt=0;
		for( int i=0;i<n;i++){
			if(s[i]=='?') cnt++;
		}
		if(cnt==n) {
			s[0]='R';
			cnt--;
		}//特判全是问号的情况 
		for( int i=0;i<n-1;i++){
			if(s[i]!='?'&&s[i+1]=='?'){
				if(s[i]=='R') s[i+1]='B';
				else s[i+1]='R';
			}
		}
		for( int i=n-1;i>=1;i--){
			if(s[i]!='?'&&s[i-1]=='?'){
				if(s[i]=='R') s[i-1]='B';
				else s[i-1]='R';
			}
		}
		cout<<s<<endl;
	}
}

C. Mocha and Hiking

题目大意：
给出一个图，图有n+1个点，第i个点和第i+1个点之间有单向边，i属于[1,n-1]而且每个点都有一条与n+1点相连的单向边，求一个路径经过所有点。
解析：
将第n+1个点插入前面n个点的序列中

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 10010
int t;
int a[N];
int main(){
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		for( int i=1;i<=n;i++){
			cin>>a[i];
		}
		if(a[1]==1){
			cout<<n+1<<" ";
			for( int i=1;i<=n;i++){
				cout<<i<<" ";
			}
			cout<<endl;
			continue;
		}
		if(a[n]==0){
			for( int i=1;i<=n+1;i++){
				cout<<i<<" ";
			}
			cout<<endl;
			continue;
		}
		int rem=0;
		int flag=0;
		for( int i=1;i<=n-1;i++){
			if((a[i]^a[i+1])==1&&flag==0){
				flag=1;
				rem=i;
			}
		}
		if(flag==0){
			cout<<-1<<endl;
			continue;
		}
		else {
			for( int i=1;i<=n;i++){
				
				cout<<i<<" ";
				if(i==rem){
					cout<<n+1<<" ";
				}
			}
			cout<<endl;
		}
		
	}
}

D. Mocha and Diana

题目大意：
现在存在两个图，两个图有相同的点和不同的边。
在两个图中添加相同的边，保证两个图形成无环图。最多可以添加多少条边？
解析：
使用并查集首先找一个原点，把所有点中满足“两个图中都不与原点连通的点”
和原点相连。
之后再遍历一下原点以外的所有点，将分别满足以下两条件之一的两点相连。
1.在A图中与原点相连，而在B图中与原点不相连
2.在B图中与原点相连，而在A图中与原点不相连

#include<bits/stdc++.h>
using namespace std;
#define N 201000
int bin[N];
int height[N];//注意需要初始化为0
int findd(int x){//查找根节点 
    int next=x;
    while(bin[next]!=next)
        next=bin[next];
    return next;
}
void merge(int x,int y){//合并的优化
    y=findd(y);
    x=findd(x);
    if(height[x]==height[y]){
        height[x] = height[y] +1;
        bin[y]=x;
} 
else{
 		if(height[x]<height[y]) bin[x]=y;
		else bin[y]=x;
	}
} 
int rem[100100];
int cnt=0;
int main(){
	int n,m1,m2;
	cin>>n>>m1>>m2;
    for( int i=1;i<=n*2;i++)
        bin[i]=i;
    for( int i=1;i<=m1;i++){
    	int a,b;
    	cin>>a>>b;
    	merge(a,b);
	}
	for( int i=1;i<=m2;i++){
		int a,b;
		cin>>a>>b;
		merge(a+n,b+n);
	}
	int now=1;
	int ans=0;
	for( int i=1;i<=n;i++){
		if(findd(now)!=findd(i)&&findd(now+n)!=findd(i+n)){
			merge(now,i);
			merge(now+n,i+n);
			ans++;
			rem[++cnt]=now;
			rem[++cnt]=i;
		}
	}
	stack<int>aaa;
	stack<int>bbb;
	for( int i=1;i<=n;i++){
		if(findd(now)!=findd(i)&&findd(now+n)==findd(i+n)){
			aaa.push(i);
			if(!bbb.empty()){
				int tp=bbb.top();
				bbb.pop();
				if(findd(tp)!=findd(i)&&findd(tp+n)!=findd(i+n)){
					merge(tp,i);
					merge(tp+n,i+n);
					ans++;
					rem[++cnt]=tp;
					rem[++cnt]=i;
					aaa.pop();
				}
			}
		}
		if(findd(now)==findd(i)&&findd(now+n)!=findd(i+n)){
			bbb.push(i);
			if(!aaa.empty()){
				int tp=aaa.top();
				aaa.pop();
				if(findd(tp)!=findd(i)&&findd(tp+n)!=findd(i+n)){
					merge(tp,i);
					merge(tp+n,i+n);
					ans++;
					rem[++cnt]=tp;
					rem[++cnt]=i;
					bbb.pop();
				}
			}
		}
	}
	if(ans==0) {
		cout<<0<<endl;
		return 0;
	}
	else{
		cout<<ans<<endl;
		for( int i=1;i<=cnt;i+=2){
			cout<<rem[i]<<" "<<rem[i+1]<<endl;
		}
	}
}