USACO：2.2.4 Party Lamps 派对灯
USACO：2.2.4 Party Lamps 派对灯
一、题目描述
★Party Lamps 派对灯在IOI98 的节日宴会上,我们有N(10<=N<=100)盏彩色灯,他们分别从1 到N 被标上号码.
这些灯都连接到四个按钮:按钮1:当按下此按钮,将改变所有的灯:本来亮着的灯就熄灭,本来是关着的灯被点亮.
按钮2:当按下此按钮,将改变所有奇数号的灯.
按钮3:当按下此按钮,将改变所有偶数号的灯.
按钮4:当按下此按钮,将改变所有序号是3*K+1(K>=0)的灯.例如:1,4,7...
一个计数器C 记录按钮被按下的次数.
当宴会开始,所有的灯都亮着,此时计数器C 为0.
你将得到计数器C(0<=C<=10000)上的数值和经过若干操作后某些灯的状态. 写一个程序去找出所有的灯最后可能的与所给出信息相符的状态,并且没有重复.
PROGRAM NAME: lamps
INPUT FORMAT
不会有灯会在输入中出现两次.
第一行: N.
第二行: C 最后显示的数值.
第三行: 最后亮着的灯,用一个空格分开,以-1 为结束.
第四行: 最后关着的灯,用一个空格分开,以-1 为结束.
SAMPLE INPUT (file lamps.in)
10
1
-1
7 -1
在这个样例中,有10 盏灯,只有1 个按钮被按下.最后7 号灯是关着的.
OUTPUT FORMAT
每一行是所有灯可能的最后状态(没有重复).每一行有N 个字符,第1 个字符表示1 号灯,最后一个
字符表示N 号灯.0 表示关闭,1 表示亮着.这些行必须从小到大排列（看作是二进制数）.
如果没有可能的状态,则输出一行'IMPOSSIBLE'.
SAMPLE OUTPUT (file lamps.out)
0000000000
0101010101
0110110110
在这个样例中,有三种可能的状态:
所有灯都关着1,4,7,10 号灯关着,2,3,5,6,8,9 亮着.
1,3,5,7,9 号灯关着,2, 4, 6, 8, 10 亮着.
二、题目解答
每个开关按钮按2次和没按效果是一样的。所以每个按钮或者按或者不按，一共有2^4=16中开关状态。枚举每个按钮是否按下，然后生成结果，看是否满足条件，排序输出即可（注意判重）。
另外，根据四种开关的操作效果，灯状态的周期为6，因此当N>=6时只需处理前6个灯, 排序时转换为10进制数, 输出时反复输出二进制的前6个的状态.
源代码
#include
#include
#include
#include
#include 官方答案
//There are a number of insights required for this problem.
//The main insight is that no matter which switches get pressed, the light pattern will repeat every six lamps.
//Another insight is that the order of switch presses does not matter,
//and that pressing a switch twice is the same as not pressing a switch at all.
//Any even number of switch presses greater than four might as well just be four switch presses,
//and any odd number greater than three might as well just be three presses.
//We can treat the light information as describing only the first six lamps (by treating lamp n as lamp (n mod 6)),
//and only try pressing each switch once or not at all.
//To maintain the actual information about which lights are on, we use an integer holding six bits.
//The least significant bit is light 6, the next least is light 5, and so on.
//This has the effect that treating these bit strings as normal numbers sorts the same way that we need to print them.
//Switches are represented as bit vectors that say which lights get toggled.#include
#include
#include
#include #define MAXLAMP 6 //定义最大灯数 6，因为灯的状态具有循环特性。
#define LAMPMASK ((1<= i.
void
search(int lights, int i, int n)
{if(n == 0) {if((lights & known) == ison)poss[lights] = 1; //return;}for(; i<4; i++) //开关操作递增，不会重复。每个类型操作，最多操作一次（因为重复没有意义，是指操作总数化简后）search(lights ^ flip[i], i+1, n-1); //异或，相当于一次开关操作
}void
printseq(FILE *fout, int lights)//输出结果
{int i;char s[100+1];for(i=0; i 4){if(nswitch%2 == 0)nswitch = 4;//偶数情况，4/2/0elsenswitch = 3;//奇数情况，3/1}for(; nswitch >= 0; nswitch -= 2)//搜索对应情况search(LAMPMASK, 0, nswitch);//LAMPMASK灯的原始状态，0代表第一种开关操作，nswitch代表最多几次开关操作impossible = 1;for(i=0; i<(1<
由于自身是初学者，编程能力有限，未达到专业程序员的水平，可能误导大家，请大家甄读；文字编辑也一般，文中可能会有措辞不当。博文中的错误和不足敬请读者批评指正。
部分引自 http://pingce.ayyz.cn:9000/usaco/20110129214306/lamps_001.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！