首页 > 代码库 > 【USACO 2.2】Party Lamps

【USACO 2.2】Party Lamps

2024-08-17 02:12:02   218人阅读

四种开关，n盏灯，1：改变所有灯状态，2：改变奇数灯状态，3：改变偶数灯状态，4：改变3k+1灯状态

给你按开关的总次数c和部分灯限制条件（开或关），一开始都是开着的。（$c \leq 10000,n \leq 100$）

我直接考虑每个开关按了奇数次或偶数次，因为顺序和总次数不影响结果，重要的是每种开关按的次数是奇数还是偶数次。

题解里有个flip[i]= (1<<6-1)&0x55 和与上0xAA，分别代表2、3开关，因为0x55就是01010101，0xAA就是10101010，每次异或上相应的flip[i]，就是开关的操作。

/*LANG:C++TASK:lamps*/#include<cstdio>#include<algorithm>#include<string>#define N 105using namespace std;int n,c,a,cnt;bool on[N],off[N],sta[N];string ans[10];bool ck(int id,int a,int b,int c,int d){    bool ans=1;    if(a&1)ans=!ans;    if(id%2){        if(b&1)ans=!ans;    }else if(c&1)ans=!ans;    if(id%3==1&&d&1)ans=!ans;    return ans;}bool get(){    bool fd=0;    for(int i=0;i<=1;i++)        for(int j=0;j<=1;j++)            for(int k=0;k<=1;k++)                for(int l=0;l<=1;l++)                    if(i^j^k^l^c==0&&i+j+k+l<=c){                    //奇数次的开关为奇数个，则总次数为奇数，因此异或起来为0                    //总次数不能超过c                   // printf("%d %d %d %d\n",i,j,k,l);                    bool ok=1;                    for(int la=1;la<=n;la++)                        if(ck(la,i,j,k,l)){                            if(off[la]){                                ok=0;break;                            }                            sta[la]=1;                        }else {                            if(on[la]){                                ok=0;break;                            }                            sta[la]=0;                        }                    if(ok){                        for(int i=0;i<n;i++)                            ans[cnt]+=sta[i+1]+‘0‘;                        ans[cnt++]+=‘\0‘;                        fd=1;                    }                }    return fd;}int main(){    freopen("lamps.in","r",stdin);    freopen("lamps.out","w",stdout);    scanf("%d%d",&n,&c);    while(scanf("%d",&a),a!=-1)        on[a]=1;    while(scanf("%d",&a),a!=-1)        off[a]=1;    if(get()){        sort(ans,ans+cnt);        for(int i=0;i<cnt;i++)            printf("%s\n",ans[i].c_str());    }else puts("IMPOSSIBLE");    return 0;}

　　

【USACO 2.2】Party Lamps


联系
我们