usaco_lamps.cpp

usaco自己做的1到5章的代码

/*
ID: wangyuc2
PROG: lamps
LANG: C++
*/ 
#include <fstream>
#include <iostream>
#include <memory>
#include <algorithm>
using namespace std;

ifstream fin("lamps.in");
ofstream fout("lamps.out");

int a[1001];
int b[1001];
int d[16][1001];
bool l[5];
int n,c,p=0,way=0;

void turn(int k)
{
    int i,q;
    bool flag;
    if(k>4)  
    {
		flag=true;
        for(i=1;i<=n;i++) 
			if(a[i]>-1 && a[i]!=b[i]) {flag=false;break;}
       
		if(flag)

		{
		} 
		if(flag && (c%2)!=(p%2) || c<p) flag=false;
        if(flag) {
			      for(i=1;i<=n;i++) d[way][i]=b[i]; i=1; q=64; 
                  while(i<=n && i<=6)
                  {
                      d[way][0]+=q*d[way][i];
                      q/=2;
                      i++;
                  }
                  way++;
                  }
    }
	else{
    switch(k){
               case 1:
                    for(i=1;i<=n;i++)  if(b[i]) b[i]-=1;
                                       else b[i]+=1;
                    l[k]=true;
					break;
               case 2:
                    for(i=1;i<=n;i+=2) if(b[i]) b[i]-=1;
                                       else b[i]+=1;

					l[k]=true;
                    break;
               case 3:
                    for(i=2;i<=n;i+=2) if(b[i]) b[i]-=1;
                                       else b[i]+=1;
									   l[k]=true;
                    break;
               case 4:
                    for(i=1;i<=n;i+=3) if(b[i]) b[i]-=1;
                                       else b[i]+=1;
									   l[k]=true;
                    break;
                    }
    p++;
    
    turn(k+1);
    switch(k){
               case 1:
                    for(i=1;i<=n;i++)  if(b[i]) b[i]-=1;
                                       else b[i]+=1;
									   l[k]=false;
                    break;
               case 2:
                    for(i=1;i<=n;i+=2) if(b[i]) b[i]-=1;
                                       else b[i]+=1;
									    l[k]=false;
                    break;
               case 3:
                    for(i=2;i<=n;i+=2) if(b[i]) b[i]-=1;
                                       else b[i]+=1;
									    l[k]=false;
                    break;
               case 4:
                    for(i=1;i<=n;i+=3) if(b[i]) b[i]-=1;
                                       else b[i]+=1;
									    l[k]=false;
                    break;
                    }
    p--;
       
    turn(k+1);  
    }
}

int main()
{
   
   int i,j,min,k;
   memset(a,-1,sizeof(a));
   memset(l,false,sizeof(l));
   for(i=0;i<16;i++) d[i][0]=0;
   fin>>n;
   fin>>c;
   for(i=1;i<=n;i++) b[i]=1;
   while(1)
   {
       fin>>j;
       if(j==-1) break;
       a[j]=1;
   }
   while(1)
   {
       fin>>j;
       if(j==-1) break;
       a[j]=0;
   }
   k=1;
   way=0;
   turn(k);
   
	   if(way==0) fout<<"IMPOSSIBLE"<<endl;
	   else{
   j=0;
   while(j<way){
	   min=0;
      for(i=0;i<way;i++)
      {
          if(d[i][0]<d[min][0]) min=i;
      }
      for(i=1;i<=n;i++) fout<<d[min][i];
      fout<<endl;
      j++;
      d[min][0]=100000;}
   }
   //system("PAUSE");
   return 0;
}