USACO 2.2.4 派对灯 Party Lamps

题解

这题还是比较有意思的，难在理解题意。
naive的遍历所有情况 O(4^N) 是绝对不行滴。
仔细想想，按一个按键 偶数次等于不按，按奇数次相当于按一次。所以某按钮按几次可以统统转化为按了0或1次。
再想想，按的次序有没有影响。答案是没有，模拟一下可知。
那么其实，所谓的 4^N 种 变化其实 就只有 0000～1111 这 16种而已。那么我们把这16种情况全部求出再作比较即可。
最后稍微注意一下 C即按次数与变化数的关系即可。

ps: 这道题最后输出结果还要排序，有点麻烦。。。

Code

// 省略头文件
using namespace std;
int n,m,c;
bool fin[2][101];// 检验条件
int chose[5];// 16种变化记录
int pres[101]; // 亮灯情况记录
int cot[17][101]; // 用于排序
typedef struct{int i;int num;
}P;
P hod[17]; // 用于排序。。 因为二维数组不好排void cal(){ // 根据变化 计算亮灯情况for(int i=1;i<=n;i++) // 初始化pres[i]=1;if( chose[1] ){for(int i=1;i<=n;i++)pres[i]=1-pres[i];}if( chose[2] ){for(int i=1;i<=n;i+=2)pres[i]=1-pres[i];}if( chose[3] ){for(int i=2;i<=n;i+=2)pres[i]=1-pres[i];}if( chose[4] ){for(int i=1,k=0;i<=n;i=3*k+1){pres[i]=1-pres[i];k++;}}}bool match(){// 判断该情况是否可行bool a,b,d;a=b=true;for(int i=1;i<=n;i++){ // 结果匹配if( fin[0][i] == true) // ona = a && (pres[i] == 1);if( fin[1][i] == true) // offb = b &&(pres[i] == 0);}// 按次数 可行性检查int sum=0;for(int i=1;i<=4;i++)sum+=chose[i];// sum 为最少按次数if( sum > c) d= false;else{if( sum%2 == c%2) d = true; // 奇偶else d = false;}return a&&b&&d ;
}void dfs(int t){ // 递归 创造所有16种情况if(t==5){cal();if(match()){for(int i=1;i<=n;i++) cot[m][i]= pres[i];m++;}return;}for(int i=1;i>=0;i--){chose[t] = i;dfs(t+1);}
}bool cmp(P a,P b){return a.numint main(void){freopen("lamps.out","w",stdout);freopen("lamps.in","r",stdin);int num;m = 0;cin>>n>>c;while(cin>>num){if(num==-1) break;fin[0][num] = true;}   while(cin>>num){if(num==-1) break;fin[1][num] = true;}   dfs(1);// 不优雅的排序int k;for(int i=0;i0;k = 1;for(int j=6;j>-1;j--){ // 比大小num+= k*cot[i][j];k*=2;}hod[i].num = num;//cout<}sort(hod,hod+m,cmp);for(int i=0;ifor(int j=1;j<=n;j++)cout<< cot[ hod[i].i][j];cout<if(m==0) cout<<"IMPOSSIBLE\n";return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！