Home > Old Blog Posts > USACO 2.2.4 Party Lamps

USACO 2.2.4 Party Lamps


注意到每个按钮按2次等同于没有按。所以实际情况只有8种。另外灯的状态有大量的重复,实际上只要考虑前6个灯就足够了(我当时咋就没想到)。

代码:

/*
ID: dementr1
PROG: lamps
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“lamps.in”);
ofstream fout(“lamps.out”);
int sum,con,coff,checkon[100]={},checkoff[100]={},A[10000][100]={},counter=0;
int cmp(int a[], int b[])
{
int i;
for(i=0;i<sum;i++)
{
if(a[i]<b[i]) return -1;
if(a[i]>b[i]) return 1;
}
return 0;
}
void swap(int *a, int *b)
{
int x=*a;
*a=*b;
*b=x;
}
int partition(int A[][100],int left, int right)
{
int i=(left+right)/2,j,k;
for(k=0;k<sum;k++) swap(&A[i][k],&A[right][k]);
i=left-1;
for(j=left;j<right;j++)
if(cmp(A[j],A[right])==-1)
{
i++;
for(k=0;k<sum;k++) swap(&A[i][k],&A[j][k]);
}
i++;
for(k=0;k<sum;k++) swap(&A[i][k],&A[right][k]);
return i;
}
void quicksort(int A[][100], int left, int right)
{
int i;
if(left<right)
{
i=partition(A,left,right);
quicksort(A,left,i-1);
quicksort(A,i+1,right);
}
}
void change(int *a)
{
if(*a==0) *a=1;
else *a=0;
}
bool check(int a[])
{
int i;
for(i=0;i<con;i++) if(a[checkon[i]-1]!=1) return false;
for(i=0;i<coff;i++) if(a[checkoff[i]-1]!=0) return false;
return true;
}
void dfs(int deep, int light[],int n)
{
int i;
if(deep==n)
{
int a[100];
for(i=0;i<sum;i++) a[i]=1;
for(i=0;i<deep;i++)
switch(light[i])
{
case 1:
for(i=0;i<sum;i++) change(&a[i]);
break;
case 2:
for(i=0;i<sum;i+=2) change(&a[i]);
break;
case 3:
for(i=1;i<sum;i+=2) change(&a[i]);
break;
case 4:
for(i=0;i<sum;i+=3) change(&a[i]);
break;
}
if(check(a))
{
for(i=0;i<sum;i++) A[counter][i]=a[i];
counter++;
}
}
else
for(i=1;i<=4;i++)
{
light[deep]=i;
dfs(deep+1,light,n);
}
}
int main()
{
int n_tmp,i,j,a1,a2,a3,a4;
fin>>sum;
fin>>n_tmp;
while(1)
{
fin>>i;
if(i==-1) break;
checkon[con++]=i;
}
while(1)
{
fin>>i;
if(i==-1) break;
checkoff[coff++]=i;
}
int light[100]={};
if(n_tmp<8)
dfs(0,light,n_tmp);
else
for(a1=0;a1<=1;a1++)
for(a2=0;a2<=1;a2++)
for(a3=0;a3<=1;a3++)
for(a4=0;a4<=1;a4++)
{
int a[100];
for(i=0;i<sum;i++) a[i]=1;
if(a1==0)    for(i=0;i<sum;i++) change(&a[i]);
if(a2==0)    for(i=0;i<sum;i+=2) change(&a[i]);
if(a3==0)    for(i=1;i<sum;i+=2) change(&a[i]);
if(a4==0)    for(i=0;i<sum;i+=3) change(&a[i]);
if(check(a))
{
for(i=0;i<sum;i++) A[counter][i]=a[i];
counter++;
}
}
quicksort(A,0,counter-1);
if(counter==0) fout<<“IMPOSSIBLE”<<endl;
else
{
for(i=0;i<sum;i++) fout<<A[0][i];
fout<<endl;
for(i=1;i<counter;i++)
if(cmp(A[i],A[i-1])!=0)
{
for(j=0;j<sum;j++) fout<<A[i][j];
fout<<endl;
}
}
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: