目录

USACO Party Lamps


有 \(N\) \((10 \le N \le 100)\) 盏亮瞎眼的灯,从 1 到 N 编号。

有四种按钮:

按钮用途
1反转所有的灯(开变为关,关变为开)
2反转编号为奇数的灯(如 1,3,5)
3反转编号为偶数的灯(如 2,4,6)
4反转编号为 \(3k+1 ; 当 ; k \ge 0\) 的灯 (如 1,4,7)

给出 \(C\)(按下按钮的次数, \(0 \le C \le 10000\))和一些灯最后的状态,找出所有组不同的灯的状态。

开始时所有灯都开着,\(C = 0\)。




题解

从题意中,我们可以知道:

  1. 每6个灯是一组,因为按钮作用1,2,3的最小公倍数是6(按钮1改变每个灯,按钮2和3改变每2个灯中的一个,按钮4改变每3个灯中的1个)。

  2. 如果按下同一个按钮两次,效果和不按该按钮相同。用逻辑符号表示,\( \sim(\sim p) = p \)。一个按钮只有开或关两种可能,一共4种按钮。所以,一共有 \( 2^4 = 16 \) 种可能。

那么,

  • 当 \(C = 0\),检查当前状态是否符合条件。
  • 当 \(C = 1\),按下每个按钮一次。
  • 当 \( C \ge 2 \), 检查所有16种可能。

这是个练习 bitset 的好机会。原来是想把 bitset 放进 set 里的,后来发现 set 不支持对 bitset 进行排序。如果有谁知道怎么让它支持对 bitset 进行排序的,麻烦告诉我一下~


代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
/*
ID: cepheid1
LANG: C++11
TASK: lamps
*/

#include<fstream>
#include<algorithm>
#include<bitset>
#include<vector>
#include<map>
#include<set>
#include<string>
using namespace std;
ifstream fin("lamps.in");
ofstream fout("lamps.out");

/* convert bitset to store in map and set to get ordered */
set<short> st;
map<short, string>mp;

bitset<6> bt; // simulates 6 lamps
bitset<4> light; // simulates 4 buttons
bool on[7], off[7];

int N, C, a;

bool chk_on() {
	for (int i = 0; i < 6 ; i++) {
		if (on[i] && !(bt[6-i-1])) return false;
	}
	return true;
}

bool chk_off() {
	for (int i = 0; i < 6 ; i++) {
		if (off[i] && (bt[6-i-1])) return false;
	}
	return true;
}

void op(int x) {
	switch(x) {
		case 1:
			bt.flip();
			break;
		case 2:
			for (int i = 1; i < 6; i+=2) bt.flip(i);
			break;
		case 3:
			for (int i = 0; i < 6; i+=2) bt.flip(i);
			break;
		case 4:
			bt.flip(2);
			bt.flip(5);
			break;
		default:
			break;
	}
}

int main(void) {
	fin >> N >> C;
	while (fin >> a && a != -1) {
	    if (a%6 == 0) on[5] = true;
        else on[(a%6-1)] = true;
	}
	while (fin >> a && a != -1) {
		if (a%6 == 0) off[5] = true;
        else off[(a%6-1)] = true;
	}
	fin.close();

	bt.set();

	if (C == 0) {
		if (chk_on() && chk_off()) {
			if (!st.count(bt.to_ulong())) {
				mp[(short)bt.to_ulong()] = bt.to_string();
				st.insert((short)bt.to_ulong());
			}
		}
	} else if (C == 1) {
		for (int i = 0; i < 4; i++) {
			bt.set();
			op(i);
			if (chk_on() && chk_off()) {
				if (!st.count(bt.to_ulong())) {
					mp[(short)bt.to_ulong()] = bt.to_string();
					st.insert((short)bt.to_ulong());
				}
			}
		}
	} else {
		for (int i = 0; i < 16; i++) {
			bt.set();
			light = i;
			for (int j = 0; j < 4; j++) {
				if (light[j]) op(j+1);
			}
			if (chk_on() && chk_off()) {
				if (!st.count(bt.to_ulong())) {
					mp[(short)bt.to_ulong()] = bt.to_string();
					st.insert((short)bt.to_ulong());
				}
			}
		}
	}

	if (st.empty()) {
		fout << "IMPOSSIBLE\n";
	} else {
		int len = 0;
		string s;
		for (auto i : st) {
			len = 0;
			s = "";
			while (len <= N) {
				s += (mp[i]);
				len += (mp[i]).size();
			}
			fout << s.substr(0, N) << endl;
		}
	}
	fout.close();
	return 0;
}