【USACO題庫】2.2.4 Party Lamps派對燈
(File IO): input:lamps.in output:lamps.out
題目描述
在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)上的數值和經過若干操作后所有燈的狀態，寫一個程式去找出所有燈最后可能的與所給出資訊相符的狀態，并且沒有重復，
輸入
不會有燈會在輸入中出現兩次，
第一行: N，
第二行: C最后顯示的數值，
第三行: 最后亮著的燈,用一個空格分開，以-1為結束，
第四行: 最后關著的燈,用一個空格分開，以-1為結束，
輸出
每一行是所有燈可能的最后狀態(沒有重復)，每一行有N個字符，第1個字符表示1號燈，最后一個字符表示N號燈，0表示關閉，1表示亮著，這些行必須從小到大排列（看作是二進制數），
如果沒有可能的狀態，則輸出一行’IMPOSSIBLE’，
樣例輸入
10
1
-1
7 -1
在這個樣例中，有10盞燈，只有1個按鈕被按下，最后7號燈是關著的，
樣例輸出
0000000000
0101010101
0110110110
在這個樣例中，有三種可能的狀態：
所有燈都關著
1,4,7,10號燈關著，2,3,5,6,8,9亮著，
1,3,5,7,9號燈關著，2, 4, 6, 8, 10亮著，
資料范圍限制
無
初看這題，大家的思路也許是這樣的：模擬、列舉……
我第一次看這道題的時候，我也是這么想的，模擬、列舉……直到半夜醒來，我才突然間想到……
如果按偶數次相同的鍵，那這跟沒按是一樣的，如果按2、3鍵（即改變編號為奇數或偶數的數，也就是改變所有的數），那這跟只按1鍵是一樣的，即使所有按鍵都沒有被重復按下，但也有可能出現重復，所以，大家會發現，無論n和c有多大，可能的狀態最多只有八種！！！！！
1、不按（同按1、2、3鍵） 當c=1時無法做到
2、按1鍵（同按2、3鍵）任何時候都可以做到
3、按2鍵（同按1、3鍵）任何時候都可以做到
4、按3鍵（同按1、3鍵）任何時候都可以做到
5、按4鍵（同按1、2、3、4鍵）當c=2時無法做到
6、按1、4鍵（同按2、3、4鍵）當c=1時無法做到
7、按2、4鍵（同按1、3、4鍵）當c=1時無法做到
8、按3、4鍵（同按1、2、4鍵）當c=1時無法做到
例如，按1、1、1、2、3、3、3、3、4鍵，相當于按1、2、4鍵，同3、4鍵，
所以我們只需要做8次判斷，判斷一下能不能做到8種情況中的各個情況，再判斷一下這種情況是不是可能的最后情況，如果兩個條件都滿足，那就輸出，當然別忘了，在程式一開始的時候，要做一次c=0的特判，而且在判斷的時候要按最后結果的升序順序判斷，
#include<cstdio>
int n,a[105],b[105],d[105],p,l,g,c;
void gb(int a1,int a2,int a3,int a4)
{
for(int i=1;i<=n;++i)
{
if(a1==1)
d[i]=!d[i];//改變（取反）
if(a2==1&&i%2==1)
d[i]=!d[i];
if(a3==1&&i%2==0)
d[i]=!d[i];
if(a4==1&&i%3==1)
d[i]=!d[i];
}
}
int pd()
{
for(int i=1;i<=l;++i)
if(d[a[i]]==0)
return 0;
for(int i=1;i<=g;++i)
if(d[b[i]]==1)
return 0;
return 1;
}
void hua()
{
for(int i=1;i<=n;++i)
printf("%d",d[i]);
printf("\n");
p=1;
}
void cz(int a1,int a2,int a3,int a4)
{
for(int i=1;i<=n;++i) d[i]=1;//初始化全是亮的
gb(a1,a2,a3,a4);//改變燈的狀態
if(pd())//判斷最后結果是否是可能的
hua();//輸出
}
int main()
{
freopen("lamps.in","r",stdin);
freopen("lamps.out","w",stdout);
scanf("%d%d",&n,&c);
while(1)//輸入
{
l++;
scanf("%d",&a[l]);
if(a[l]==-1) break;
}
l--;
while(1)
{
g++;
scanf("%d",&b[g]);
if(b[g]==-1) break;
}
g--;
if(c==0)//特判
{
if(g!=0)
printf("IMPOSSIBLE");
else
{
for(int i=1;i<=n;++i) d[i]=1;
hua();
}
return 0;
}
if(l==0)//判斷8種情況
cz(1,0,0,0);//按1
if(c!=1)
cz(0,0,1,1);//按3、4
cz(0,1,0,0);//按2
if(c!=2)
cz(0,0,0,1);//按4
if(c!=1)
cz(1,0,0,1);//按1、4
cz(0,0,1,0);//按3
if(c!=1)
cz(0,1,0,1);//按2、4
if(c!=1&&g==0)
cz(0,0,0,0);//不按
if(p==0)
printf("IMPOSSIBLE");
return 0;
}
我：來人！！！把燈砸了！！！
不見不散
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/258985.html
標籤：其他