USACO 2.2Party Lamps

meaning:是给4个开关,第一个开关控制所有灯,也就是本来开的变关,本来关的变开,第二个开关控制单数灯,第三个开关控制双数灯,第4个开关控制n%3==1的灯。

给一个n,c,分别表示灯的数量和按下开关的数量,然后再给按c次开关后有哪几个灯是亮的,哪几个灯是不亮的。如果存在满足的可能则输出所有可能,按照0在前面的输出顺序,也就是数组大小的输出顺序,如果不可能则输出IMPOSSIBLE.

the reason of failure:1、范围特例,特殊没考虑按开关为0的可能。

2、题意理解,没注意输出的顺序是要按数组大小而不是按照0的个数从小到大。

3、数据是水过的~

thinking:因为c在16次后的按下和之前是重复的那么大于16的可以%16。然后可以把灯分为4类,因为这4类的灯都是同亮同按的,然后dfs,把所有满足条件放入一个数组,然后O(n^2)的方法比较,找出最大的标记后输出。

/*
ID: me
PROG: lamps
LANG: C++
*/
#includeiostream
#include string.h
#include stdio.h
#include map
#include algorithm
using namespace std;
int q1[5];
int qq[105];
int q2[5],n;
int q3[5];
struct ttt{
int z,a[100];
};
int q5[50][150];
ttt q6[105];
int gg1;
int t1;
bool walked[500];
maplong long,intccc;
int fun(){
    int i,j,k;
    for(i=1;i=4;i++){
           // cout  q3[i]  " "  q1[i] endl;
        if(q3[i]==q1[i]||(q3[i]==-1q1[i]==0)||q1[i]==-1){
            continue;
        }else{
            //cout i  endl;
            return 0;
        }
    }
    int c5=0;
    for(i=1;i=4;i++){
        if(q3[i]==-1)c5=c5*10+0;
        else c5=c5*10+q3[i];
    }
    if(ccc[c5]!=0){
        return 0;
    }else{
        ccc[c5]=1;
    }
    gg1++;
    q6[gg1].z=gg1;
    for(i=1;i=n;i++){
        if(i%2==0){
            if(i%3==1){
                if(q3[2]==-1)
                    //cout  0;
                    q5[gg1][i]=0;     //-1是指没开灯也就是0
                else{
                    q6[gg1].a[i]++;
                    //cout  1;
                    q5[gg1][i]=1;
                }
                }else{
                if(q3[4]==-1)
                    //cout  0;
                    q5[gg1][i]=0;     //-1是指没开灯也就是0
                else{
                        q6[gg1].a[i]++;
                //cout  1;
                    q5[gg1][i]=1;
                }

                }
        }else{
        if(i%3==1){
                if(q3[1]==-1)
                    //cout  0;
                    q5[gg1][i]=0;     //-1是指没开灯也就是0
                else{
                //cout  1;
                    q5[gg1][i]=1;
                q6[gg1].a[i]++;}
                }else{
                if(q3[3]==-1)
                    //cout  0;
                    q5[gg1][i]=0;   //-1是指没开灯也就是0
                else{
                        q6[gg1].a[i]++;
                    //cout  1;
                    q5[gg1][i]=1;}

                }
        }
    }
    //cout endl;
}
int dfs(int x){
    if(xt1)fun();
    else{
        for(int i=1;i=4;i++){
            if(i==1){
                q3[2]=-q3[2];
                q3[3]=-q3[3];
                q3[4]=-q3[4];
                q3[1]=-q3[1];
                dfs(x+1);
                q3[2]=-q3[2];
                q3[3]=-q3[3];
                q3[4]=-q3[4];
                q3[1]=-q3[1];
            }else if(i==2){
                q3[4]=-q3[4];
                q3[2]=-q3[2];
                dfs(x+1);
                q3[4]=-q3[4];
                q3[2]=-q3[2];
            }else if(i==3){
                q3[1]=-q3[1];
                q3[3]=-q3[3];
                dfs(x+1);
                q3[3]=-q3[3];
                q3[1]=-q3[1];
            }else if(i==4){
                q3[2]=-q3[2];
                q3[1]=-q3[1];
                dfs(x+1);
                q3[2]=-q3[2];
                q3[1]=-q3[1];
        }
        }
    }
}
int sort1(const ttt *x,const ttt  *y){
    int i;
    int t1,t2;
    for(i=1;i=n;i++){
            t1=(*(ttt*)x).a[i];
           t2=(*(ttt*)y).a[i];
        if(t1!=t2){
            return t1t2;
        return 1;
        }
    }
}

int main(){
    freopen("in.txt","r",stdin);
   // freopen("lamps.in","r",stdin);
    //freopen("lamps.out","w",stdout);
    int i,j,k,l,f1,f2,f3,t2,t3;
    int m;
    gg1=0;
    memset(qq,-1,sizeof(qq));
    memset(q1,-1,sizeof(q1));
    memset(q5,0,sizeof(q5));
    memset(q6,0,sizeof(q6));
    memset(walked,0,sizeof(walked));
    for(i=1;i=4;i++)
        q3[i]=1;
    scanf("%d",n);
    //ccc.clear;
    cin  t1; //刚开始,全部都是on
    t1=t1%16;
    while(scanf("%d",t2)==1t2!=-1){
        qq[t2]=0;
    if(t2%2==0){
        if(t2%3==1){
            q1[2]=1;
        }else{
            q1[4]=1;
        }
    }else{
        if(t2%3==1){
            q1[1]=1;
        }else{
            q1[3]=1;
        }
    }
    }
    while(scanf("%d",t3)==1t3!=-1){
        qq[t3]=1;
    if(t3%2==0){
        if(t3%3==1){
            q1[2]=0;
        }else{
            q1[4]=0;
        }
    }else{
        if(t3%3==1){
            q1[1]=0;
        }else{
            q1[3]=0;
        }
    }
    }
    for(i=1;i=4;i++)
        q2[i]=1;
    dfs(1);
    t3=1;
    if(t1!=0)
    for(i=1;i=gg1;i++){
            t3=1;
            while(walked[t3]==1){
                t3++;
            }
        for(j=1;j=gg1;j++){
            if(memcmp(q5[j],q5[t3],sizeof(q5[0]))0walked[j]==0){ //j小于t3
                t3=j;
            }
        }
        walked[t3]=1;
        for(k=1;k=n;k++)
            cout  q5[t3][k];
        cout  endl;
    }
    if(gg1==1t1==0){
        for(i=1;i=n;i++)
            cout  1;
        cout  endl;
    }
    if(gg11)
        cout  "IMPOSSIBLE" endl;
    return 0;
}


最新回复(0)
/jishuJ_2BmkwUaq3SN2BUt6ih9D1BRlscMdx2hIguB2XA_3D_3D4858396
8 简首页