Codeforces Round #819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022

A：Mainak and Array 思维

题意：

给定一串序列，你可以进行如下操作

 询问经过多次操作后，得到的(an-a1)的最大值。

思路：

情况1：如果选择整个区间，我们只能选择相对下标差为n-1的两个数

情况2：不改变a1，在其他数中选出最大值作an

情况3：不改变an，在其他数中选出最小值作a1

B： Mainak and Interesting Sequence 构造

 题意：

给定序列元素个数n，以及元素总和m，我们需要构造出一个序列满足所有小于ai的数异或和为0（ai为正数）

思路：

首先n>m一定无法构造。然后异或和为0，代表着小于ai的aj一定有偶数个，因为aj^aj=0。为了方便，我们首先用1填充，如果n%1=1，最后在1序列末尾加上一个m-（n-1）即可；如果n%2=0，最后需要加上的2个（m-(n-2)）/2，但如果（m-(n-2)）%1==1，我们也无法构造，因为这样始终会有两个数无法凑成一对

C. Jatayu's Balanced Bracket Sequence 思维

 题意：给定一个合法括号序列（当“（）”内部合法，这个括号才是合法的），根据这个合法序列建图，询问有多少个联通分量

样例：

 思路：

真的建图去跑感觉上也行，但属实是下下策。我们可以发现“）（”这样的序列并没有使图出现新的连通块，但“（（”会使连通块数量+1，所以遍历整个序列就行，但注意最开始整体本就是一个连通块，所以最后答案要+1

void solve() {
    cin >> n;
    int inx = 0, cnt = 0, ans = 0, ans2 = 0, ans3 = 0;
    for (int i = 1; i <= 2 * n; i++)
        cin>> line[i];
    for (int i = 1; i <= 2 * n - 1; i++) {
        if (line[i] == '(' && line[i + 1] == '(')
            ans++;
        if (line[i] == '(' && line[i + 1] == ')')
            ans2++;
        if (line[i] == ')' && line[i + 1] == '(')
            ans3++;
    }
    cout << ans2+ans-ans3 << endl;
    return;
}
int

D. Edge Split（联通图）

题意：

给出一个有n个点，m条边的无向图，我们对所有的边黑白染色，定义只有黑边存在时的连通块个数为c1,相对的只用白边存在时联通块的个数为c2,求c1+c2有最小值所有边的染色情况（m>=n-1&&m<=n+2）

思路：

首先我们可以明确，加入一条边后连通块数量会-1（不形成环），所以最优策略一定是没有环的；其次因为是求总和，所以无论怎么分配每种颜色对最后的结果都没影响。所以我们首先对整个图跑生成树并将这些边染为白色，然后如果剩下的边没有形成环便可直接得出；如果有环我们需要将其中任意一条边染为白色来去掉这个环，但如此以来白色中就出现了环，所以我们还需要将被改色的边的顶点的另一条边染为黑色。

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 10;
int fa[MAX_N], t, n, m;
int find(int x)
{
    if (fa[x] != x)
        fa[x] = find(fa[x]);
    return fa[x];
}
struct node
{
    int u, v, id;
}e[MAX_N];
bool vis[MAX_N];
void work()
{
    vector<node> v1, v2;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) fa[i] = i;
    set<int> s;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        e[i] = { u,v,i };
        int x = find(u), y = find(v);
        if (x != y)
        {
            vis[i] = 1;
            fa[x] = y;
            v1.push_back(e[i]);
        }
        else
        {
            s.insert(e[i].v);
            s.insert(e[i].u);
            vis[i] = 0;
            v2.push_back(e[i]);
        }
    }
    if (m == n + 2 && s.size() == 3)
    {
        node e2 = v2.back();
        vis[e2.id] = 1;
        for (auto e1 : v1)
        {
            if (e1.u == e2.u || e1.v == e2.u)
                vis[e1.id] = 0;
        }
    }
    for (int i = 1; i <= m; i++)cout << vis[i];
    cout << endl;
}
int main() {
    std::ios::sync_with_stdio(false);//加快cin读取速度的
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t--) {
        work();
    }

}