导语

三道，但是第二题的结论谁想的出来啊

涉及的知识点

思维，二分图，欧拉回路

链接：Codeforces Round #770 (Div. 2)

题目

A

题目大意：略

思路：如果字符串初始回文，那么只产生一种，否则产生两种

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
int n,t,a[maxn],k;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>t;
    while(t--) {
        cin >>n>>k;
        string s;
        cin >>s;
        int len=s.length();
        bool flag=0;
        for(int i=0; i<=len/2; i++)//判断是否为回文串
            if(s[i]!=s[len-i-1]) {
                flag=1;
                break;
            }
        if(k==0||!flag) {//不操作或者是回文
            cout <<1<<endl;
            continue;
        }
        cout <<2<<endl;
    }
    return 0;
}

B

题目大意：略

思路：一开始错过了一个关键条件：每个元素都会操作一遍，并且以下标的升序操作，以及异或运算和加运算的结果的奇偶性是相同的，而 $x, x + 3$ 的奇偶性一定不同，所以只用判断哪个数进行n次操作之后的奇偶性与y相同即可

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
int n,t,a[maxn],k,x,y;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>t;
    while(t--) {
        cin >>n>>x>>y;
        for(int i=1; i<=n; i++) {
            int p;
            cin >>p;
            x^=p;//异或
        }
        if((x&1)^(y&1))cout <<"Bob\n";//判断奇偶性
        else cout <<"Alice\n";
    }
    return 0;
}

C

题目大意：1 ~ n×k这n×k个整数放入一个n×k的矩阵中，对于每一行需要满足任意区间的平均值都需要是整数，输出构造的矩阵

思路：贪心的考虑，由于是任意区间，所以相邻的两个数必然也需要平均数为整数，那么奇偶性必须相同，那么每一行顺着放相同奇偶的即可，如果无法放完则无解

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
int n,t,k;
signed main() {
//    ios::sync_with_stdio(0);
//    cin.tie(0);
    cin >>t;
    while(t--) {
        cin >>n>>k;
        if(k==1) {//每一行只用放一个
            cout <<"YES\n";
            for(int i=1; i<=n*k; i++)
                cout <<i<<endl;
            continue;
        }
        if(n*k&1) {//整体是奇数
            cout <<"NO\n";
            continue;
        }
        if(n&1) {//行为奇数，奇数和偶数个数都为奇数，但是每一行只能放偶数个
            cout <<"NO\n";
            continue;
        }
        cout <<"YES\n";
        for(int i=2; i<=n*k; ) {
            for(int j=1; j<=k; j++)
                cout <<i<<" ",i+=2;
            cout <<endl;
        }
        for(int i=1; i<=n*k;) {
            for(int j=1; j<=k; j++)
                cout <<i<<" ",i+=2;
            cout <<endl;
        }
    }
    return 0;
}

E

题目大意：给出m个长度为偶数的整数序列，需要将所有的数字划分成两个集合，并且对于每个序列也必须有一半的数字在A集合，一半在B集合中，输出一种分配方式

思路：见参考文献，大多数题解没有详细讲清楚DFS的原理，之后抽时间弄清楚

代码

#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int maxn=2e5+5;
int m,n,cnt,pos[maxn<<1];
map<int,int> acc,ind;
vector<pair<int,int>>g[maxn<<1];
string ans[maxn<<1];
void DFS(int v) {
    if(pos[v]==0)
        ans[v]=string(g[v].size(),'L');
    while(pos[v]<g[v].size()) {
        int x=g[v][pos[v]].first,y=g[v][pos[v]].second;
        if(x==-1) {
            pos[v]++;
            continue;
        }
        g[x][y].first=-1,g[v][pos[v]].first=-1;
        if(v<maxn)ans[v][pos[v]]='R';
        pos[v]++;
        DFS(x);
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>m;
    for(int i=0; i<m; i++) {
        int n;
        cin >>n;
        for(int j=1; j<=n; j++) {
            int x;
            cin >>x;
            if(!ind.count(x))ind[x]=cnt++;//离散化
            x=ind[x];//获得离散化后的下标
            acc[x]++;//对应的个数增加
            g[i].emplace_back(x+maxn,g[x+maxn].size());
            //i到对应数字建边，边权为第几次出现
            g[x+maxn].emplace_back(i,g[i].size()-1);
            //对应数字到i建边，边权为该数组的第几个
        }
    }
    for(auto i:acc)//如果存在一个数的个数为奇数
        if(i.second&1) {
            cout <<"NO\n";
            return 0;
        }
    for(int i=0; i<(maxn<<1); i++)DFS(i);
    cout <<"YES\n";
    for(int i=0; i<m; i++)cout <<ans[i]<<endl;
    return 0;
}