Party Lamps_usaco2.2.4_暴力?

NO IMAGE

題目描述 Description


在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)上的數值和經過若干操作後某些燈的狀態。寫一個程式去找出所有燈最後可能的與所給出資訊相符的狀態,並且沒有重複。

輸入描述 Input Description


不會有燈會在輸入中出現兩次。

第一行: N。

第二行: C最後顯示的數值。

第三行: 最後亮著的燈,用一個空格分開,以-1為結束。

第四行: 最後關著的燈,用一個空格分開,以-1為結束。

輸出描述 Output Description


每一行是所有燈可能的最後狀態(沒有重複)。每一行有N個字元,第1個字元表示1號燈,最後一個字元表示N號燈。0表示關閉,1表示亮著。這些行必須從小到大排列(看作是二進位制數)。

如果沒有可能的狀態,則輸出一行’IMPOSSIBLE’。

樣例輸入 Sample Input


10
1
-1
7 -1
在這個樣例中,有10盞燈,只有1個按鈕被按下。最後7號燈是關著的。

樣例輸出 Sample Output


0000000000
0101010101
0110110110
在這個樣例中,有三種可能的狀態:

所有燈都關著

1,4,7,10號燈關著,2,3,5,6,8,9亮著

1,3,5,7,9號燈關著,2, 4, 6, 8, 10亮著

題解 Analysis


因為連著改變的狀態只可能是11個、22個或者33個,那麼受影響的狀態只有1∗2∗3=61*2*3=6 位
試著dfs了一下但是好像錯了,大概推了推發現操作的組合就88種,打個1∗81*8的表記錄一下操作和所需步數,輸入的時候找一下就可以了
分別用onon和offoff兩個變數記錄開與關的限制條件並壓成二進位制數,合法狀態滿足且僅滿足on&status==0on&status==0和off&status==offoff&status==off
位運算老是打錯,蛋疼

程式碼 Code


/*
ID:wjp13241
PROG:lamps
LANG:C  
*/
#include <stdio.h>
#include <cstring>
using namespace std;
int t[8]={0,28,42,54,9,21,35,63};
int steps[8]={1,2,1,2,1,1,2,0};
int f[7];
int n,m;
int get(int x)
{
return !(x%6)?6:x%6;
}
void print(int x)
{
memset(f,0,sizeof(f));
do{
f[  f[0]]=x%2;
}while(x/=2);
f[0]=6;
for (int i=1;i<=n;i  )
printf("%d",f[get(i)]);
printf("\n");
}
int main()
{
freopen("lamps.in","r",stdin);
freopen("lamps.out","w",stdout);
int tmp,on=0,off=0,cnt1=0,cnt2=0;
scanf("%d%d",&n,&m);
while (scanf("%d",&tmp)&&tmp!=-1)
on=on|(1<<(get(tmp)-1)),cnt1  ;
while (scanf("%d",&tmp)&&tmp!=-1)
off=off|(1<<(get(tmp)-1)),cnt2  ;
if (!m)
{
if (cnt1==n)
while (n--)
printf("0");
else
if (!cnt2)
while (n--)
printf("1");
else
if (cnt2)
printf("IMPOSSIBLE");
printf("\n");
return 0;
}
bool flag=false;
for (int i=0;i<8;i  )
{
int a=on&t[i];
int b=off&t[i];
if (!b&&(a==on)&&m>steps[i])
{
print(t[i]);
flag=true;
}
}
if (!flag)
printf("IMPOSSIBLE\n");
fclose(stdin);
fclose(stdout);
return 0; 
}