首页 > 代码库 > 【USACO 2.2.4】派对灯
【USACO 2.2.4】派对灯
【描述】
在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:
(file lamps.in)
不会有灯会在输入中出现两次。
第一行: N。
第二行: C最后显示的数值。
第三行: 最后亮着的灯,用一个空格分开,以-1为结束。
第四行: 最后关着的灯,用一个空格分开,以-1为结束。
OUTPUT FORMAT:
(file lamps.out)
每一行是所有灯可能的最后状态(没有重复)。每一行有N个字符,第1个字符表示1号灯,最后一个字符表示N号灯。0表示关闭,1表示亮着。这些行必须从小到大排列(看作是二进制数)。
如果没有可能的状态,则输出一行‘IMPOSSIBLE‘。
【分析】
1 #include <cstdlib> 2 #include <iostream> 3 #include <cstring> 4 #include <cmath> 5 #include <cstdio> 6 #include <queue> 7 #include <algorithm> 8 const int Max=(1<<7)+10; 9 using namespace std;10 struct node11 {12 int state;13 int step;//已经走过的步数 14 }sta;15 int Check[10],n,c,ans[Max];16 int vis[(1<<6)+10][10005],ans_point=0;17 inline int MOD(int t) {return (t%6)==0?6:t%6;}//取模运算 18 inline int get(int num,int i) {return (num&(1<<i))==(1<<i);}19 void bfs();20 bool check(int num);21 int main()22 {23 int t,i,j;24 //文件操作25 freopen("lamps.in","r",stdin);26 freopen("lamps.out","w",stdout);27 memset(Check,-1,sizeof(Check));28 29 scanf("%d%d",&n,&c);30 while (scanf("%d",&t) && t!=-1) Check[MOD(t)]=1;//最后亮着的 31 while (scanf("%d",&t) && t!=-1) Check[MOD(t)]=0;//最后黑着的 32 bfs();33 sort(ans,ans+ans_point); 34 if (ans_point==0) printf("IMPOSSIBLE\n");35 for (i=0;i<ans_point;i++)36 {37 for (j=1;j<=n;j++) printf("%d",get(ans[i],MOD(j)-1));38 printf("\n");39 }40 return 0;41 }42 void bfs()43 {44 memset(vis,0,sizeof(vis));45 queue<node>Q;46 sta.state=(1<<6)-1;sta.step=0;47 Q.push(sta);48 while (!Q.empty())49 {50 node u=Q.front();Q.pop();51 if (check(u.state) && u.step==c) {ans[ans_point++]=u.state;continue;}52 node v;v=u;53 v.step=u.step+1;54 //四种操作 55 v.state=v.state^((1<<6)-1);if (vis[v.state][v.step]==0) {vis[v.state][v.step]=1;Q.push(v);}v=u;v.step=u.step+1;56 v.state=v.state^(1)^(1<<2)^(1<<4);if (vis[v.state][v.step]==0) {vis[v.state][v.step]=1;Q.push(v);}v=u;v.step=u.step+1;57 v.state=v.state^(1<<1)^(1<<3)^(1<<5);if (vis[v.state][v.step]==0) {vis[v.state][v.step]=1;Q.push(v);}v=u;v.step=u.step+1;58 v.state=v.state^(1)^(1<<3);if (vis[v.state][v.step]==0) {vis[v.state][v.step]=1;Q.push(v);}v=u;v.step=u.step+1;59 }60 }61 bool check(int num)62 {63 for (int i=0;i<min(n,6);i++) if (Check[i+1]!=get(num,i) && Check[i+1]!=-1) return 0;64 return 1;65 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。