Tenka Programmer Contest D - Crossing / 構造（附帶數學證明）

題

給定一正整數 N N N （ 1 ≤ N ≤ 1 0 5 1 \le N \le 10^5 1≤N≤105），求是否存在一個集合的集合 T T T 滿足：

• ∣ T ∣ ∈ N ∗ |T| \in N^* ∣T∣∈N∗
• ∀ S i ∈ T ， S i ⊆ { 1 , 2 , 3 , . . . , N } \forall S_i \in T，S_i \subseteq \{1,2,3,...,N\} ∀Si​∈T，Si​⊆{1,2,3,...,N}
• ∀ i , j ∈ [ 1 , ∣ T ∣ ] \forall i,j \in [1,|T|] ∀i,j∈[1,∣T∣] 且 i ≠ j i \neq j i̸​=j， ∣ S i ⋂ S j ∣ = 1 |S_i \bigcap S_j|=1 ∣Si​⋂Sj​∣=1
• ∀ i ∈ { 1 , 2 , 3 , . . . , N } \forall i\in \{1,2,3,...,N\} ∀i∈{1,2,3,...,N}， T T T 中存在恰好兩個不同的集合 S ， S ′ S，S' S，S′ 滿足 i ∈ S i \in S i∈S 且 i ∈ S ′ i \in S' i∈S′

如果存在這樣的集合 T T T ，請先輸出 “Yes” （不含引号），

然後接下來一行輸出一個正整數表示 ∣ T ∣ |T| ∣T∣。

接下來 ∣ T ∣ |T| ∣T∣ 行，每行先一個正整數，表示集合中的第 i i i 個元素 S i S_i Si​ 的大小 ∣ S i ∣ |S_i| ∣Si​∣。

接下來 ∣ S I ∣ |S_I| ∣SI​∣ 個正整數，表示 S i S_i Si​ 中的元素。

如果不存在滿足條件的集合 T T T ，請輸出“No”（不含引号）。

你隻需要按照如上方法輸出一個滿足條件的 T T T 即可。

S a m p l e   ： Sample\ ： Sample ：

輸入：3

輸出：

Yes

3

2 1 2

2 1 3

2 2 3

解

構造題。考場上不會證明，隻會瞎猜。

手玩小資料，發現 1 1 1 可以， 3 3 3 可以， 6 6 6 可以，自然會想是不是滿足 k ( k + 1 ) 2 ， k ∈ N ∗ \frac {k(k+1)}{2}，k \in N^* 2k(k+1)​，k∈N∗ 的數都可以。然後這類數有個好聽的名字叫三角形數1，是以我就畫了這樣的三角形：

然後發現可以這樣分：

（每個顔色代表一個集合）

這貌似是一種通解，于是我就寫了這個代碼，就過了，代碼如下：

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define R register
#define Maxn 100005

int main()
{
	R int n,sum=0;
	scanf("%d",&n);
	for (R int i=1;i<=n;++i)
	{
		sum += i;
		if(sum == n)
		{
			puts("Yes");
			printf("%d\n",i+1);
			R int j=1,cnt1=2;
			for (;j<=n;j+=cnt1,cnt1++)
			{
				printf("%d ",i);
				for (R int k=j-cnt1+2;k<=j;++k)printf("%d ",k);
				R int cnt2=cnt1-1;
				for (R int k=j+cnt2;k<=n;++cnt2,k+=cnt2)printf("%d ",k);
				puts("");
			}
			j=1,cnt1=2;
			printf("%d ",i);
			for (;j<=n;j+=cnt1,cnt1++)printf("%d ",j);
			return 0;
		}
	}
	puts("No");	
	return 0;
}
           

證明

但是我們不能隻滿足于猜結論！我們要嚴格證明！

我們接下來證明兩個分結論，進而證明原題結論。

三角形數一定能構造出符合條件的集合T

引理1：若 k ( k − 1 ) 2 \frac{k(k-1)}{2} 2k(k−1)​ 可以構造，并且構造出來的 ∣ T ∣ = k |T|=k ∣T∣=k，那麼 k ( k + 1 ) 2 \frac{k(k+1)}{2} 2k(k+1)​ 一定可以構造。

引理1證明：

設前者構造出來的集合組為

S 1 S_1 S1​

S 2 S_2 S2​

. . . ... ...

S k S_k Sk​

我們按照如下方法給每個集合添加一個數字

S 1 + { k ( k − 1 ) 2 + 1 } S_1+\{\frac{k(k-1)}{2}+1\} S1​+{2k(k−1)​+1}

S 2 + { k ( k − 1 ) 2 + 2 } S_2+\{\frac{k(k-1)}{2}+2\} S2​+{2k(k−1)​+2}

. . . ... ...

S k + { k ( k + 1 ) 2 } S_k+\{\frac{k(k+1)}{2}\} Sk​+{2k(k+1)​}

我們添上的數都是兩兩不同的，是以這些集合還是滿足兩兩公共元素恰好 1 個。

接下來，我們添的那些元素還要滿足恰好出現在 2 個集合中，于是我們再構造一個集合

S k + 1 = { k ( k − 1 ) 2 + 1 , k ( k − 1 ) 2 + 2 , . . . , k ( k + 1 ) 2 } S_{k+1}=\{\frac{k(k-1)}{2}+1,\frac{k(k-1)}{2}+2,...,\frac{k(k+1)}{2}\} Sk+1​={2k(k−1)​+1,2k(k−1)​+2,...,2k(k+1)​}

這個集合和前面 k k k 個集合的公共元素也都是恰好 1 個，并且 1 , 2 , . . . , k ( k + 1 ) 2 1,2,...,\frac{k(k+1)}{2} 1,2,...,2k(k+1)​ 這些數都恰好出現在 2 個集合中。是以這是一種合法的構造方案，是以引理1得證。

然後我們知道對于 1 1 1 顯然可以構造出 ∣ T ∣ = 2 |T|=2 ∣T∣=2 的滿足條件的 T T T，這樣我們根據數學歸納法就證明了原命題。

不是三角形數一定無法構造出滿足條件的集合T

對于一個确定的 N N N，假設能構造出集合 T T T

分析可知， ∑ ∣ S ∣ = N + k ( k − 1 ) 2 \sum|S| = N+\frac{k(k-1)}{2} ∑∣S∣=N+2k(k−1)​，其中 k = ∣ T ∣ k=|T| k=∣T∣

又根據已知條件， ∑ ∣ S ∣ = 2 N \sum|S| = 2N ∑∣S∣=2N

聯立，即 k 2 − k − 2 N = 0 k^2-k-2N=0 k2−k−2N=0，得 k = 1 + 8 N + 1 2 k=\frac{1+\sqrt {8N+1}}{2} k=21+8N+1

​​

可以證明當且僅當 N N N 為三角形數的情況下 k k k 為整數，也就是說若 N N N 不為三角形數，則不存在符合條件的 k k k 。

是以原命題得證。

1. 三角形數： https://baike.baidu.com/item/三角形數/5836794?fr=aladdin ↩︎