518
[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);
}
最後更新：2017-04-02 06:51:48