[数据结构与算法]Codeforces Round #738 (Div. 2)题解

A

题意：一个数组长度为$n$，对数组进行操作，选取区间$a_i$到$a_j$对区间的数进行与操作$a_{i+l}$ = $a_{i+l}$ & $a_{r?i}$这种操作可以作用任何数组中的数，最小化最大的数，答应这个值；
思路：&运算以后，$a$&$b$ <= $a$($a$ > $b$)所以想要让最大值最小就让数组中最大的数&整个数组，就可以得到最小值.

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int t, n;
long long a[N];
int main()
{
    cin >> t;
    while (t -- )
    {
        cin >> n;
        for (int i = 1; i <= n; i ++ ) {
            cin >> a[i];
        }
        long long maxx = a[1];
        for (int i = 2; i <= n; i ++ ){
            maxx = maxx & a[i];
        }
        cout << maxx << endl;
    }
    return 0;
}

B

题意：一个字符串是由$?$、$B$、$R$组成的，连续的$B$和连续的$R$是不完美的，表示为$BB$、$RR$的不完美度是2，$BBB$不完美度是3……，将$?$换成$B$或者是$R$，输出替换完成之后不完美度最小的字符串。
理解：我们用栈来表示这个这个字符串

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, t;
int main()
{
    cin >> t;
    while (t -- )
    {
        cin >> n;
        string s;
        cin >> s;
        stack<int>a;
        for (int i = 0; i < n; i ++ ){
            if (s[i] == '?') a.push(i);
            else{
                if (a.size() == 0) continue;
                else {
                    while(a.size()){
                        s[a.top()] = (s[a.top() + 1] == 'R')?'B':'R';
                        a.pop();
                    }
                }
            }
        }
        if (a.size() == 0) cout << s << endl;
        else{
            if (a.size() != n){
                for (int i = n - a.size(); i < n; i ++ ){
                    s[i] = (s[i - 1] == 'R')?'B':'R';
                }
            }
            else{
                for (int i = 0; i < n; i ++ ){
                    if (i % 2) s[i] = 'B';
                    else s[i] = 'R';
                }
            }
            cout << s << endl;
        }
    }
    return 0;
}

C

题意：有$n+1$个村庄，这个村庄有单向路，是$i$到$i+1$的一条路$i<=n$，给一个长度为n的数组，如果$a_i=0$表示一条路$i$到$n+1$,如果$a_i=1$表示一条路$n+1$到$i$,一个人想浏览这$n+1$个村子，从起点出发回到起点，起点是任意的，如果有这样的路线打印，打印出来这个路线，否则输出-1.
思路：这道题看上去像是图论题用拓扑排序写，但是我们发现没有入度为0的点写不了，其实这是到思维题，我们特判一下$a_1=1$和$a_n=0$的时候再找有没有01.

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, t;
int main()
{
    cin >> t;
    while (t -- )
    {
        cin >> n;
        string s;
        cin >> s;
        stack<int>a;
        for (int i = 0; i < n; i ++ ){
            if (s[i] == '?') a.push(i);
            else{
                if (a.size() == 0) continue;
                else {
                    while(a.size()){
                        s[a.top()] = (s[a.top() + 1] == 'R')?'B':'R';
                        a.pop();
                    }
                }
            }
        }
        if (a.size() == 0) cout << s << endl;
        else{
            if (a.size() != n){
                for (int i = n - a.size(); i < n; i ++ ){
                    s[i] = (s[i - 1] == 'R')?'B':'R';
                }
            }
            else{
                for (int i = 0; i < n; i ++ ){
                    if (i % 2) s[i] = 'B';
                    else s[i] = 'R';
                }
            }
            cout << s << endl;
        }
    }
    return 0;
}

D

题意：有两个森林（森林就是没有环的无向图）有n个点，这两个森林分别有$m1$和$m2$条边,向这两个森林里面填边，如果往森林a中填了一条$(u,v)$的边也要在森林b中添加同样的边，最多可以填多少边？打印出边数，和每一条边。
思路：并查集暴力枚举每一条边

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
typedef pair<int, int> PII;
int n, m1, m2, f[2][N], v, u;
int get(int i , int x){
    return f[i][x] == x?x:f[i][x] = get(i, f[i][x]);
}
int main()
{
    cin >> n >> m1 >> m2;
    for (int i = 1; i <= n; i ++ ) f[0][i] = f[1][i] = i;
    for (int i = 1; i <= m1; i ++ ){
        cin >> u >> v;
        f[0][get(0, u)] = get(0, v);
    }
    for (int i = 1; i <= m2; i ++ ){
        cin >> v >> u;
        f[1][get(1, u)] = get(1, v);
    }
    vector<PII>a;
    for (int i = 1; i <= n; i ++ ){//无向图
        for (int j = i + 1; j <= n; j ++ ){
            if (get(0, i) != get(0, j) && get(1, j) != get(1, i)){
                f[0][get(0, i)] = get(0, j);
                f[1][get(1, i)] = get(1, j);
                a.push_back(PII(i, j));
            }
        }
    }
    cout << a.size() << endl;
    for (auto x : a)
        cout << x.first << " " << x.second << endl;
    return 0;
}