[数据结构与算法]Codeforces Round #770 (Div. 2) E. Fair Share（欧拉回路）

题目

m(1<=m<=1e5)个数组，第i个数组的长度为ni（2<=ni<=2e5，ni为偶数）

第i个数组内的第j个值aij(1<=aij<=1e9)，sumni<=2e5

问是否能把这些整数分成两个multiset，不妨称为L集合和R集合，

使得每个数组内恰有一半元素在L集合内，另一半元素在R集合内，

且L集合和R集合最终是相同的multiset

思路来源

palayutm、wifiii代码

题解

如果想到欧拉回路的构造，就很好做了

首先考虑无解的情形，某一种数字出现了奇数次，一定无解；否则，一定有解

先把数字离散化，然后这里给出一种构图方式：

第i个数组中，ai0和ai1连无向边，ai2和ai3连无向边，以此类推

相当于ai0和ai1位于二分图的不同侧，ai2和ai3同理，

可以发现，对于图上每个点（离散化后的数字）来说，

由于出现次数是偶数，所以度数为偶数，所以欧拉回路一定有解

不妨在某一种欧拉回路的方案中，边x是从第i个数组的a值指向b值的，

给边定向，不妨给b值划分到R集合，给a值划分到L集合

无论同一个数组内的边如何定向，都恰有一半属于L，另一半属于R

而对于每个数字v来说，恰有一半边从v出发指向其他点，另一半边从其他点出发回到v

这里试了一下c11和c17的语法，感觉还挺好用的

心得

反向考虑，为什么这么建图，

由于每个数字出现是偶数，所以每个aij连一条边，就能保证欧拉回路有解

由于最后每个数组内恰有ni/2个位于L集合，另ni/2个位于R集合，

所以相当于有ni/2对互斥关系，就对应在每个数组内建ni/2对两两结对的边，

给边定向时，让相邻点位于不同集合，即可达到这个目的

这与官方题解中，二分图左侧点i表示第i个数组，右侧点j表示数字j的建图方法，本质一致

代码

#include<bits/stdc++.h>
using namespace std;
void fast(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
int main(){
    fast();
    int m,n;
    cin>>m;
    vector<vector<int> >a(m),ans(m);
    vector<int>b;
    for(int i=0;i<m;++i){
        cin>>n;
        a[i].resize(n);
        ans[i].resize(n);
        for(int j=0;j<n;++j){
            cin>>a[i][j];
            b.push_back(a[i][j]);
        }
    }
    sort(b.begin(),b.end());
    b.erase(unique(b.begin(),b.end()),b.end());
    vector<int>deg(b.size());
    for(int i=0;i<m;++i){
        for(auto &v:a[i]){
            v=lower_bound(b.begin(),b.end(),v)-b.begin();
            deg[v]++;
        }
    }
    for(auto &v:deg){
        if(v&1){
            cout<<"NO"<<endl;
            return 0;
        }
    }
    vector<vector<array<int,4>> >e(b.size());
    int id=0;
    for(int i=0;i<m;++i){
        for(int j=1;j<a[i].size();j+=2){
            e[a[i][j]].push_back({a[i][j-1],i,j,id});
            e[a[i][j-1]].push_back({a[i][j],i,j-1,id});
            id++;
        }
    }
    vector<bool>vis(id);
    function<void(int)> dfs = [&](int u){
        while(!e[u].empty()){
            auto [v,i,j,id]=e[u].back();
            e[u].pop_back();
            if(vis[id])continue;
            vis[id]=1;
            ans[i][j]=1;
            dfs(v);
        }
    };
    for(int i=0;i<b.size();++i){
        dfs(i);
    }
    cout<<"YES"<<endl;
    for(int i=0;i<m;++i){
        for(auto &v:ans[i]){
            cout<<(v?'L':'R');
        }
        cout<<endl;
    }
    return 0;
}