『算法-ACM 竞赛-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;
    }