[usaco][舞会灯] party lamps

这是我做过的题目中用时间最长的一个
题目原文：
--------------------------------------------
Party Lamps
IOI 98
To brighten up the gala dinner of the IOI'98 we have a set of N (10 <= N <= 100) colored lamps numbered from 1 to N.

The lamps are connected to four buttons:

Button 1: When this button is pressed, all the lamps change their state: those that are ON are turned OFF and those that are OFF are turned ON.
Button 2: Changes the state of all the odd numbered lamps.
Button 3: Changes the state of all the even numbered lamps.
Button 4: Changes the state of the lamps whose number is of the form 3xK+1 (with K>=0), i.e., 1,4,7,...
A counter C records the total number of button presses.

When the party starts, all the lamps are ON and the counter C is set to zero.

You are given the value of counter C (0 <= C <= 10000) and the final state of some of the lamps after some operations have been executed. Write a program to determine all the possible final configurations of the N lamps that are consistent with the given information, without repetitions.

PROGRAM NAME: lamps
INPUT FORMAT
Line 1:  N 
Line 2:  Final value of C 
Line 3:  Some lamp numbers ON in the final configuration, separated by one space and terminated by the integer -1. 
Line 4:  Some lamp numbers OFF in the final configuration, separated by one space and terminated by the integer -1. 
No lamp will be listed twice in the input. 

SAMPLE INPUT (file lamps.in)
10
1
-1
7 -1

In this case, there are 10 lamps and only one button has been pressed. Lamp 7 is OFF in the final configuration.

OUTPUT FORMAT
Lines with all the possible final configurations (without repetitions) of all the lamps. Each line has N characters, where the first character represents the state of lamp 1 and the last character represents the state of lamp N. A 0 (zero) stands for a lamp that is OFF, and a 1 (one) stands for a lamp that is ON. The lines must be ordered from least to largest (as binary numbers).

If there are no possible configurations, output a single line with the single word `IMPOSSIBLE'

SAMPLE OUTPUT (file lamps.out)
0000000000
0101010101
0110110110

In this case, there are three possible final configurations:
All lamps are OFF
Lamps 1, 4, 7, 10 are OFF and lamps 2, 3, 5, 6, 8, 9 are ON.
Lamps 1, 3, 5, 7, 9 are OFF and lamps 2, 4, 6, 8, 10 are ON.
---------------------------------------------------------------------------
刚开始我真的用了bfs，因为没有发现规律。
深探C步，当C比较小的时候还可以忍受，但C大了的时候，就会出现stack overflow，即使不出现这个，还有时间的问题。
要遍历4^N，指数级的。

后来发现了规律：
1：对于每一个button，如果按下两次，就相当于什么也没发生。
2：对于所有的等，相当于6盏灯。

利用第一个条件，递归的深度最多只需要4；大大的节省了空间和时间
利用第二个条件，储存时节省了空间
我的解法：
-----------------------------------------------------------------------------

/*
ID:yunleis2
PROG:lamps
LANG:C++
*/
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int N;
int C;
int *final_on;
int *final_off;
void search(int depth,bool * state0);
vector<bool *> result;
void quicksort(bool ** a,int p,int r);
int compare(bool * b1,bool *b2);
void button1(int num,bool *state0);
void button2(int num,bool *state0);
void button3(int num,bool *state0);
void button4(int num,bool *state0);
void check(int num,bool *state0);
int main()
{
	fstream fin("lamps.in",ios::in);
	fin>>N;
	int old_n=N;
	N--;
	N=N%6+6;
	N++;
	fin>>C;
	int t;
	final_on=new int[N+1];
	final_off=new int[N+1];
	bool * init_s=new bool[N];
	for(int i=0;i<N;i++)
		init_s[i]=true;
	int ptr=0;
	do{
		fin>>t;
		final_on[ptr++]=t-1;
	}while(t!=-1);
	ptr=0;
	do{
		fin>>t;
		final_off[ptr++]=t-1;
	}while(t!=-1);
	//search(C,init_s);
	button1(0,init_s);

	bool **result1 =new bool*[result.size()];
	int size=result.size();
	for(int i=0;i<result.size();i++)
	{
		result1[i]=result.at(i);
	}
	for(int i=0;i<size;i++)
	{
		for(int j=0;j<N;j++)
			cout<<result[i][j];
		cout<<endl;
	
	}
	quicksort(result1,0,result.size()-1);
	fstream fout("lamps.out",ios::out);
	if(size==0)
		fout<<"IMPOSSIBLE"<<endl;
	cout<<endl;
	for(int i=0;i<size;i++)
	{
		if(i!=0&&compare(result1[i],result1[i-1])==0)
		{ 
			continue;
		}
		for(int j=0;j<old_n;j++)
			fout<<result1[i][j%6];
		fout<<endl;
		 
	}
	for(int i=0;i<size;i++)
		delete [] result1[i];
	
	 
 
} 
int compare(bool * b1,bool *b2)
{
 #if 0

 	cout<<"compare"<<endl;
 	for(int j=0;j<N;j++)
 		cout<<b1[j];
 	cout<<endl;
 	for(int j=0;j<N;j++)
 		cout<<b2[j];
 	cout<<endl; 
#endif
 
	for(int i=0;i<N;i++)
	{
		int a=b1[i];
		int b=b2[i];
		if(a<b)
			return -1;
		if(a>b)
			return 1;
	}
	return 0;
}
int partition(bool ** a,int p,int r)
{
	bool * x=a[r];
	int i=p-1;
	for(int j=p;j<r;j++)
	{
		if(compare(a[j],x)<=0)
		{
			i++;
			bool * temp=a[i];
			a[i]=a[j];
			a[j]=temp;
		}
	}
	bool * temp=a[i+1];
	a[i+1]=a[r];
	a[r]=temp;
	return i+1;
}
void quicksort(bool ** a,int p,int r)
{
	if(p<r)
	{
		int i=partition(a,p,r);
		quicksort(a,p,i-1);
		quicksort(a,i+1,r);
	}
}

void button1(int num,bool *state0)
{
	if(num>C)
		return;
	bool * state1;
	state1=new bool[N];
	for(int i=0;i<N;i++)
	{
		state1[i]=state0[i];
	}
	//no change
	button2(num,state1);
	for(int i=0;i<N;i++)
		state1[i]=!state1[i];
	button2(num+1,state1);
	delete []state1;
}
void button2(int num,bool *state0)
{
	if(num>C)
		return;
	bool * state1;
	state1=new bool[N];
	for(int i=0;i<N;i++)
	{
		state1[i]=state0[i];
	}
	//no change
	button3(num,state1);
	for(int i=0;i<N;i+=2)
		state1[i]=!state1[i];
	button3(num+1,state1);
	delete [] state1;
}

void button3(int num,bool *state0)
{
	if(num>C)
		return;
	bool * state1;
	state1=new bool[N];
	for(int i=0;i<N;i++)
	{
		state1[i]=state0[i];
	}
	//no change
	button4(num,state1);
	for(int i=1;i<N;i+=2)
		state1[i]=!state1[i];
	button4(num+1,state1);
	delete [] state1;
}
void button4(int num,bool *state0)
{
	if(num>C)
		return;
	bool * state1;
	state1=new bool[N];
	for(int i=0;i<N;i++)
	{
		state1[i]=state0[i];
	}
	//no change
	check(num,state1);
	for(int i=0;i<N;i+=3)
		state1[i]=!state1[i];
	check(num+1,state1);
	 delete [] state1;
}
void check(int num ,bool *state0)
{
	if(num>C)
		return;
	if((num%2)!=C%2)
		return;
	for(int i=0;i<N&&final_on[i]!=-2;i++)
	{
		if(!state0[final_on[i]%6])
		{ 
			 
			return ;
		}
	}
	for(int i=0;i<N&&final_off[i]!=-2;i++)
	{
		if(state0[final_off[i]%6])
		{ 
			
			return ;
		}
	}
	bool *res=new bool[N];
	for(int i=0;i<N;i++)
		res[i]=state0[i];
	result.push_back(res);
 
}