CodeforcesLuogu分析这个“所有边的出入度都是偶数”可以想到欧拉回路。可以发现只要造一张边数最小且为偶数的欧拉图出来，然后把欧拉回路上的边依次正向、反向定向即可。这个很容易造，我们只要把相邻度数为奇数的点两两之间连一条边即可。练完之后边数可能是奇数，再连一个自环即可。显然这样子边数是最小的。代码// ==================================== //...
Conspiracy考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。可能会有些卡空间。代码Lollipop可以发现如果存在一段和为 $w$，则一定存在一段和为 $w-2$，...
LuoguLOJ分析考虑二分答案，则我们需要判定是否存在混合图欧拉回路。首先混合图不连通的话一定不存在。然后给无向边任意定向，算出每个点的度数，如果有点度数为奇数则不存在。那么对于一条无向边，假设我们定向 $u\to v$，则我们可以改变它的方向使得 $in_u-out_u$ 增加 $2$、$in_v-out_v$ 减少 $2$。因此可以考虑网络流。对于 $in_ out_i$ 的点，从源点...
CodeForcesLuogu翻译分析记红色的区间为$1$，蓝色的区间为$-1$，那么对于任意一个点，覆盖它的线段的权值和的绝对值不超过$1$。那么可以对于每个区间 $[l,r]$ ，从 $l$ 向 $r+1$ 连无向边。此时也就变成了每个点的入度与出度之差的绝对值不超过$1$。发现奇度数点不太好搞。可以按照横坐标排个序，然后一一匹配。这样子只要求一条欧拉回路就行了。求出欧拉回路后给每条边染...
Luogu算法建图求欧拉路即可。代码#include <bits/stdc++.h> #define re register using namespace std; const int MAXN=256; int G[MAXN][MAXN]; int degree[MAXN]; char ans[MAXN*MAXN]; char tmp[MAXN]; int n; inli...