[开发测试]Codeforces Round #738 (Div. 2) 2021.08.16

Codeforces Round #738 (Div. 2)

闲话：手速场，题区分度有点差。前四题比较简单就简单说一下。

A. Mocha and Math

因为操作次数是任意的，每次一个数&上另一个数肯定是会变小的，那么最小值就是所有数&起来。

代码：

https://codeforces.com/contest/1559/submission/125947426

/*
 * @Autor: violet apricity (zpx)
 * @Date: 2021-07-22 22:06:15
 * @LastEditors: violet apricity (zpx)
 * @LastEditTime: 2021-08-14 23:21:30
 * @FilePath: \apricity\cf.cpp
 * @Description: Violet acm && Apricity:/ The warmth of the sun in the winter /
 */


        // violet apricity
        // Do all I can do.Do good to be good.
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>
#include<sstream>
#include<numeric>
#include<queue>
#include<iomanip>
#include<fstream>
#include<unordered_map>
#include<stack>
#include<set>
#include<random>

//#include<bits/stdc++.h>

#define ll long long
#define db double
#define ldb long double
#define IOS std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);
#define MAX 88888888
#define INF 0x3f3f3f3f
#define r0 return 0;
#define SYP system("pause");
//#define endl '\n'
using namespace std;

ll gcd(ll a,ll b){ll d;while(b){d=b;b=a%b;a=d;}return a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll _pow(ll a,ll b){ll d=1;while(b){if(b&1)d*=a;a*=a;b>>=1;}return d;}
ll mpow(ll a,ll b,ll m){ll d=1;while(b){if(b&1)d=(d*(a%m))%m;a=((a%m)*(a%m))%m;d%=m;b>>=1;}return d%m;}

//#define int long long

//=====================================================================

const int N=2e5+10;
const ll mod=1e9+7;
/*
ll jie[N];
ll tow[N];
void init()
{
    jie[0]=1;
    for(int i=1;i<N;i++)jie[i]=jie[i-1]*i%mod;
    tow[N-1]=mpow(jie[N-1],mod-2,mod);
    for(int i=N-2;i>=0;i--) tow[i]=tow[i+1]*(i+1)%mod;
}
ll cal(ll n,ll m)
{
    if(m>n) return 0;
    return jie[n]*tow[m]%mod*tow[n-m]%mod;
}
*/

//=====================================================================

#define pcase(t,d) cout<<"Case #"<<(t)<<": "<<(d)<<'\n'
#define pno cout<<"NO\n"
#define pyes cout<<"YES\n"
#define pdebug(ans) cout<<"ans:"<<(ans)<<'\n'
#define pshow(x) cout<<" show:"<<(x)<<'\n'
#define p(ans) cout<<(ans)<<'\n'
#define pdec(t,ans) cout<<std::fixed<<std::setprecision(t)<<(ans)<<'\n'

//=====================================================================

//=====================================================================

ll a[1001],b[1001];

int main()
{
#ifdef LOCAL
    //ifstream cin("E:\\ACMdream\\in.txt");
    //ofstream cout("E:\\ACMdream\\out.txt");
    freopen("E:\\ACMdream\\in.txt","r",stdin);
    freopen("E:\\ACMdream\\out.txt","w",stdout);
#endif
    IOS

    //======================================================================

    int t =1 ;
    cin >> t ;
    while (t--) {
        int n;cin>>n;
        vector<int>v(n+1);
        for(int i=1;i<=n;i++){
            cin>>v[i];
        }
        int ans=v[1];
        for(int i=2;i<=n;i++)ans=ans&v[i];
        p(ans);
    }

    //======================================================================

    //SYP
    return 0;
}

B. Mocha and Red and Blue

暴力贪心。对？填颜色就是和相邻的颜色不一样。

代码：

https://codeforces.com/contest/1559/submission/125970495

/*
 * @Autor: violet apricity (zpx)
 * @Date: 2021-07-22 22:06:15
 * @LastEditors: violet apricity (zpx)
 * @LastEditTime: 2021-08-14 23:21:30
 * @FilePath: \apricity\cf.cpp
 * @Description: Violet acm && Apricity:/ The warmth of the sun in the winter /
 */


        // violet apricity
        // Do all I can do.Do good to be good.
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>
#include<sstream>
#include<numeric>
#include<queue>
#include<iomanip>
#include<fstream>
#include<unordered_map>
#include<stack>
#include<set>
#include<random>

//#include<bits/stdc++.h>

#define ll long long
#define db double
#define ldb long double
#define IOS std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);
#define MAX 88888888
#define INF 0x3f3f3f3f
#define r0 return 0;
#define SYP system("pause");
//#define endl '\n'
using namespace std;

ll gcd(ll a,ll b){ll d;while(b){d=b;b=a%b;a=d;}return a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll _pow(ll a,ll b){ll d=1;while(b){if(b&1)d*=a;a*=a;b>>=1;}return d;}
ll mpow(ll a,ll b,ll m){ll d=1;while(b){if(b&1)d=(d*(a%m))%m;a=((a%m)*(a%m))%m;d%=m;b>>=1;}return d%m;}

//#define int long long

//=====================================================================

const int N=2e5+10;
const ll mod=1e9+7;
/*
ll jie[N];
ll tow[N];
void init()
{
    jie[0]=1;
    for(int i=1;i<N;i++)jie[i]=jie[i-1]*i%mod;
    tow[N-1]=mpow(jie[N-1],mod-2,mod);
    for(int i=N-2;i>=0;i--) tow[i]=tow[i+1]*(i+1)%mod;
}
ll cal(ll n,ll m)
{
    if(m>n) return 0;
    return jie[n]*tow[m]%mod*tow[n-m]%mod;
}
*/

//=====================================================================

#define pcase(t,d) cout<<"Case #"<<(t)<<": "<<(d)<<'\n'
#define pno cout<<"NO\n"
#define pyes cout<<"YES\n"
#define pdebug(ans) cout<<"ans:"<<(ans)<<'\n'
#define pshow(x) cout<<" show:"<<(x)<<'\n'
#define p(ans) cout<<(ans)<<'\n'
#define pdec(t,ans) cout<<std::fixed<<std::setprecision(t)<<(ans)<<'\n'

//=====================================================================

//=====================================================================

ll a[1001],b[1001];

int main()
{
#ifdef LOCAL
    //ifstream cin("E:\\ACMdream\\in.txt");
    //ofstream cout("E:\\ACMdream\\out.txt");
    freopen("E:\\ACMdream\\in.txt","r",stdin);
    freopen("E:\\ACMdream\\out.txt","w",stdout);
#endif
    IOS

    //======================================================================

    int t =1 ;
    cin >> t ;
    while (t--) {
        string s;int n;cin>>n;cin>>s;
        int be=0;
        for(be=0;be<n;be++){
            if(s[be]!='?')break;
        }
        int d=be;
        if(be!=n){{
            for(be=be-1;be>=0;be--){
                if(s[be+1]=='R')s[be]='B';
                else s[be]='R';
            }
        }
        for(d=d+1;d<n;d++){
            if(s[d]!='?')continue;
            else {if(s[d-1]=='R')s[d]='B';
                else s[d]='R';}
        }
        cout<<s<<'\n';}
        else {for(int i=0;i<n;i++){
            if(i&1)cout<<"B";else cout<<"R";
        }
            cout<<'\n';
        
        }
    }

    //======================================================================

    //SYP
    return 0;
}

C. Mocha and Hiking

考虑到1到n都是可以直接一边走的，那么考虑第n+1个点如何加入即可。

分出三种情况：

1.n+1—>1

2.n-------->n+1

3.k---->n+1----->k+1

代码：

https://codeforces.com/contest/1559/submission/125990350

/*
 * @Autor: violet apricity (zpx)
 * @Date: 2021-07-22 22:06:15
 * @LastEditors: violet apricity (zpx)
 * @LastEditTime: 2021-08-15 23:47:59
 * @FilePath: \apricity\cf.cpp
 * @Description: Violet acm && Apricity:/ The warmth of the sun in the winter /
 */


        // violet apricity
        // Do all I can do.Do good to be good.
//g++  ./violet/run.cpp -o ./violet/run.exe
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>
#include<sstream>
#include<numeric>
#include<queue>
#include<iomanip>
#include<fstream>
#include<unordered_map>
#include<stack>
#include<set>
#include<random>

//#include<bits/stdc++.h>

#define ll long long
#define db double
#define ldb long double
#define IOS std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);
#define MAX 88888888
#define INF 0x3f3f3f3f
#define r0 return 0;
#define SYP system("pause");
//#define endl '\n'
using namespace std;

ll gcd(ll a,ll b){ll d;while(b){d=b;b=a%b;a=d;}return a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll _pow(ll a,ll b){ll d=1;while(b){if(b&1)d*=a;a*=a;b>>=1;}return d;}
ll mpow(ll a,ll b,ll m){ll d=1;while(b){if(b&1)d=(d*(a%m))%m;a=((a%m)*(a%m))%m;d%=m;b>>=1;}return d%m;}

//#define int long long

//=====================================================================

const int N=2e5+10;
const ll mod=1e9+7;
/*
ll jie[N];
ll tow[N];
void init()
{
    jie[0]=1;
    for(int i=1;i<N;i++)jie[i]=jie[i-1]*i%mod;
    tow[N-1]=mpow(jie[N-1],mod-2,mod);
    for(int i=N-2;i>=0;i--) tow[i]=tow[i+1]*(i+1)%mod;
}
ll cal(ll n,ll m)
{
    if(m>n) return 0;
    return jie[n]*tow[m]%mod*tow[n-m]%mod;
}
*/

//=====================================================================

#define pcase(t,d) cout<<"Case #"<<(t)<<": "<<(d)<<'\n'
#define pno cout<<"NO\n"
#define pyes cout<<"YES\n"
#define pdebug(ans) cout<<"ans:"<<(ans)<<'\n'
#define pshow(x) cout<<" show:"<<(x)<<'\n'
#define p(ans) cout<<(ans)<<'\n'
#define pdec(t,ans) cout<<std::fixed<<std::setprecision(t)<<(ans)<<'\n'

//=====================================================================

//=====================================================================
const int maxn=1e4+3;
ll a[maxn];
int main()
{
#ifdef LOCAL
    //ifstream cin("E:\\ACMdream\\in.txt");
    //ofstream cout("E:\\ACMdream\\out.txt");
    freopen("E:\\ACMdream\\in.txt","r",stdin);
    freopen("E:\\ACMdream\\out.txt","w",stdout);
#endif
    IOS

    //======================================================================

    int t =1 ;
    cin >> t ;
    while (t--) {
        int n;cin>>n;
        int x=0,y=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(i>1){
                if(a[i-1]==0&&a[i]==1)x=i-1,y=i;
            }
        }
        if(a[1]==1){
            cout<<n+1<<' ';
            for(int i=1;i<=n;i++)cout<<i<<' ';
            cout<<'\n';
        }
        else if(a[n]==0){
            for(int i=1;i<=n;i++)cout<<i<<' ';
                        cout<<n+1<<' ';
            cout<<'\n';
        }
        else {
            for(int i=1;i<=n;i++){
                if(i==y)cout<<n+1<<' ';
                cout<<i<<' ';
            }
            cout<<'\n';
        }
    }

    //======================================================================

    //SYP
    return 0;
}

D1. Mocha and Diana (Easy Version)

两个并查集，O(n^2)暴力查询，当两个点对于两个图都不在一个集合即可加入答案。

代码：

https://codeforces.com/contest/1559/submission/126006807

/*
 * @Autor: violet apricity (zpx)
 * @Date: 2021-07-22 22:06:15
 * @LastEditors: violet apricity (zpx)
 * @LastEditTime: 2021-08-16 00:23:56
 * @FilePath: \apricity\cf.cpp
 * @Description: Violet acm && Apricity:/ The warmth of the sun in the winter /
 */


        // violet apricity
        // Do all I can do.Do good to be good.
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>
#include<sstream>
#include<numeric>
#include<queue>
#include<iomanip>
#include<fstream>
#include<unordered_map>
#include<stack>
#include<set>
#include<random>

//#include<bits/stdc++.h>

#define ll long long
#define db double
#define ldb long double
#define IOS std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);
#define MAX 88888888
#define INF 0x3f3f3f3f
#define r0 return 0;
#define SYP system("pause");
//#define endl '\n'
using namespace std;

ll gcd(ll a,ll b){ll d;while(b){d=b;b=a%b;a=d;}return a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll _pow(ll a,ll b){ll d=1;while(b){if(b&1)d*=a;a*=a;b>>=1;}return d;}
ll mpow(ll a,ll b,ll m){ll d=1;while(b){if(b&1)d=(d*(a%m))%m;a=((a%m)*(a%m))%m;d%=m;b>>=1;}return d%m;}

//#define int long long

//=====================================================================

const int N=2e5+10;
const ll mod=1e9+7;
/*
ll jie[N];
ll tow[N];
void init()
{
    jie[0]=1;
    for(int i=1;i<N;i++)jie[i]=jie[i-1]*i%mod;
    tow[N-1]=mpow(jie[N-1],mod-2,mod);
    for(int i=N-2;i>=0;i--) tow[i]=tow[i+1]*(i+1)%mod;
}
ll cal(ll n,ll m)
{
    if(m>n) return 0;
    return jie[n]*tow[m]%mod*tow[n-m]%mod;
}
*/

//=====================================================================

#define pcase(t,d) cout<<"Case #"<<(t)<<": "<<(d)<<'\n'
#define pno cout<<"NO\n"
#define pyes cout<<"YES\n"
#define pdebug(ans) cout<<"ans:"<<(ans)<<'\n'
#define pshow(x) cout<<" show:"<<(x)<<'\n'
#define p(ans) cout<<(ans)<<'\n'
#define pdec(t,ans) cout<<std::fixed<<std::setprecision(t)<<(ans)<<'\n'

//=====================================================================

const int maxn=1e3+2;
int father1[maxn];   
int father2[maxn];

void makeSet() {  
    for (int i = 0; i < maxn; i++)   
        father2[i] = i,  
        father1[i] = i;  
}  

int findRoot1(int x) {  
    int root = x;
    while (root != father1[root]) { 
        root = father1[root];  
    }  
    while (x != root) {  
        int tmp = father1[x];  
        father1[x] = root; 
        x = tmp;  
    }  
    return root;  
}
int findRoot2(int x) {  
    int root = x; 
    while (root != father2[root]) { 
        root = father2[root];  
    }  
    while (x != root) {  
        int tmp = father2[x];  
        father2[x] = root; 
        x = tmp;  
    }  
    return root;  
}

void Union1(int x, int y) { 
    int a, b;  
    a = findRoot1(x);  
    b = findRoot1(y);  
    father1[a] = b; 
}  
void Union2(int x, int y) {
    int a, b;
    a = findRoot2(x);
    b = findRoot2(y);
    father2[a] = b;
}


//=====================================================================

int main()
{
#ifdef LOCAL
    //ifstream cin("E:\\ACMdream\\in.txt");
    //ofstream cout("E:\\ACMdream\\out.txt");
    freopen("E:\\ACMdream\\in.txt","r",stdin);
    freopen("E:\\ACMdream\\out.txt","w",stdout);
#endif
    IOS

    //======================================================================

    int t =1 ;
    //cin >> t ;
    while (t--) {
        int n,m1,m2;cin>>n>>m1>>m2;
        makeSet();
        int ans=0;
        vector<pair<int,int>>v;
        for(int i=1;i<=m1;i++){
            int x,y;cin>>x>>y;
            Union1(x,y);
        }
        for(int i=1;i<=m2;i++){
            int x,y;cin>>x>>y;
            Union2(x,y);
        }
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(findRoot1(i)!=findRoot1(j)&&findRoot2(i)!=findRoot2(j)){
                    v.push_back(make_pair(i,j));
                    ans++;
                    Union1(i,j);Union2(i,j);
                }
            }
        }
        cout<<ans<<'\n';
        for(int i=0;i<ans;i++){
            cout<<v[i].first<<' '<<v[i].second<<'\n';
        }
    }

    //======================================================================

    //SYP
    return 0;
}

D2. Mocha and Diana (Hard Version)

逛submission逛到的一种解法，自己理解了一番，觉得很妙。

考虑到题目要保持两棵树且尽最大可能多地连边，不妨选一个点作为根节点，本人习惯上上并查集大的合并到小的，所以这里选择1。

遍历2到n每个点，分别检查两张图里它们与1的的连接状态。假设当前检查点为i，那么就有以下情况：

1. 假设都没有接上1，那么答案就可以增加一组<1,i>

2. 都接上了1，那么不需要添加边

3. 一张接上了1，另一张没有接上1，那么这时的点i有可能与接下来某个点j连接从而使他合理地接上1，所以这里把它存进栈里(保证单调)。

综上所述，开两个并查集和两个栈分别存储两个图的元素，在把<1,i>的答案组检查完之后再去检查栈里的元素，每次提出两个点，将它们连接作为另一种答案组。

这里实时将未和1连接的点放入栈内，在检查第二种答案组时判断一下和1的连接状态。

那么问题就解决了。

/*
 * @Autor: violet apricity (zpx)
 * @Date: 2021-07-22 22:06:15
 * @LastEditors: violet apricity (zpx)
 * @LastEditTime: 2021-08-16 14:05:38
 * @FilePath: \apricity\cf.cpp
 * @Description: Violet acm && Apricity:/ The warmth of the sun in the winter /
 */


        // violet apricity
        // Do all I can do.Do good to be good.
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>
#include<sstream>
#include<numeric>
#include<queue>
#include<iomanip>
#include<fstream>
#include<unordered_map>
#include<stack>
#include<set>
#include<random>

//#include<bits/stdc++.h>

#define ll long long
#define db double
#define ldb long double
#define IOS std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);
#define MAX 88888888
#define INF 0x3f3f3f3f
#define r0 return 0;
#define SYP system("pause");
//#define endl '\n'
using namespace std;

ll gcd(ll a,ll b){ll d;while(b){d=b;b=a%b;a=d;}return a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll _pow(ll a,ll b){ll d=1;while(b){if(b&1)d*=a;a*=a;b>>=1;}return d;}
ll mpow(ll a,ll b,ll m){ll d=1;while(b){if(b&1)d=(d*(a%m))%m;a=((a%m)*(a%m))%m;d%=m;b>>=1;}return d%m;}

//#define int long long

//=====================================================================

const int N=2e5+10;
const ll mod=1e9+7;
/*
ll jie[N];
ll tow[N];
void init()
{
    jie[0]=1;
    for(int i=1;i<N;i++)jie[i]=jie[i-1]*i%mod;
    tow[N-1]=mpow(jie[N-1],mod-2,mod);
    for(int i=N-2;i>=0;i--) tow[i]=tow[i+1]*(i+1)%mod;
}
ll cal(ll n,ll m)
{
    if(m>n) return 0;
    return jie[n]*tow[m]%mod*tow[n-m]%mod;
}
*/

//=====================================================================

#define pcase(t,d) cout<<"Case #"<<(t)<<": "<<(d)<<'\n'
#define pno cout<<"NO\n"
#define pyes cout<<"YES\n"
#define pdebug(ans) cout<<"ans:"<<(ans)<<'\n'
#define pshow(x) cout<<" show:"<<(x)<<'\n'
#define p(ans) cout<<(ans)<<'\n'
#define pdec(t,ans) cout<<std::fixed<<std::setprecision(t)<<(ans)<<'\n'

//=====================================================================

struct dsu {
	vector<int> f;
	dsu(int n) :f(n) { iota(f.begin(), f.end(), 0); }
	int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
	void merge(int x, int y) {
		x = find(x); y = find(y);
		if (x > y)swap(x, y);
		f[y] = x;
	}
};

//=====================================================================

int main()
{
#ifdef LOCAL
    //ifstream cin("E:\\ACMdream\\in.txt");
    //ofstream cout("E:\\ACMdream\\out.txt");
    freopen("E:\\ACMdream\\in.txt","r",stdin);
    freopen("E:\\ACMdream\\out.txt","w",stdout);
#endif
    IOS

    //======================================================================

    int t =1 ;
    //cin >> t ;
    while (t--) {
        int n, m1, m2; cin >> n >> m1 >> m2;
	    dsu t1(n + 1), t2(n + 1);
	    for (int i = 0; i < m1; i++) {
	    	int x, y; cin >> x >> y;
	    	t1.merge(x, y);
    	}
	    for (int i = 0; i < m2; i++) {
	    	int x, y; cin >> x >> y;
	    	t2.merge(x, y);
    	}
	    vector<pair<int, int>> ans;
	    vector<int> v1, v2;
	    for (int i = 2; i <= n; i++) {
	    	if (t1.find(i) != 1 && t2.find(i) != 1) {
		    	ans.push_back({ 1,i });
		    	t1.merge(1, i);
		    	t2.merge(1, i);
	    	}
	    	if (t1.find(i) != 1)v1.push_back(i);
	    	if (t2.find(i) != 1)v2.push_back(i);
	    }
	    while (!v1.empty() && !v2.empty()) {
	    	if (t1.find(v1.back()) == 1 && t2.find(v1.back())==1) {
		    	v1.pop_back();
		    	continue;
		    }
	    	if (t1.find(v2.back()) == 1 && t2.find(v2.back()) == 1) {
		    	v2.pop_back();
		    	continue;
	    	}
		    ans.push_back({ v1.back(),v2.back() });
		    t1.merge(v1.back(), v2.back());
		    t2.merge(v1.back(), v2.back());
	    	v1.pop_back(); v2.pop_back();
    	}
    	cout << ans.size() << '\n';
    	for (auto i : ans) {
    		cout << i.first << ' ' << i.second << '\n';
    	}
    }

    //======================================================================

    //SYP
    return 0;
}