首页 > 代码库 > USACO 2.2 Party Lamps 【高能等效+规律枚举】
USACO 2.2 Party Lamps 【高能等效+规律枚举】
题在这:https://www.luogu.org/problem/show?pid=1468#sub
按钮1:当按下此按钮,将改变所有的灯:本来亮着的灯就熄灭,本来是关着的灯被点亮。
按钮2:当按下此按钮,将改变所有奇数号的灯。
按钮3:当按下此按钮,将改变所有偶数号的灯。
按钮4:当按下此按钮,将改变所有序号是3*K+1(K>=0)的灯。例如:1,4,7...
此题关键:找到4个按钮之间的关系,可发现最终状态只有少数(可枚举的)几种,又:四个操作的影响周期取最小公倍数后,发现 6个灯为一个变化周期,不管如何按按钮,最终N个灯的状态均是以6个灯为基本单位,N/6为循环次数的循环序列
一、首先,从基本操作入手,随意搭配四个按钮,且每种按钮只能使用一次,可发现:(只考虑6个灯,0表示灯灭,1表示灯亮)
1 2 3 4
按1 ====》0 0 0 0 0 0
按2 ====》0 1 0 1 0 1
按3 ====》1 0 1 0 1 0
按4 ====》0 1 1 0 1 1
按1和2====》1 0 1 0 1 0 ====》相当于按3
按1和3 ====》0 1 0 1 0 1 ====》相当于按2
按1和4 ====》1 0 0 1 0 0
按2和3 ====》0 0 0 0 0 0 ====》相当于按1
按2和4 ====》1 1 0 0 0 1
按3和4 ====》0 0 1 1 1 0
按1、2、3====》相当于按2遍三 ====》不变
按1、2、4====》相当于按3和4
按1、3、4====》相当于按2和4
再加上不按 ====》1 1 1 1 1 1
共计8种最终状态(红色),故以后所有的状态都是由这8个中的一个为基本循环得到的
完成它们的最少操作次数分别为:1,1,1,3,2,2,2,
就是按4这种情况,按4 可以一步,也可以三步或者三步以上(224)但是就是不能两步达到,故设为3,把按一次的情况特判
二、又由:
按1和按2相当于按3;
按2和按3相当于按1;
按1和按3相当于按2;
按1按2和按3相当于不按;
由(一)和(二)得,c 等于任意操作次数时,我们均可以用(一)搭出规律骨架,用(二)扩充(一)中的操作使凑齐c个操作,以这8个结果为基础,构造答案(只是为了证明正确性,不必输出),最后,只输出最终状态,完毕。
下面为参考代码(借鉴了“ly59782的博客”中的代码):
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int state[9][7]={ {0,0,0,0,0,0,0}, {0,0,0,0,0,0,0},//press 1 {0,0,0,1,1,1,0},//press 3 & 4 {0,0,1,0,1,0,1},//press 2 {0,0,1,1,0,1,1},//press 4 {0,1,0,0,1,0,0},//press 1 & 4 {0,1,0,1,0,1,0},//press 3 {0,1,1,0,0,0,1},//press 2 & 4 {0,1,1,1,1,1,1} //not pressing }; int c,n,x,a[8]; int minn[9]={0,1,2,1,3,2,1,2}; bool flag=0; int main() { freopen("lamps.in","r",stdin); freopen("lamps.out","w",stdout); for(int i=1;i<=6;i++) a[i]=-1; cin>>n>>c; while(cin>>x,x!=-1) { int v=x%6; if(v==0) v=6; a[v]=1; } while(cin>>x,x!=-1) { int v=x%6; if(v==0) v=6; a[v]=0; } for(int i=1;i<=8;i++) { int f=1; for(int j=1;j<=6;j++) { if(a[j]==-1) continue; if(a[j]!=state[i][j]) { f=0; break; } } if(f==1&&(c>=minn[i]||(c==1&&i==4))) { for(int p=1;p<=n;p++) { int v=p%6; if(v==0) v=6; cout<<state[i][v]; flag=1; } cout<<endl; } } if(!flag) cout<<"IMPOSSIBLE"<<endl; return 0; }
USACO 2.2 Party Lamps 【高能等效+规律枚举】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。