Codeforces Round #770 (Div. 2) E. Fair Share 二分图染色 补

思路

题目给定 m m m个整数序列，要求尝试找到一种分类方式，将每个序列分到 2 2 2个可重集合中。要求在分类完成后，两个集合的完全相同。

首先考虑一定非法的情况：容易发现：

• 对于某个序列长度为奇数的情况，一定不存在解(无法对半分)
• 对所有的数字开桶记录，如果存在某个数字的出现次数为奇数，则一定不存在对等的分配方案

我们可以对每个序列的编号向其元素编号连无向边，可以发现分 L , R L,R L,R符合二分图的性质，那么直接遍历二分图进行染色即可。

注意，由于序列的编号和元素的编号会发生重叠，因此我们对元素的编号需要进行一个映射。一种方法是先记录集合的数量，然后数字从集合的数量 + 1 +1 +1开始编号。

Accepted Code

#include 
#define int long long

#define showYes std::cout