G. 手工巧克力
题目要意:求最小的,使得对于集合的任意有个元素的子集,都存在三个数,满足
预期通过数:20
实际通过数:0?
怎么给我干成防ak了?
关键词:数学,构造,打表乱猜
每场比赛都应该有激动人心的guess环节
该题改编自CMO2012 Q6
不过,这里是算法竞赛,我们不用证明,猜到就行,具体的证明可以看这个
除了样例提到的的情况外,答案都是
以下提供一些比较算法竞赛的做法
解法1 构造
我们可以尝试构造一些尽可能长的非法序列
容易想到全体奇数是一种可能,因为奇+奇=偶,此时选择的不论任何奇偶性都不可能成立
那么我们尝试加入一个偶数,如果加入,依然不影响,因为不存在两个不同的正整数的和为
再加入其他的偶数,都可以构造了
大胆的猜测答案是
解法2 打表
码力比较强的同学很容易以实际上是的复杂度打出一张表(大概能打到),非常敢于guess的同学就能猜出答案了