菜菜补题,大佬轻喷

A题，一道关于与运算本质理解的题目，主要最近对于思维题老是脑抽

https://codeforces.com/contest/1559/problem/A

题意：给出一组数据，对这组数据可以进行如下操作，选取任意一个区间，区间中的数等于该数和上区间对称的数的与运算结果，！！！该操作可以进行无数次（做的时候我没看到，然后疯狂WA），求能最后形成的新数组里最大的数是所有新数组中最小的

题解：因为操作可以进行无数次，即每个数都可以与上任意数字，又因为与运算的特点，全为1才是1，所以两个数进行与运算操作后，结果一定<=原来的连个数字，所以只需要让所有数进行与运算即可

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define x first
#define y second

using namespace std;
const int N = 105;
typedef long long LL;

using namespace std;

int n,T;
int q[N];

void solve()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> q[i];

    int x = q[0];
    for (int i = 1; i < n; i ++ )
    {
        x &= q[i];
    }

    cout << x << endl;
}

int main()
{
    cin >> T;
    while (T --)
    {
        solve();
    }

    return 0;
}

B题 也是一道思维题，暴力模拟

https://codeforces.com/contest/1559/problem/B

题意：给出字符串长度和一个字符串，该字符串包含三种字符，分别是’B’,’R’,’?’,其中’?’可以被B或R替代，问怎么填写可以使得两个连续的B或者两个连续的R出现的次数最少（BBB表示存在两个BB小串），任意输出一种可行的方法即可

题解：主要思想为对于长的’?’考虑BR交替出现，使得双对出现最少，对于少的’?’考虑和旁边的B或者R不同。操作时进行两遍遍历更改，第一次从左到右，先更新左边的字符，再更新右边的字符，这样操作后会出现前面如果是’?’开头不会被更改，所以从右向左进行一遍更新，先更新右边的字符，再更新左边的字符。可以注意到，如果字符全是’?’的话两种办法遍历完仍是’?’，所以需要特判一下，然后将字符串的第一个字符更新为B或者是R，再进行上面的两种操作

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
const int N = 105;

int T,n;
char s[N];

void solve()
{

    scanf("%d%s",&n,s+1);

    int cnt = 0,num=0;
    for(int i = 1 ; i <= n ; i++ )
    {
        if(s[i] != '?') cnt ++;
    }

    if(!cnt) s[1] = 'B';
    for(int i = 2 ; i <= n ; i ++)
        if(s[i-1] != '?' && s[i] == '?')
        {
            if(s[i-1] == 'B')
                s[i] = 'R';
            else if(s[i-1] == 'R')
                s[i] = 'B';
        }

    for(int i = n-1 ; i >= 1 ; i --)
        if(s[i+1] != '?' && s[i] == '?')
        {
            if(s[i+1] == 'B')
                s[i] = 'R';
            else if(s[i+1] == 'R')
                s[i] = 'B';
        }

    printf("%s\n",s+1);
}

int main()
{
    cin >> T;
    while(T --)
    {
        solve();
    }
    return 0;
}

C题 分类讨论模拟题，读懂题就能过

https://codeforces.com/contest/1559/problem/C

题意：给出一个n值，有n+1个村子，各村子之间的关系有两种：第一种：对于 1->n 中的村庄，i村可以到达i+1村（1-2-3-4）。第二种：给出a[1]~a[n]的数据（0或1），当a[i]=0时，表示a[i]可以到达n+1村,当a[i]=1时，表示n+1可以到达a[i]村。问怎么走可以不重不漏地走完1~n+1所有的村子，任意输出一种可行的答案即可，如果到无法实现则输出-1

题解：经过题意的理解，只要可以走完所有村子，形式一定始终有一种是1~n的顺序排列加上插入其中某位置的n+1。一共可以分为3种情况进行讨论，第一种为a[1]为1，可以直接输出n+1和1~n。第二种为a[n]=0，可以直接输出1~n和n+1。最后一种可以证明一定存在01相连的情况，这时候只需要找到该位置，然后将n+1插到两个村子位置中间即可

#include <iostream>
#include <cstring>
#include <cstdio>
#define x first
#define y second

using namespace std;
typedef pair<int,int> PII;
const int N = 1e4+10;

int T,n;
int q[N];

void solve()
{
    cin >> n;
    int cnt = 0;
    for(int i = 1 ; i <= n ; i ++) 
        cin >> q[i];

    int flag = 0,res;

    if(q[1] == 1) 
    {
        cout << n+1 << ' ';
        for(int i = 1 ; i <= n ; i ++)
            cout << i << ' ';
        puts("");
    }
    else if(!q[n]) 
    {
        for(int i = 1 ; i <= n+1 ; i ++)
            cout << i << ' ';
        puts("");
    }
    else 
    {
        for(int i = 1 ; i < n ; i ++)
            if(q[i] == 0 && q[i+1] == 1)
            {
                res = i;
                flag = 1;
                break;
            }

        if(!flag) cout << -1 << endl;
        else 
        {
            for(int i = 1 ; i <= res ; i ++)
                cout << i << ' ';
            cout << n+1 << ' ';
            for(int i = res+1 ; i <= n ; i ++)
                cout << i << ' ';
                puts("");
        }
    }
}

int main()
{
    cin >> T;
    while(T --)
    {
        solve();
    }
    return 0;
}

D1题 一道关于并查集的问题，也比较简单，思想了解了就可以过

https://codeforces.com/contest/1559/problem/D1

加上2-4边

题意：现有两颗没有任何边的树，每棵树都有n个节点，小明和小红分别先在空树中进行加边，操作完之后，问在这个基础上还最多可以同时加几条相同的边使得仍是两棵树（即小明树加了a-b边的话小红的树也要加a-b边）

题解：维护两个并查集，易知，只要两组中的同样两个边都各自不在同一个集合中，就可以加上这两个边，只需要遍历一遍所有两个边的关系即可，复杂度为n^2

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define x first
#define y second

using namespace std;
typedef pair<int,int> PII;
const int N = 1010;

int n,m1,m2;
int p[N],q[N];//p数组m1的father数组，q为m2的father数组
PII res[N];//储存加的边

int find1(int x)
{
    if(p[x] != x) p[x] = find1(p[x]);
    return p[x];
}

int find2(int x)
{
    if(q[x] != x)q[x] = find2(q[x]);
    return q[x];
}

int main()
{
    cin >> n >> m1 >> m2;
    for(int i = 1 ; i <= n ; i ++) p[i] = i,q[i]=i;

    while(m1 --)
    {
        int a,b;
        cin >> a >> b;
        int pa = find1(a),pb = find1(b);
        if(pa != pb) p[pa] = pb;
    }

    while(m2 --)
    {
        int a,b;
        cin >> a >> b;
        int qa = find2(a),qb = find2(b);
        if(qa != qb) q[qa] = qb;
    }

    int cnt = 0;
    for(int i = 1 ; i <= n ; i ++)
    {
        for(int j = 1 ; j <= n ; j ++)
        {
            int PA = find1(i),PB = find1(j);
            int QA = find2(i),QB = find2(j);
            if(PA != PB && QA != QB)
            {
                res[cnt].x = i;
                res[cnt].y = j;
                p[PA] = PB;
                q[QA] = QB;
                cnt ++;
            }
        }
    }

    cout << cnt << endl;
    for(int i = 0 ; i < cnt ; i ++)
        cout << res[i].x << ' ' << res[i].y << endl;
    return 0;
}