题意：
给定 \(m\) 个长度为偶数的数组，\(L, R\) 是初始为空的两个多重集。将每个数组恰好一半的数放入 \(L\)，另一半放入 \(R\)，要求最后 \(L=R\)，要求构造方案或判断无解。
\(m \le 10^5, \sum n \le 10^5\)。
思路：
首先我们不难想到，对于同一个数组内相同的值，可以成双除去，所以我们可以简化为每个数组一个值最多有一个的情况。
然后思考这些限制，由于一个值有两个关键的信息：他的值和所属数组。这两个都要满足恰好一半。这让我们联想到建图。
构造二分图，一边是数组，一边是值，然后连边。我们现在要求一个选取边的方案，使得每个点刚好有一半的出边被选取。
这个形式等价于该图存在欧拉回路，所以我们只用找到欧拉回路，然后轮换染色即可。
很有意思的欧拉回路题。
点击查看代码
#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;
int m;
vector<vector<int> > a;//原数组
map<int, int> mp;
int tot = 0;
struct Edge {
int to, idx;
Edge (int _to = 0, int _idx = 0) :
to(_to), idx(_idx) {}
};
vector<Edge> e[N * 2];//二分图
int ed = 0, dg[N * 2] = {0}; //点的度数
void add(int u, int v) {
dg[u]++, dg[v]++, ed++;
// cout << u << " " <<v <<" "<<ed<<endl;
e[u].push_back(Edge(v, ed));
e[v].push_back(Edge(u, ed));
}
void build() {
for (auto &i: mp)
i.second = ++tot;
for (int T = 0; T < m; T++) {
vector<int> t = a[T];
sort(t.begin(), t.end());
for (int i = 0, j = 0; i < (int)t.size(); i++)
if (i == (int)t.size() - 1 || t[i] != t[i + 1]) {
if ((i - j + 1) % 2 == 1)
add(T + 1, m + mp[t[i]]);
j = i + 1;
}
}
}
int cur[N * 2] = {0};
bool vis[N * 2] = {false};
int stk[N * 2] = {0}, tp = 0;
void srh(int x) {
for (int i = cur[x]; i < (int)e[x].size(); i = cur[x]) {
++cur[x];
if (!vis[e[x][i].idx]) {
vis[e[x][i].idx] = true;
srh(e[x][i].to);
stk[++tp] = e[x][i].idx;
}
}
}
bool ans[N * 2] = {false};
bool LR[N] = {false};
void fnd_sol(int T) {
vector<pair<int, int> > t;
for (int i = 0; i < a[T].size(); i++)
t.push_back(make_pair(a[T][i], i)), LR[i] = false;
sort(t.begin(), t.end());
for (int i = 0, j = 0, k = 0; i < (int)t.size(); i++)
if (i == (int)t.size() - 1 || t[i].first != t[i + 1].first) {
int len = i - j + 1;
if (len % 2 == 1) {
// cout << T << " " << t[i].first << " " << ans[e[i][k].idx] << endl;
LR[t[j].second] = ans[e[T + 1][k].idx];
k++, j++, len--;
}
for (int x = j; x <= j + len / 2 - 1; x++)
LR[t[x].second] = false;
for (int x = j + len / 2; x <= i; x++)
LR[t[x].second] = true;
j = i + 1;
}
for (int i = 0; i < (int)a[T].size(); i++)
if (LR[i])
printf("L");
else
printf("R");
printf("\n");
}
int main() {
cin >> m;
for (int i = 1, n; i <= m; i++) {
cin >> n;
vector<int> t = vector<int>(n, 0);
for (int j = 0; j < n; j++)
cin >> t[j], mp[t[j]] = 1;
a.push_back(t);
}
//首先，离散化建图去重
build();
for (int i = 1; i <= m + tot; i++)
if (dg[i] % 2 == 1) {
printf("NO\n");
return 0;
}
//找欧拉回路
for (int i = 1; i <= m + tot; i++)
if (cur[i] < (int)e[i].size()) {
srh(i);
bool rev = (i <= m);
//如果是 <= m -> >m 的就是 true
//否则是 false
while (tp > 0) {
ans[stk[tp]] = rev;
// cout << stk[tp] <<" "<<rev<<endl;
rev = !rev, tp--;
}
}
//找完了，还原方案
printf("YES\n");
for (int T = 0; T < m; T++)
fnd_sol(T);
return 0;
}