题目来源
取模下序列构造
是否存在 \(3\) 个长度为 \(n\) 的 \([0,n)\) 的排列 \(a,b,c\),使得 \(a_i+b_i=c_i\mod n\)
遇到取模考虑奇偶性,不要像太复杂,考虑 \(n\) 为奇数的时候直接 \(a=b=~0,1,2,3,4,…\),\(c=~{0,2,4,…,n-1,1,3,5,…}\)。
偶数发现不好写,考虑证明无解,首先去掉取模,发现两端和对 \(n\) 取模不相等,易证无解。
特殊完全图三元环构造
\(2^n−1\) 个点的完全图,你需要找出尽量多边互不相交的三元环,输出最优情况下的方案。
考虑上界,是 \(\frac{(2^n-1)\cdot (2^n-2)}{6}\),可以证明这是一个整数,考虑取到这个上界。
考虑三个点满足 \(x\oplus y\oplus z=0\) 我们发现这种构造满足在枚举 \(x,y\) 的时候 \(z\ne x,z\ne y\) 而且任意两数相同时下一个数也确定,很完美,所以这个上界可以取到。
完全图固定数量独立集构造
\(2n\) 个点的完全图,要把这些点分成 \(2n−1\) 组,每组 \(n\) 条边,且每组都是一个匹配(任意两条边没有公共点)
考虑一下我们有个简单想法,构造连出去的圈圈,类似 \(i\to i+1,i-1\to i+2\)。或者中间空一个的构造,但是发现容易重复,考虑两种一起构造,增加标志物来避免重复。
我们对第 \(i\) 组,让 \(i\) 向 \(2n\) 连边,然后 \(i-1\to i+1,i-2\to i+2\) 直到边界,然后右侧用 \(x\to x+1,x-1\to x+2\) ,用这两种构造结合即可。
完全图构造树
\(n\) 个点的完全图,从中选出尽量多互不相交的树,输出方案。
考虑先构造上界 \(\frac{n(n-1)}{2(n-1)}=\frac{n}{2}\),考虑取到上界,用归纳法:
我们假设 \(2k\) 的方案构造出来了,接着构造 \(2k+1,2k+2\) 就可以了。
考虑怎么构造:
对于 \(2k+1\):我们直接用前 \(k\) 条边连上去就好了。
对于 \(2k+2\):我们考虑先构造相同的 \(2k+1\),然后用 \(2k+2\) 的 \([k+1,2k]\) 这些边分别都连上树,然后用剩下的边全部连成一棵树就可以了。