[USACO2.2] 派对灯 Party Lamps

题目描述

我们有 \(n\) 盏彩色灯，他们分别从 \(1 \sim n\) 被标上号码。这些灯都连接到四个按钮：

按钮 \(1\)：当按下此按钮，将改变所有的灯：本来亮着的灯就熄灭，本来是关着的灯被点亮。

按钮 \(2\)：当按下此按钮，将改变所有奇数号的灯。

按钮 \(3\)：当按下此按钮，将改变所有偶数号的灯。

按钮 \(4\)：当按下此按钮，将改变所有序号是 \(3k+1 \ (k \in [0,+\infty) \cap \mathbb Z)\) 的灯。例如：\(1,4,7,10 \dots\)

一个计数器 \(c\) 记录按钮被按下的次数。当宴会开始，所有的灯都亮着，此时计数器 \(c\) 为 \(0\)。

输出格式

第一行一个正整数 \(n\)；第二行一个整数 \(c\)，表示最后计数器的数值。

第三行若干个整数，表示最后亮着的灯，以 -1 结束。

第四行若干个整数，表示最后关着的灯，以 -1 结束。

输出格式

每一行是所有灯可能的最后状态（没有重复）。

每一行有 \(n\) 个字符，第 \(i\) 个字符表示 \(i\) 号灯。\(0\) 表示关闭，\(1\) 表示亮着。这些行必须从小到大排列（看作是二进制数）。

如果没有可能的状态，则输出一行 IMPOSSIBLE。

对于 \(100\%\) 的数据，\(10 \le n \le 100\)，\(0 \le c \le 10^4\)。

思路

我们发现 \(0 \le c \le 10^4\)，如果我们直接深搜，则会发现复杂度飙升到 \(O(2^{10 ^ 4})\)。

我们手模几个操作，发现序列的最终结果跟操作的顺序没有关系，也就是说这几种操作满足交换律。

我们还会发现，同一个操作操作两次相当于没有操作。

所以我们可以把 \(c \le 10 ^ 4\) 的操作变为 \(c \le 4\) 次的操作。

首先判断 \(c\) 的奇偶性，再使用状态压缩表示进行了哪几种操作，并且排除掉集中不符合设定的操作，对于每个可行的操作，我们存下答案，然后按照字典序排序即可。

\(code\)

#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;
}