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

Codeforces Round #738 (Div. 2)

A. Mocha and Math

题目描述：

给你一个数组，你可以进行一种操作，选[l,r]的区间，对于[l, r]的所有i，用a_l+i & a_r-i来代替a_l+i,可以进行无数次这种操作，问你最小化最大值为多少

思路：

这个题我其实没怎么读题，看了一眼是与操作，然后看了一眼样例，发现四组样例的答案都是a_i想与，然后就写了一发交了，直接a掉了

如果不猜的话该怎么分析？也很简单，因为是与操作，而一个数与上另一个数，只会让原来的数更小，所以我们通过适当的操作使得所有的a_i相与，这就是最小化的最大值

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1.0E-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX  2000000 + 50
//#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define max(a,b) (((a)>(b)) ? (a):(b))
#define min(a,b) (((a)>(b)) ? (b):(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int t, n, x, ans;

int main(){
    sd(t);
    while (t--) {
        sd(n);
        sd(ans);
        for(int i = 1; i < n; ++i){
            sd(x);
            ans &= x;
        }
        cout<<ans<<endl;
    }
    return 0;
}

B. Mocha and Red and Blue

题目描述：

给你一个串，这个串只有?BR这三个字符，?可以填B或R，你需要构造含有最少的BB和RR字符的串，比如BRRRBBR，有2个RR和1个BB，总共是3个

思路：

你可以发现如果左面有字符，那么下一个字符选与他相异的字符最优，对于左面没有字符的就从右面往左构造

所以先找到第一个不是B和R的，往左构造，然后再等一个不是BR的往右构造到最后就可以

如果全是?就特判一下，BR交替出现就可以

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1.0E-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX  2000000 + 50
//#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define max(a,b) (((a)>(b)) ? (a):(b))
#define min(a,b) (((a)>(b)) ? (b):(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int t, n, x, ans;
string s, p;

int main(){
    sd(t);
    while (t--) {
        cin>>n>>s;
        int pos = -1;
        for(int i = 0; i < s.size(); ++i){
            if(s[i] == 'B' || s[i] == 'R'){
                pos = i;
                break;
            }
        }
        for(int i = pos - 1; i >= 0; --i){
            s[i] = s[i + 1] == 'B' ? 'R' : 'B';
        }
        for(int i = pos + 1; i < s.size(); ++i){
            if(s[i] == 'B' || s[i] == 'R')continue;
            if(i == 0)s[i] = 'B';
            else{
                s[i] = s[i - 1] == 'B' ? 'R' : 'B';
            }
        }
        cout<<s<<endl;
        
    }
    return 0;
}

C. Mocha and Hiking

题目描述：

n+1个点，2n-1条有向边，其中n-1条边是i到i + 1，1 <= i <= n-1,

另外n+1条边有a_i控制，a_i = 1，则有一条a_n+1指向a_i的边，a_i = 0，则有一条从a_i指向a_n+1的边，你需要输出一条路径，经过所有点，且每个点只经过一次

思路：

分情况讨论即可

当a₁ = 1，说明有a_n+1指向a₁的边，此时就输出n+1、1、2……n即可

当a_n = 0，说明用a_n指向a_n+1的边，此时输出1、2、3……n+1即可

任意一个01出现的位置，假设0的位置为i，则输出1……i、n+1、i+1、i+2……n

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1.0E-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX  5000000 + 50
//#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define max(a,b) (((a)>(b)) ? (a):(b))
#define min(a,b) (((a)>(b)) ? (b):(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int t, n;
int tr[MAX];

int main(){
    sd(t);
    while (t--) {
        sd(n);
        for(int i = 1; i <= n; ++i)sd(tr[i]);
        if(tr[1] == 1){
            cout<<n + 1;
            for(int i = 1; i <= n; ++i)cout<<' '<<i;
            cout<<endl;
        }
        else if(tr[n] == 0){
            for(int i = 1; i < n + 1; ++i)cout<<i<<' ';
            cout<<n + 1<<endl;
        }
        else{
            int pos = -1;
            for(int i = 1; i < n; ++i){
                if(tr[i] == 0 && tr[i + 1] == 1){
                    pos = i;
                    break;
                }
            }
            if(pos == -1)cout<<-1<<endl;
            else{
                for(int i = 1; i <= pos; ++i)cout<<i<<' ';
                cout<<n + 1;
                for(int i = pos + 1; i <= n; ++i)cout<<' '<<i;
                cout<<endl;
            }
        }
    }
    return 0;
}

D1. Mocha and Diana (Easy Version)

题目描述：

开局给出两张森林，你可以进行的操作是连接任意两个点，连的时候必须在两张图都连，且不能形成环

思路

数据才1000，直接暴力就可以，双重for循环，用并查集判断两个点能不能连接，能连就连，不能连就不连，O(n²logn)的复杂度

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1.0E-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX  5000 + 50
//#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define max(a,b) (((a)>(b)) ? (a):(b))
#define min(a,b) (((a)>(b)) ? (b):(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int p, n, m, x, y;
int fa[MAX][2];

int tfind(int x, int val){
    return fa[x][val] == x ? x : fa[x][val] = tfind(fa[x][val], val);
}

void emerge(int x, int y, int val){
    fa[tfind(x, val)][val] = tfind(y, val);
}

int main(){
    sddd(p, n, m);
    for(int i = 1; i <= p; ++i){
        fa[i][0] = fa[i][1] = i;
    }
    for(int i = 1; i <= n; ++i){
        sdd(x, y);
        emerge(x, y, 0);
    }
    for(int i = 1; i <= m; ++i){
        sdd(x, y);
        emerge(x, y, 1);
    }
    cout<<p - 1 - max(n, m)<<endl;
    for(int i = 1; i <= p; ++i){
        for(int j = 1; j <= p; ++j){
            if(i == j)continue;
            else{
                if(tfind(i, 0) != tfind(j, 0) && tfind(i, 1) != tfind(j, 1)){
                    cout<<i<<' '<<j<<endl;
                    emerge(i, j, 0);
                    emerge(i, j, 1);
                }
            }
        }
    }
    
    return 0;
}

 

昨天晚上躺在床上为手机玩到十一点二十的时候准备睡觉，然后看了一眼QQ，发现群友在打CF，才意识到晚上有CF，但是有点晚了，而且看群友全在吐槽评测机炸了，就没做，这谁想得到这次的DIV2这么简单，艹，错失上分良机(╥﹏╥)