USACO/lamps

分析

还可以从另外一个方面考虑： 从按键个数而言，如果C大于>4，我们把它不断减小2，使它小于4（这个过程也就相当于把重复的按键去掉），最后我们再枚举每一种按键所能得到的结果，加以判断就可以了。

分析

每个按钮按2次和没按效果是一样的。所以每个按钮或者按或者不按，一共有2^4=16种状态。枚举每个按钮是否按下，然后生成结果，排序输出即可（注意判重）。

另外灯1和灯7,2和8,3和9...是一样的因此当N>=6时只需处理前6个,排序时转换为10进制数, 输出时反复输出前6个的状态.

深究：

这道题如果深究的话会变得非常简单， 但是提前声明，如果对这道题兴趣不大，或者是初学者，建议跳过， 刚才的分析已经足以过这道题。 我们现在记不按按钮，以及按下1，2，3，4按钮分别O，①，②，③，④， 那么，按下3，4，可以记为③④，以此类推， 我们发现一个问题，那就是①，②，③之间微妙的关系， ①②=③，而②③=①，①③=②（可以自己试试），于是我们知道，①②③也相当与不按，即相差3的倍数也可互相转换；

所以，所谓前四个的16种按法其实只有8种， 分别为：O,①，②，③，④，①④，②④，③④；

然后讨论c， 由于当c>4时，均可化为当c<=4的情况， 所以我们先讨论当c<=4的情况，

当c=0时，只有一种O；

当c=1时，四种：①，②，③，④；

当c=2时，除了④均可（可以自己想想）；

当c=3时，由于3-1=2，所以c=1的情况都满足，而在c=2中，把所有有前三类的展开，如①④变为②③④， 可知满足c=2的同时满足c=3，所以c=3其实是c=2和c=1的并集，即所有按法均可。

当c=4时，由于4-1=3（①②③相当于不按），且4-2=2，由上，c=4也是所有按法均可。

当c>4时，我先有一个引理：对于任意的正整数n>1，均可写成n=2*p+3*q(p,q为非负整数）的形式， 证明如下：若n为偶数，必然成立，若n为奇数，必然大于2，则n-3必为非负偶数，得证。 由这个引理我们可以知道，任意c>4均可写成，c=2*p+3*q+3(p,q为非负整数）的形式，而可知， 对于两个相同的按键，以及情况①②③（按键三次），均相当于不按，所以任意c>4均可化归为c=3的情况， 即当c>4时，所有按法均可。

综上所述，

当c=0时，只有一种O；

当c=1时，四种：①，②，③，④；

当c=2时，除了④均可；

当c>2时，所有按法均可。

好了，这样一来就非常简单了， 只有四种情况，8种按法。

---

另一种判断按下按钮数是否为C的方法（与上面的差不多）：

在判断是否按了c次时，就不好直接判断了，因为我们的思路是：“每个按钮按2次和没按效果是一样的。所以每个按钮或者按或者不按” 但是实际上每个按钮按2次和没按效果有细微差别——就是按的次数。

为了解决这个问题，我从奇偶考虑：假如有两种情况结果相同，但按的次数不同，分别为a,b。而如果a-b是偶数，那么按的次数少的那种情况完全可以通过按2K次来凑够次数（k为正整数），因此，我们可以用mod语句来完成判断是否能凑够c次，用此方法可以发现不用判重了，因为我搜索的是基本情况，而其他的情况自然被无形的滤掉了 具体过程如下：（change(k)表示按第k个按钮，在这里就不贴出了。）

function check:boolean;
var
  i:integer;
begin
  for i:=1 to cy do
    if now[y[i]]<>1 then exit(false);
  for i:=1 to cny do
    if now[ny[i]]<>0 then exit(false);
  if ((c mod 2)=(tn mod 2)) {检查是否能凑够c次} and (tn<=c) then
    exit(true)
    else exit(false);
end;
 
procedure  tryit(k:integer);
var
  i,j,t:integer;
begin
  if (k>4) then begin if check then rec; exit; end;
  change(k);
  inc(tn);
  tryit(k+1);//按
  dec(tn);
  change(k);
  tryit(k+1); //不按
end;（by ymfoi）

---

关于状态的记录，这题可以用位运算简化，如上面所说，用一个longint存储前6位的状态就行了。而4种操作也很简单，用异或就可以搞定：

操作1：异或(111111)2=63

操作2：异或(010101)2=21

操作3：异或(101010)2=42

操作4：异或(001001)2=9 【这个地方不对是(100100)2=36，轻信别人我调了一节课...】

//由于位数是从左向右数的，因此操作4是正确的。

判断状态是否符合题意，则可以用&和|完成：

先将题目给出的灯的状态映射到0～5之间，即(灯的编号-1)%6

生成一个6位二进制数isOn，其中题目给出是ON的灯的对应位为1，其余为0

生成一个6位二进制数isOff，其中题目给出是OFF的灯的对应位为0，其余为1

若当前状态state满足：

(state&isOn)==isOn && (state|isOff)==isOff

则state满足题目要求。

另外，关于判断某一状态是否能由c次按键得到，如果某一状态能由x次按键得到，若c-x为偶数，则该状态进行c-x次操作1后状态不变。

如果用DFS或枚举，x<=4即可。

详细请见参考代码里的GeorgeG1的C++源程序

---

首先不要读错了题,不是正好按了c次，是<=c次都可以。-------------（不知道你怎么读出这么深奥的题意 - - 表示无奈）

其实不用这么麻烦。只用记录和前四个检验前四个灯就行了。

为什么呢。

1号灯 ——代表了所有3的倍数+1的奇数号灯

2号灯 ——代表了所有不是3的倍数+1的偶数号灯

3号灯 ——代表了所有不是3的倍数+1的奇数号灯

4号灯 ——代表了所有3的倍数+1的偶数号灯

读入数据的时候就可以处理

例如

  read(tmp);
  while tmp<>-1 do
   begin
     if (tmp-1) mod 3=0 then
      if odd(tmp) then a[1]:=1 else a[4]:=1;
     if (tmp-1) mod 3<>0 then
      if odd(tmp) then a[3]:=1 else a[2]:=1;
     read(tmp);
   end;
   readln;

处理的过程其实就是16种方案

每个按钮都可以选择按还是不按

把每个方案求出来就是，当然最好记录一下每种方案最少按键次数

如果这个次数<=c就可以输出了。

至于按钮的处理。

你可以选择用xor.

因为只需要记录前4个.所以一个b[]:longint就够了。

首先全部赋值成15 即二进制下的1111

按钮1 —— b[x] xor 15 (1111)

按钮2 —— b[x] xor 10 (1010)

按钮3 —— b[x] xor 5 (0101)

按钮4 —— b[x] xor 9 (1001)

至于输出

例如先将前四个数放进zl数组里

  for i:=1 to n do
   begin
     if i<=4 then write(zl[i]);
     if i>4 then
      if (i-1) mod 3 =0 then
       if odd(i) then write(zl[1]) else write(zl[4]);
     if i>4 then
      if (i-1) mod 3 <>0 then
       if odd(i) then write(zl[3]) else write(zl[2]);
   end;
   大功告成。  by  重庆一中zzl

 补充一点点，输出时候用一个1 shl 6 -1 的布尔数组，转换成十进制数存在布尔数组里就可以解决字典序问题，不需要排序了。

==============================================================================

我想补充一下楼上的说法，我觉得题目中所要求的状态还是在恰好c次是的状态，以下是原题“Write a program to determine all the possible final configurations of the N lamps that are consistent with the given information, without repetitions. ”我不知道你英语怎么样……反正…… 而按你的理解之所以也可以做对是偶然。本身题目中四种操作都是只有奇偶两种状态的，而任意两种状态之间都是可以在4步之内相互转化的，也就是说，超出四步以后任意状态都是可以到达的，所要做的就是符合题目的目标状态。

   事实上这个题目是可以根据奇偶性解决的。
   每種操作都只有奇偶两种状态，因此只要确定每种操作的奇偶性就可以确定灯的状态了。
   按照楼上的枚举毫无疑问会有操作不同但状态相同的情况（即使做少操作数也会有，比如1和2、3），还得判重。
   出现这个原因是因为其实有的状态是根本到不了的，就是说与给出的C是不相符合的。
   我们可以用三重0..1的循环来确定操作1到3的奇偶，那么4就可以由c和前面三个状态来确定。
   其实任意操作按键不同但出现重复的情况的操作总数的奇偶都是不同的（废话，要不不就成了一种情况了……），
   一旦操作4的奇偶确定，c更确定了，那么前三种操作和的奇偶也就确定了，从而不可能会出现重复。
   你可以自己考虑一下，或者试着列一下。
code： 
for a1:=0 to 1 do
if c-a1>=0 then              {加IF就可以不用单独处理c<4的情况}
for a2:=0 to 1 do
 if c-a1-a2>=0 then
 for a3:=0 to 1 do
  if c-a1-a2-a3>=0 then
   begin
   a4:=(c-a1-a2-a3) mod 2;
   sou;                      {判断是否符合要求}
   end;
        OK，解说完毕，就此闪人。                   ----做好事不留名的活雷锋

小于C次的那种做法可行是因为，你一种按钮重复按两次使他没有改变状态。 1111

一种跟诸位截然不同的方法（代码是比较简洁的）

这个题，首先，我们需要知道这个电灯系统的一个比较邪恶的性质，其实不论咋搞，都是每隔六位循环的！！ 有了这个，我们就可以使用常量表来搞了。自己动一下手，不要偷懒。自己推算一下所有的情况，用light[][]表示这个情况的集合（仅包含前六个灯，并且已经人工进行了排 序），然后再用一个数组minnum记录light[][]中对应的每种情况的最少操作次数，然后，呵呵，就不用我多说了，诸位该自己爽了。。。。 爆一下我自己的常量表：

light[10][10]={
                {},
                {0,0,0,0,0,0,0},
                {0,0,0,1,1,1,0},
                {0,0,1,0,1,0,1},
                {0,0,1,1,0,1,1},
                {0,1,0,0,1,0,0},
                {0,1,0,1,0,1,0},
                {0,1,1,0,0,0,1},
                {0,1,1,1,1,1,1},
               };
 
minnum[50]={0,1,2,1,1,2,1,2,0};

具体参考我的c++代码（talenth1/c++参考代码）

//这个是不是有点问题的 就是light[8]的最少操作次数是0，但只操作1次就不能出现这种状态

类似的质疑：010101这个状态应该能1次按出来，同样的我没能发现011011 用2次翻转的方法 我觉得应该是这样

000000 能1 2 3 4 5……

010101 能1 2 3 4 5……

101010 能1 2 3 4 5……

111111 能0 2 3 4 5……

100100 能2 3 4 5 6……

011011 能1 3 4 5 6……

110001 能2 3 4 5 6……

001110 能2 3 4 5 6……

模拟退散！

引用第一位朋友的话： “综上所述，

当c=0时，只有一种O；

当c=1时，四种：①，②，③，④；

当c=2时，除了④均可；

当c>2时，所有按法均可。

好了，这样一来就非常简单了， 只有四种情况，8种按法。 ” 由此可见，最终态只有8种。而这些灯是“6个一组，每组相同”的。所以读入开关灯的时候只用 mod 6。如果两个灯编号 mod 6 相同，而开关状态不同，如1号灯开而7号灯关(1 mod 6=7 mod 6)，就直接输出'IMPOSSIBLE'。

如果这里的灯通过了，就再把每个灯(编号 mod 6)和那8种状态比较，如果符合就输出，没有符合就输出'IMPOSSIBLE'。

这样两个优化一起用，就全部 0 sec AC 了。

不多加考虑,注意一点就够了

我脑子比较简单,所以说最简单的 就是如上面诸位所说,注意到,虽然灯最多有100盏,但6盏以后的灯都是前6盏的重复 即BFS的每一层最多产生2^6 = 64种状态 利用这一点就足以优化到全部0.0sec

参考代码

c++
c
pascal
Java

引用

[1]

[2]