【USACO题库】2.2.4 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亮着。

简单的dfs，只需要枚举每种情况，最后在判断即可，但是有一个优化：

不会有C次，最多8次，优化为：

if c>8 then
        begin
                if odd(c) then
                        c:=5
                else
                        c:=4;
        end;

代码为：

var
        n,c,i,l,j:longint;
        a,b:array[0..1000]of longint;
        ans:array[0..10000]of string;
        s:string;
procedure does(n1:longint;var s:string);
var
        i:longint;
begin
        if n1=1 then
        begin
                for i:=1 to length(s) do
                        if s[i]='1' then s[i]:='0'
                        else s[i]:='1';
                exit;
        end;
        if n1=2 then
        begin
                for i:=1 to length(s) do
                        if i mod 2=1 then
                        begin
                                if s[i]='1' then s[i]:='0'
                                else s[i]:='1';
                        end;
                exit;
        end;
        if n1=3 then
        begin
                for i:=1 to length(s) do
                        if i mod 2=0 then
                        begin
                                if s[i]='1' then s[i]:='0'
                                else s[i]:='1';
                        end;
                exit;
        end;
        if n1=4 then
        begin
                for i:=0 to length(s) div 2 do
                        if s[3*i+1]='1' then s[3*i+1]:='0'
                        else s[3*i+1]:='1';
                if length(s)>n then delete(s,length(s),1);
                exit;
        end;
end;
function pd(s:string):boolean;
var
        i:longint;
begin
        for i:=1 to 100 do
        begin
                if a[i]=-1 then break;
                if s[a[i]]='0' then exit(false);
        end;
        for i:=1 to 100 do
        begin
                if b[i]=-1 then break;
                if s[b[i]]='1' then exit(false);
        end;
        exit(true);
end;
function pd1(s:string;l:longint):boolean;
var
        i:longint;
begin
        for i:=1 to l do
                if ans[i]=s then exit(false);
        exit(true);
end;
procedure dg(s:string;t:longint);
var
        i:longint;
        k:int64;
begin
        if t=c then
        begin
                if pd(s) and pd1(s,l) then
                begin
                        inc(l);
                        ans[l]:=s;
                end;
                exit;
        end;
        for i:=1 to 4 do
        begin
                does(i,s);
                dg(s,t+1);
                does(i,s);
        end;
end;
begin
        readln(n,c);
        if c>8 then
        begin
                if odd(c) then
                        c:=5
                else
                        c:=4;
        end;
        for i:=1 to 100 do
        begin
                read(a[i]);
                if a[i]=-1 then break;
        end;
        for i:=1 to 100 do
        begin
                read(b[i]);
                if b[i]=-1 then break;
        end;
        for i:=1 to n do s:=s+'1';
        dg(s,0);
        if l=0 then
        begin
                writeln('IMPOSSIBLE');
        end;
        for i:=1 to l-1 do
                for j:=1 to l-i do
                        if ans[j]>ans[j+1] then
                        begin
                                ans[0]:=ans[j];
                                ans[j]:=ans[j+1];
                                ans[j+1]:=ans[0];
                        end;
        for i:=1 to l do writeln(ans[i]);
end.

大神的方法为：

var
  light:array[1..8,1..6]of longint=(
                             (0,0,0,0,0,0),
                             (0,0,1,1,1,0),
                             (0,1,0,1,0,1),
                             (0,1,1,0,1,1),
                             (1,0,0,1,0,0),
                             (1,0,1,0,1,0),
                             (1,1,0,0,0,1),
                             (1,1,1,1,1,1));
  zxczs:array[1..8]of longint=(1,2,1,1,2,1,2,0);
  mv:array[1..8]of boolean;
  n,c,x,xc,xcc,i,j:longint;
begin
  readln(n);
  readln(c);
  read(x);
  fillchar(mv,sizeof(mv),false);
  while x<>-1 do
   begin
     if x=-1 then readln;
     x:=(x-1)mod 6+1;
     for i:=1 to 8 do
     if (not mv[i])and(light[i,x]<>1) then mv[i]:=true;
     read(x);
     if x=-1 then readln;
   end;
  read(x);  xcc:=0;
  fillchar(xc,sizeof(xc),255);
  while x<>-1 do
   begin
     if x=-1 then readln;
     x:=(x-1)mod 6+1;
     for i:=1 to 8 do
     if (not mv[i])and(light[i,x]<>0) then mv[i]:=true;
     read(x);
     if x=-1 then readln;
   end;
  for i:=1 to 8 do
   begin
     if (mv[i])or(not((c-zxczs[i]<0)or(c-zxczs[i]=1))) then continue;
     mv[i]:=true;
   end;
  for i:=1 to 8 do
   begin
     xc:=0;
     if mv[i] then continue;
     for j:=1 to n do
       begin
          x:=(j-1)mod 6+1;
          xc:=1; xcc:=1;
          write(light[i,x]);
       end;
     if xc=1 then writeln;
   end;
   if xcc=0 then writeln('IMPOSSIBLE');
end.

秒客网

【USACO题库】2.2.4 Party Lamps派对灯