CodeforcesRound#770E.FairShare（欧拉回路）

题目

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的建图方法，本质一致

代码

#includeusing namespace std;void fast(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}int main(){ fast(); int m,n; cin>>m; vector >a(m),ans(m); vectorb; for(int i=0;i>n; a[i].resize(n); ans[i].resize(n); for(int j=0;j>a[i][j]; b.push_back(a[i][j]); } } sort(b.begin(),b.end()); b.erase(unique(b.begin(),b.end()),b.end()); vectordeg(b.size()); for(int i=0;i >e(b.size()); int id=0; for(int i=0;i 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