G. 手工巧克力

题目要意:求最小的$k$，使得对于集合${1,2,..n}$的任意有$k$个元素的子集$S$,都存在三个数$a,b,c \in {1...n},a \neq b \neq c$,满足$a+b,a+c,b+c \in S$

预期通过数:20

实际通过数:0?

怎么给我干成防ak了？

关键词：数学，构造，打表乱猜

每场比赛都应该有激动人心的guess环节

该题改编自CMO2012 Q6

不过，这里是算法竞赛，我们不用证明，猜到就行，具体的证明可以看这个

除了样例提到的$n=6$的情况外，答案都是$\frac{n}{2} +2$

以下提供一些比较算法竞赛的做法

解法1 构造

我们可以尝试构造一些尽可能长的非法序列

容易想到全体奇数是一种可能，因为奇+奇=偶，此时选择的$a,b,c$不论任何奇偶性都不可能成立

那么我们尝试加入一个偶数，如果加入$2$，依然不影响，因为不存在两个不同的正整数的和为$2$

再加入其他的偶数，都可以构造了

大胆的猜测答案是$\frac{n}{2} +2$

解法2 打表

码力比较强的同学很容易以实际上是$O(n^3(\frac{n}{2} +2)!)\approx O((n-2)!)$的复杂度打出一张表（大概能打到$n=12$），非常敢于guess的同学就能猜出答案了