[USACO2.2] 派对灯 Party Lamps
题目描述
我们有 盏彩色灯,他们分别从 被标上号码。这些灯都连接到四个按钮:
按钮 :当按下此按钮,将改变所有的灯:本来亮着的灯就熄灭,本来是关着的灯被点亮。
按钮 :当按下此按钮,将改变所有奇数号的灯。
按钮 :当按下此按钮,将改变所有偶数号的灯。
按钮 :当按下此按钮,将改变所有序号是 的灯。例如:
一个计数器 记录按钮被按下的次数。当宴会开始,所有的灯都亮着,此时计数器 为 。
输出格式
第一行一个正整数 ;第二行一个整数 ,表示最后计数器的数值。
第三行若干个整数,表示最后亮着的灯,以 -1 结束。
第四行若干个整数,表示最后关着的灯,以 -1 结束。
输出格式
每一行是所有灯可能的最后状态(没有重复)。
每一行有 个字符,第 个字符表示 号灯。 表示关闭, 表示亮着。这些行必须从小到大排列(看作是二进制数)。
如果没有可能的状态,则输出一行 IMPOSSIBLE。
对于 的数据,,。
思路
我们发现 ,如果我们直接深搜,则会发现复杂度飙升到 。
我们手模几个操作,发现序列的最终结果跟操作的顺序没有关系,也就是说这几种操作满足交换律。
我们还会发现,同一个操作操作两次相当于没有操作。
所以我们可以把 的操作变为 次的操作。
首先判断 的奇偶性,再使用状态压缩表示进行了哪几种操作,并且排除掉集中不符合设定的操作,对于每个可行的操作,我们存下答案,然后按照字典序排序即可。
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 105;
int n,c;
int judge[MAXN];
int x;
int ans[MAXN][20];
int anscnt = 0;
int pre[MAXN];
void make(int id){
if(id == 1){
for(int i = 1;i <= n;i++){
pre[i] = pre[i] ^ 1;
}
}else if(id == 2){
for(int i = 1;i <= n;i += 2){
pre[i] = pre[i] ^ 1;
}
}else if(id == 3){
for(int i = 2;i <= n;i += 2){
pre[i] = pre[i] ^ 1;
}
}else{//id == 4
for(int i = 1;i <= n;i += 3){
pre[i] = pre[i] ^ 1;
}
}
}
string anss[MAXN];
int main(){
scanf("%d%d", &n, &c);
while(1){
cin>>x;
if(x == -1) break;
judge[x] = 1;
}
while(1){
cin>>x;
if(x == -1) break;
judge[x] = -1;
}
for(int sta = 0;sta <= 15;sta++){
int cnt = 0;
for(int i = 1;i <= n;i++) pre[i] = 1;
for(int i = 0;i <= 3;i++){
if(sta & (1 << i)) cnt++;
}
if((cnt % 2) != (c % 2)) continue;
if(cnt > c) continue;
for(int i = 0;i <= 3;i++){
if(sta & (1 << i)){
make(i);
}
}
bool flag = true;
for(int i = 1;i <= n;i++){
if(judge[i] != 0){
if(judge[i] == -1 && pre[i] == 1){
flag = false;break;
}
if(judge[i] == 1 && pre[i] == 0){
flag = false;break;
}
}
}
if(flag){
anscnt++;
for(int i = 1;i <= n;i++){
ans[i][anscnt] = pre[i];
}
}
}
if(anscnt == 0) cout<<"IMPOSSIBLE";
else{
for(int i = 1;i <= anscnt;i++){
for(int j = 1;j <= n;j++){
anss[i].append(ans[j][i] == 1 ? "1" : "0");
}
}
sort(anss + 1,anss + anscnt + 1);
for(int i = 1;i <= anscnt;i++){
cout<<anss[i]<<endl;
}
}
return 0;
}