Codeforces-1634 E：Fair Share（欧拉回路）

Mitsuha_

451人浏览 · 2026-03-28 13:56:49

Mitsuha_ · 2026-03-28 13:56:49 发布

E. Fair Share
time limit per test 1.5 seconds
memory limit per test 256 megabytes
You are given m arrays of positive integers. Each array is of even length.

You need to split all these integers into two equal multisets L and R, that is, each element of each array should go into one of two multisets (but not both). Additionally, for each of the m arrays, exactly half of its elements should go into L, and the rest should go into R.

Give an example of such a division or determine that no such division exists.

Input
The first line contains an integer $m$ $(1≤m≤105)(1\leq m\leq10^5)$ — the number of arrays.

The next $2 \cdot m$ lines contain descriptions of the arrays.

For each array, the first line contains an even integer $n$ $(2≤n≤2⋅105)(2\leq n\leq2⋅10^5)$ — the length of the array. The second line consists of $n$ space-separated integers $a_1,a_2,…,a_n$ $(1≤ai≤109)(1\leq a^i\leq10^9)$ — array elements.

It is guaranteed that the sum of $n$ over all arrays does not exceed $2⋅10^5$ .

Output
If the answer exists, print “YES”, and then print $m$ lines.

On each line, for each element, print the letter “L” or “R” (capitalized, without spaces), depending on which multiset the element should go into.

If there is no answer, print “NO” on the only line.

Example
Input
3
2
1 2
4
1 2 3 3
6
1 1 2 2 3 3
Output
YES
RL
LRLR
RLLRRL

思路：要均分所有数，每个数的总出现次数必须为偶数。考虑建图，把 $n$ 个数组看成 $n$ 个节点，将数组里的数与数组建边。
如此这个图中的每个节点度数都为偶数，满足欧拉回路性质。接下来就是将此图中的每个节点所连的边平均分配至L和R中，即每个数组里一半的数在L一半在R，同时每种数也是一半在L，一半在R。
考虑欧拉回路，从任一点出发，经过每条边一次，最终回到起点。假设数组节点开始，则由数组向数访问的出边分配至L，数向数访问的入边分配之R，因为数组和数之间是交替连通的，所以正好满足题目条件。

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson (k<<1)
#define rson (k<<1)+1
#define mid ((l+r)/2)
#define sz(x) ssize(x)
#define pii pair<int,int>
#define ull unsigned long long
using namespace std;
const int MAX=5e5+10;
const int MOD=1e9+7;
const int INF=INT_MAX/2;
const double PI=acos(-1.0);
typedef long long ll;
vector<int>ans[MAX];
set<pii>e[MAX];
int v[MAX];
void dfs(int k)
{
    stack<pii>p;
    while(e[k].size())
    {
        v[k]=1;
        auto [nex,idx]=*e[k].begin();
        e[k].erase({nex,idx});
        e[nex].erase({k,-idx});
        p.push({k,idx});
        k=nex;
        if(v[nex]==0)continue;
        while(!p.empty())
        {
            auto [pre,idx]=p.top();p.pop();
            v[pre]=0;
            if(idx>0)ans[pre][idx-1]='L';
            else ans[k][abs(idx)-1]='R';
            k=pre;
            if(pre==nex)break;
        }
    }
}
int solve()
{
    int n;
    cin>>n;
    map<int,int>ma,c;
    for(int i=1;i<=n;i++)
    {
        int m;
        scanf("%d",&m);
        ans[i].resize(m);
        for(int j=1,x;j<=m;j++)
        {
            scanf("%d",&x);
            if(ma[x]==0)ma[x]=ma.size()+n;
            e[i].insert({ma[x],j});
            e[ma[x]].insert({i,-j});
            c[x]++;
        }
    }
    for(auto [i,j]:c)if(j%2)return puts("NO");
    for(int i=1;i<=n;i++)dfs(i);
    puts("YES");
    for(int i=1;i<=n;i++)
    {
        for(char c:ans[i])printf("%c",c);
        puts("");
    }
    return 0;
}
int main()
{
    int T=1;
//    cin>>T;
    while(T--)solve();
    return 0;
}