POJ1176 Party Lamps DFS

POJ1176
题目大意
有N个灯，初始状态全开。
有4个处理按钮：
按钮1：所有的灯 更换状态（开-〉关，关-〉开）
按钮2：所有奇数的灯 更换状态（开-〉关，关-〉开）
按钮3：所有偶数的灯 更换状态（开-〉关，关-〉开）
按钮4：所有3K+1(k>=0)的灯 更换状态（开-〉关，关-〉开）
总共可以按动C次

输入
N 灯的数量(10<=N<=100)
C 按按钮的次数(1<=C<=10000)
最终状态位置为开的灯 输入到-1结束
最终状态位置为关的灯 输入到-1结束

输出
字典序输出C次操作后满足条件的序列

Sample Input

10
1
-1
7 -1

Sample Output

0000000000
0101010101
0110110110

强制让自己用dfs做的。。。程序相当很渣
大致思路是 用4个函数作为4个处理
然后dfs 合理就输出
但是WA了！！ 因为没有考虑到答案的重复 或者字典序什么的。。
然后加上了容器set（懒。。。。）和迭代器 感觉内存和时间上会增加
结果TLE了。。。。
然后对C进行优化。。。
开始的时候是C mod 16 没经过大脑，必然超时
改为

if(c>4){
    if(c%2)c=3;
    else c=4;
}

通过了。。。。

不过还有更快更好的方法。。。
灯每6个一组状态循环一次：
所以只需要枚举灯"1,2,3,4,5,6即可"，之后的状态在输出时按要求循环输出。
懒的写，，，，，没救了，，

//32ms
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<iostream>
using namespace std;
int mp[105],on[105],off[105];
int n,c,buff;
set<string> vec;
set<string>::iterator it;
int chk(){
    for(int i=1;i<=n;i++){
        if(on[i]&&mp[i]==0)return 0;
        else if(off[i]&&mp[i]==1)return 0;
    }
    return 1;
}
void mod1(){
    for(int i=1;i<=n;i++)mp[i]=!mp[i];
}
void mod2(){
    for(int i=1;i<=n;i+=2)mp[i]=!mp[i];
}
void mod3(){
    for(int i=2;i<=n;i+=2)mp[i]=!mp[i];
}
void mod4(){
    for(int i=0;(i*3+1)<=n;i++)mp[i*3+1]=!mp[i*3+1];
}

void dfs(int dep){
    if(dep==c){
        if(chk()){
            string s;
            int i;
            //for(int i=1;i<=n;i++)printf("%d",mp[i]);
            //putchar('\n');
            for(s="",i=1; i<=n; i++)
                s+='0'+mp[i];
            vec.insert(s);
        }
        return ;
    }
    mod1();dfs(dep+1); mod1();
    mod2();dfs(dep+1); mod2();
    mod3();dfs(dep+1); mod3();
    mod4();dfs(dep+1); mod4();
    return ;
}

int main(){
    while(scanf("%d%d",&n,&c)!=EOF){
        vec.clear();
        for(int i=1;i<=n;i++)mp[i]=1;
        memset(on,0,sizeof(on));
        memset(off,0,sizeof(off));
        while(scanf("%d",&buff),buff!=-1){
            on[buff]=1;
        }
        while(scanf("%d",&buff),buff!=-1){
            off[buff]=1;
        }
        //c%=16;
        if(c>4){
            if(c%2)c=3;
            else c=4;
        }
        dfs(0);
        for(it=vec.begin();it!=vec.end();it++){
            cout<<*it<<endl;
        }
    }
    return 0;
}