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

https://codeforc.es/contest/1559

A. Mocha and Math

题意： 给出长度为n的序列a， 可进行如下操作任意次：选择一个闭区间[l, r]， 对于任意i在[0, r - l]，可以将a[l + i]替换成a[l + r] & a[r - i]，操作之后使得最大值最小，输出最小的最大值。

思路： 众所周知与运算只会越与越小，而且满足交换律与结合律，所以求一下所有数的与就行了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
    int t, n, a;
    cin >> t;
    while(t--)
    {
        cin >> n >> a;
        int ans = a;
        for(int i = 1;i < n; i++)
        {
            cin >> a;
            ans &= a;
        }
        cout << ans << endl;
    }
    return 0;
}

B. Mocha and Red and Blue

题意： 给出n个格子，其中一些可能已经有颜色了，但是其他的是空白的，我们可以把格子染成红色或者黑色，问怎么染使得相邻格子颜色相同的数量最少，输出染色序列；

思路： 简单贪心，但别忘了考虑全部空白的情况。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

char a[233];

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d%s", &n, a + 1);
        int ans = 0, flag = 0;
        for(int i = 1;i <= n; i++)
        {
            if(a[i] == '?' && !flag) continue;
            if(!flag)
            {
                for(int j = i - 1;j >= 1; j--)
                {
                    if(a[j + 1] == 'R') a[j] = 'B';
                    else a[j] = 'R';
                }
                flag = 1;
            }
            if(a[i] == '?')
            {
                if(a[i - 1] == 'R') a[i] = 'B';
                if(a[i - 1] == 'B') a[i] = 'R';
            }
        }
        if(!flag)
        {
            for(int i = 1;i <= n; i++)
            {
                if(i % 2 == 1) printf("R");
                else printf("B");
            }
            printf("\n");
        }
        else printf("%s\n", a + 1);
    }
    return 0;
}

C. Mocha and Hiking

题意： 有n + 1个点，对于i在[1, n - 1]，有一条i到i + 1的有向边，给出长度为n的序列a，如果a[i]是0，表示i到n + 1有条边；a[i]是1，表示n + 1到i有条边，问如何走可以走遍这n + 1个城市且每个城市只走一次，输出访问序列。

思路： 从1到n可以直接走，所以只需要考虑n + 1放哪就行，有三种情况：①从n走到n + 1；②从n + 1走到1；③从i走到n + 1再走回i + 1；

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1e4 + 10;

int a[maxn];

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d", &n);
        for(int i = 1;i <= n; i++) scanf("%d", &a[i]);
        if(a[n] == 0)
        {
            for(int i = 1;i <= n + 1; i++) printf("%d ", i);
            printf("\n");
        }
        else if(a[1] == 1)
        {
            printf("%d ", n + 1);
            for(int i = 1;i <= n; i++) printf("%d ", i);
            printf("\n");
        }
        else
        {
            int flag = 0;
            for(int i = 2;i <= n; i++)
            {
                if(flag) printf("%d ", i);
                else if(a[i - 1] == 0 && a[i] == 1 && !flag)
                {
                    for(int j = 1;j <= i - 1; j++) printf("%d ", j);
                    printf("%d %d ", n + 1, i);
                    flag = 1;
                }
            }
            printf("\n");
        }
    }
    return 0;
}

D1. Mocha and Diana (Easy Version)

题意： 有两个人，分别有一个由n节点构成的森林，两人的森林分别有m1条与m2条边，现在让你加尽可能多的边，使得加完边之后的森林仍然是森林。加边的规则：当在a和b之间加一条边时，两人的森林会同时增加这条边。输出最多可加边数以及如何加。

思路： 点不是很多，所以直接维护两个并查集，然后暴力就可以。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1010;

int n, m1, m2;
int p1[maxn], p2[maxn];
int x[maxn], y[maxn], idx;

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

int find2(int x)
{
    if(p2[x] != x) return p2[x] = find2(p2[x]);
    return p2[x];
}
int main()
{
    scanf("%d%d%d", &n, &m1, &m2);
    for(int i = 1;i <= n; i++)
    {
        p1[i] = i;
        p2[i] = i;
    }
    while(m1--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if(find1(a) !=find1(b))
        {
            p1[find1(a)] = find1(b);
        }
    }
    while(m2--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if(find2(a) !=find2(b))
        {
            p2[find2(a)] = find2(b);
        }
    }
    idx = 0;
    for(int i = 1;i <= n; i++)
    {
        for(int j = 1;j <= n; j++)
        {
            if(i == j) continue;
            if(find1(i) != find1(j) && find2(i) != find2(j))
            {
                idx++;
                x[idx] = i;
                y[idx] = j;
                p1[find1(i)] = find1(j);
                p2[find2(i)] = find2(j);
            }
        }
    }
    printf("%d\n", idx);
    for(int i = 1;i <= idx; i++) printf("%d %d\n", x[i], y[i]);
    return 0;
}