题解

admin 2024-12-21 18:51:52

G. 手工巧克力

题目要意:求最小的,使得对于集合的任意有个元素的子集,都存在三个数,满足

预期通过数:20

实际通过数:0?

怎么给我干成防ak了?

关键词:数学,构造,打表乱猜

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

该题改编自CMO2012 Q6

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

除了样例提到的的情况外,答案都是

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

解法1 构造

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

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

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

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

大胆的猜测答案是

解法2 打表

码力比较强的同学很容易以实际上是的复杂度打出一张表(大概能打到),非常敢于guess的同学就能猜出答案了