題目來(lái)源

取模下序列構(gòu)造

是否存在 \(3\) 個(gè)長(zhǎng)度為 \(n\) 的 \([0,n)\) 的排列 \(a,b,c\)，使得 \(a_i+b_i=c_i\mod n\)

遇到取模考慮奇偶性，不要想太復(fù)雜，考慮 \(n\) 為奇數(shù)的時(shí)候直接 \(a=b=~0,1,2,3,4,…\)，\(c=~{0,2,4,…,n-1,1,3,5,…}\)。

偶數(shù)發(fā)現(xiàn)不好寫(xiě)，考慮證明無(wú)解，首先去掉取模，發(fā)現(xiàn)兩端和對(duì) \(n\) 取模不相等，易證無(wú)解。

特殊完全圖三元環(huán)構(gòu)造

\(2^n?1\) 個(gè)點(diǎn)的完全圖，你需要找出盡量多邊互不相交的三元環(huán)，輸出最優(yōu)情況下的方案。

考慮上界，是 \(\frac{(2^n-1)\cdot (2^n-2)}{6}\)，可以證明這是一個(gè)整數(shù)，考慮取到這個(gè)上界。

考慮三個(gè)點(diǎn)滿(mǎn)足 \(x\oplus y\oplus z=0\) 我們發(fā)現(xiàn)這種構(gòu)造滿(mǎn)足在枚舉 \(x,y\) 的時(shí)候 \(z\ne x,z\ne y\) 而且任意兩數(shù)相同時(shí)下一個(gè)數(shù)也確定，很完美，所以這個(gè)上界可以取到。

完全圖固定數(shù)量獨(dú)立集構(gòu)造

\(2n\) 個(gè)點(diǎn)的完全圖，要把這些點(diǎn)分成 \(2n?1\) 組，每組 \(n\) 條邊，且每組都是一個(gè)匹配（任意兩條邊沒(méi)有公共點(diǎn)）

考慮一下我們有個(gè)簡(jiǎn)單想法，構(gòu)造連出去的圈圈，類(lèi)似 \(i\to i+1,i-1\to i+2\)。或者中間空一個(gè)的構(gòu)造，但是發(fā)現(xiàn)容易重復(fù)，考慮兩種一起構(gòu)造，增加標(biāo)志物來(lái)避免重復(fù)。

我們對(duì)第 \(i\) 組，讓 \(i\) 向 \(2n\) 連邊，然后 \(i-1\to i+1,i-2\to i+2\) 直到邊界，然后右側(cè)用 \(x\to x+1,x-1\to x+2\) ，用這兩種構(gòu)造結(jié)合即可。

完全圖構(gòu)造樹(shù)

\(n\) 個(gè)點(diǎn)的完全圖，從中選出盡量多互不相交的樹(shù)，輸出方案。

考慮先構(gòu)造上界 \(\frac{n(n-1)}{2(n-1)}=\frac{n}{2}\)，考慮取到上界，用歸納法：

我們假設(shè) \(2k\) 的方案構(gòu)造出來(lái)了，接著構(gòu)造 \(2k+1,2k+2\) 就可以了。

考慮怎么構(gòu)造：

對(duì)于 \(2k+1\)：我們直接用前 \(k\) 條邊連上去就好了。

對(duì)于 \(2k+2\)：我們考慮先構(gòu)造相同的 \(2k+1\)，然后用 \(2k+2\) 的 \([k+1,2k]\) 這些邊分別都連上樹(shù)，然后用剩下的邊全部連成一棵樹(shù)就可以了。