http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2328
题目大意:(如题)
输入输出:(如题)
解题思路:
1.因为每个按钮按2次和没按效果是一样的。所以每个按钮或者按或者不按,一共有2^4=16中状态。
2.然后因为这个电灯系统有个性质,每6个一循环,所以把这4个按钮的16种状态对应的前6个灯的状态枚举出来。然后分析,发现一下规律:
-按1和按2相当于按3;
-按2和按3相当于按1;
-按1和按3相当于按2;
-按1按2和按3相当于不按;
-相差3的倍数也可以相互转换;
消重之后得到8种按法:不按,按1,按2,按3,按4,按1按4,按2按4,按3按4。
相对应的最少按的次数为:0,1,1,1,1,2,2,2。
3.参照了NOCOW-USACO上的一个比较邪恶的方法-常量表法,把前6个灯的状态保存在light数组里面,然后用一个minnum数组存储相应状态的按的次数。如下:

int light[9][7]={
	0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,//按1
	0,0,0,1,1,1,0,//按1按4
	0,0,1,0,1,0,1,//按3
	0,0,1,1,0,1,1,//按1按4
	0,1,0,0,1,0,0,//按4
	0,1,0,1,0,1,0,//按2
	0,1,1,0,0,0,1,//按2按4
	0,1,1,1,1,1,1,//不按
};//常量表

int minnum[9]={0,1,2,1,1,2,1,2,0};//对应常量表8个状态最少摁的次数

4.然后就可以开始写代码了,嘿嘿
核心代码;

flag1=false;
	for(i=1;i<9;i++)
	{
		flag2=true;
        for(j=1;j<=n;j++)
        {
			if(dat[j]==-1)//如果没有确定是亮或灭
				continue;
			tmp=j%6;//六位循环
			if(tmp==0)//如果是6的倍数
				tmp=6;
			if(dat[j]!=light[i][tmp])//有个灯不同说明不是这个状态,结束判断
			{
				flag2=false;
				break;
			}
        }
        if(flag2==true&&c>=minnum[i])
		{
			flag1=true;//有一个满足条件就标记
			for(j=1;j<=n;j++)
			{
				tmp=j%6;
				if(tmp==0)
					tmp=6;
				cout<<light[i][tmp];
			}
			cout<<endl;
		}
	}
	if(flag1==false)
		cout<<"IMPOSSIBLE"<<endl;

发表评论

电子邮件地址不会被公开。

Post Navigation