USACO Section2.2 Party Lamps - Xavier's Blog

USACO Section2.2 Party Lamps - Xavier's Blog

一开始是想，给定某一盏灯的最终状态，就可知道相关按钮拨动次数的奇偶。比如，state[1] = 0，我就可以知道B1+B2+B4为偶数。因此，对于给出的部分灯的最终状态，就可得到一系列的关于按钮的约束条件（可能有重复），再枚举B1～B4的情况，使其既满足B1+B2+B3+B4 = C，又满足上述约束条件，就可以得到合理的按钮拨动次数的集合了。但编程实现下来，发现C⁴无法满足时限，而且代码想到丑陋！

后来通过网上一些文章的提示，想到某一按钮按两次跟没有按是同样的情况，所以每种按钮只有按0次和按1次这两种情况，复杂度一下就降到2⁴了。对于按钮的每种情况，分析以下属性：

• 按1次按钮的总个数CBn。它代表了按钮至少按下了CBn次，因此因满足条件C >= CBn

• CBn的奇偶性。它应该跟C的奇偶性相同

• 已确定的部分灯的状态是否与其相符

如果满足了这三个约束条件，就是答案之一了。

////////////////////////////////////////////////////////////////////////////////////////////

看了USACO的官方分析后，发现题目中还有许多巧妙的地方：

• 无论n和c为多大，最终灯的状态都是以长度6为循环的

• 大于4且为偶数的c，可以转化为4；大于3且为奇数的c，可以转化为3

对于c=4，可分为：

• 4个不同的按钮按下；

• 2个不同的按钮按下；

• 0个按钮按下。

对于c=3，可分为：

• 3个不同的按钮按下；

• 1个不同的按钮按下。

对于c=2：

• 2个不同按钮按下；

• 0个不同按钮按下。

对于c=1：

• 1个不同按钮按下

Read full article from USACO Section2.2 Party Lamps - Xavier's Blog