欧拉回路

感觉自己学了个假的欧拉回路。

trick 1

• 给定一个图，我们需要给每个边定向，使得每个点入度与出度差不超过 \(1\) 。

\(sol:\)

首先，因为有奇数点的存在，我们不能直接构造出欧拉回路。所以我们建立一个虚点，然后从所有奇数点和虚点连边，显然此时所有点度数都为偶数，我们跑欧拉回路求一组解，容易验证符合要求。

• 应用

CF723E One-Way Reform

注意到答案的上界是偶数点数量，而上述构造显然可以符合要求。

CF547D Mike and Fish

考虑建立行-列的二分图，每个点就变成了一条边，我们跑一遍上述定向过程，然后把从左到右的边定位蓝色，反之为红色，显然符合要求。

CF429E Points and Segments

考虑差分一下，那么就变成了 \(l_i，r_{i}+1\) 单点加减。
对于每个位置，求出其被多少个区间覆盖了。
假设所有点都被偶数个区间覆盖了，那么最终一定是 \(0\)，也就是差分数组是 \(0\)，那么我们连一条 \(l_i\to r_i+1\) 的边，跑欧拉回路，根据边的方向加一减一一定是对的。
如果被奇数的区间覆盖，我们加一个区间 \([i,i]\) 即可，注意需要离散化。

trick2

• 特殊情况下解决哈密顿回路问题。

CF325E The Red Button

首先容易证明 \(n\) 为奇数无解，否则令 \(m=n/2\) 。
关键性质，\(x,x+m\) 拥有相同的入边，出边集合，其中 \(x\in [0,m)\) 。也就是说这对点某种程度上可以看成一个点
那么我们建一个 \(m\) 个点的图，每个点实际代表一对点 \([0,m)\) 。然后从 \(x\) 向 \(2x\bmod m,2x+1\bmod m\) 连边跑欧拉回路，正确性证明比较显然。

ZR2482 飞毯

就是让你构造一个长度为 \(n\) 的 \(01\) 字符串使得本质不同子串数量最大。
首先我们找一下答案的上界，显然有一个：\(\sum_i\min(2^i,n-i+1)\) ，接下来我们证明可以取到它。

求出满足 \(2^k+k-1\leq n\) 最大的 \(k\)，那么我们只需要要求长度为 \(k\) 的串都出现，长度为 \(k+1\) 的串两两不同即可。

我们把每个长度为 \(k+1\) 的区间看成一个数，然后从 \(x\) 向 $2x\bmod 2^{k+1},2x+1\bmod 2^{k+1} $连边，现在我们需要在找一条长度为 \(n-k\) 的不经过重复点的路径，使得 \(x,x+2^k\) 至少出现一个。

考虑仿照上题做法构造一个 \(2^k\) 的点的哈密顿环，此时可以发现把这个环当成长度为 \(k+1\) 时，\(x,x+2^k\) 恰好有一个已经确定出边了，那么因为出边集合相同，另一个也确定了。这样会形成若干个环，其中有一个长度为 \(2^k\) 的大环，并且 \(x,x+2^k\) 恰好一个在大环上。

注意假设 \(x,x+2^k\) 现在不在一个环上，交换 \(x,x+k\) 的出边可以使他们的环合并，那么我们不断合并环直到环长 \(\geq n-k\)，此时因为之前的环长 \(<n-k\) 且满足 \(x,x+2^k\) 至少出现了依次，我们只需要从之前的环的起点开始选，这样一定能把之前的环包上，就合法了。。

复杂度线性。