POJ 1176 Party Lamps&& USACO 2.2 派对灯（搜索）
POJ 1176 Party Lamps&& USACO 2.2 派对灯（搜索）
题目地址 http://poj.org/problem?id=1176 题目描述 在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’。
输入输出样例 输入样例#1： 10 1 -1 7 -1 输出样例#1： 0000000000 0101010101 0110110110 说明 在这个样例中，有三种可能的状态：
所有灯都关着
1,4,7,10号灯关着，2,3,5,6,8,9亮着。
1,3,5,7,9号灯关着，2, 4, 6, 8, 10亮着。
翻译来自NOCOW
USACO 2.2 讲真的这个翻译真不咋地，之前用过别的方法做过这个题目，咱们现放开超时，优化策略，先分析这个题目，题目是给了这四种操作，让你找到这四种操作能够达成符合条件的类型是哪几种，明显搜索题，但是这里有两个思想一定要明白，也是这道题的关键所在： 1.搜索上限，当搜索次数达到一定数量之后，已经搜索出所有结果，没必要在继续进行搜索，这个思想不仅是搜索，有时候二分也会用到这个思想。 2.重复性，结果具有规律，通过这个规律可以对某简单结果进行扩展的到正确答案。 比如在这个题目中其实四位数足以表示所有情况，但是我为了保险还使用了6位，但是这并没有太大的区别，考虑四位数，当对四位数变换超过6次时必然出现重复结果，虽然不知道最少变换几次，但是6次已经够少了。 虽然代码写的比较丑，比较长，但是思路明确纯搜索写法。
#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<cstring>
using namespace std;
set<int> kai;
set<int> guan;
char flag[7];
set<string> ob;
int n=6,q,cc=-1,yy;
int op1(char *a,char* b);
int op2(char *a,char* b);
int op3(char *a,char* b);
int op4(char *a,char* b);
void dfs(char *a,int w)
{
if(w==q){
// cout<<a<<endl;
for(auto i=kai.begin();i!=kai.end();i++)
{
if(a[*i]!='1') return ;
}
for(auto i=guan.begin();i!=guan.end();i++)
{
if(a[*i]!='0') return ;
}
string temp;
temp.clear();
int t=0;
for(int i=0;i<yy;i++)
{
temp.push_back(a[t]);
t++;
if(t==6) t=0;
}
ob.insert(temp);
return;
}
char tem[7];
op1(a,tem);
dfs(tem,w+1);
op2(a,tem);
dfs(tem,w+1);
op3(a,tem);
dfs(tem,w+1);
op4(a,tem);
dfs(tem,w+1);
}
int main()
{
fill(flag,flag+7,'1');
int m=1,x=1,cc=-1;
cin>>yy>>q;
if(q>6) q=6;
kai.clear();guan.clear();
while(m!=-1)
{
cin>>m;
if(m==-1) break;
m=(m-1)%6;
kai.insert(m);
}
while(x!=-1)
{
cin>>x;
if(x==-1) break;
x=(x-1)%6;
guan.insert(x);
}
dfs(flag,0);
if(ob.size()==0)
{
cout<<"IMPOSSIBLE"<<endl;
return 0;
}
for(set<string> ::iterator po=ob.begin();po!=ob.end();po++)
cout<<*po<<endl;
}
int op1(char *a,char* b)
{
for(int i=0;i<=n;i++)
{
if(a[i]=='0') b[i]='1';
else b[i]='0';
}
return 0;
}
int op2(char *a,char* b)
{
for(int i=0;i<=n;i++)
{
if(i%2==1){
if(a[i]=='0') b[i]='1';
else b[i]='0';
}
else b[i]=a[i];
}
return 0;
}
int op3(char *a,char* b)
{
for(int i=0;i<=n;i++)
{
if(i%2==0){
if(a[i]=='0') b[i]='1';
else b[i]='0';
}
else b[i]=a[i];
}
return 0;
}
int op4(char *a,char* b)
{
for(int i=0;i<=n;i++)
{
if(i%3==0){
if(a[i]=='0') b[i]='1';
else b[i]='0';
}
else b[i]=a[i];
}
return 0;
}腾讯云开发者
