DDOSvoid's Blog

CF 1634E Fair Share

发表于 分类于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

题目描述

https://codeforces.com/problemset/problem/1634/E

简要题意：给定 $n$ 个数列，第 $i$ 个数列的长度为 $m_i$，现在要求将这 $\sum_{i=1}^nm_i$ 个数划分进两个可重集合中，要求这两个可重集合完全相同，每个数只能进一个集合，同时必须保证每个数列都有恰好一半的数进入 $A$ 集合，另一半进入 $B$ 集合

$n\le 10^5,\sum_{i=1}^nm_i\le 2\times 10^5$

Solution

我们考虑将数字和数组都看成点，如果一个 $x$ 在 $i$ 数列中出现了 $k$，那么就连 $k$ 条 $x$ 到 $i$ 的双向边，然后我们跑欧拉回路，我们将入边和出边看成左右集合，因为每个点的入度都等于出度，所以两个条件都能得到满足

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <vector>
#include <map>
#define maxn 300010
using namespace std;

int n, m, cnt;
map<int, int> mp;
vector<int> ans[maxn];
char s[maxn];

struct Edge {
    int to, next, x, y;
    bool ext;
} e[maxn * 2]; int c1, head[maxn], du[maxn];
inline void add_edge(int u, int v, int x, int y) {
    e[c1].to = v; e[c1].x = x; e[c1].y = y; 
    e[c1].next = head[u]; head[u] = c1++; 
}

void dfs(int u) {
    for (int &i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to, x = e[i].x, y = e[i].y; bool &ext = e[i].ext, &Ext = e[i ^ 1].ext; 
        if (ext) continue; ext = Ext = 1; dfs(v);
        if (v <= n) ans[x][y] = 1;
    }
} 

int main() { fill(head, head + maxn, -1);
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int l, x; cin >> l; ans[i].resize(l);
        for (int j = 0; j < l; ++j) {
            cin >> x; 
            if (!mp[x]) mp[x] = ++cnt;
            add_edge(i, mp[x] + n, i, j); 
            add_edge(mp[x] + n, i, i, j);
            ++du[i]; ++du[mp[x] + n];
        }
    }
    for (int i = 1; i <= n + cnt; ++i) if (du[i] & 1) return cout << "NO" << "\n", 0;
    for (int i = 1; i <= n; ++i) dfs(i); 
    cout << "YES" << "\n";
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < ans[i].size(); ++j) s[j] = ans[i][j] ? 'L' : 'R';
        s[ans[i].size()] = 0; cout << s << "\n";
    }
    return 0;
}