题目描述
为了照亮 IOI98 的盛大晚宴,我们共提供了 $N$ 栈灯来进行照明,编号为 $1∼N$。
有以下四个按钮控制灯光:
按钮 1:按下此按钮时,所有灯都会更改其状态:“开”的灯熄灭,而“关”的灯点亮。
按钮 2:更改所有编号为奇数的灯的状态。
按钮 3:更改所有编号为偶数的灯的状态。
按钮 4:更改所有编号为 $3K+1$ (即1,4,7…)的灯的状态。
计数器 C 记录了按钮按下的总次数。
当晚宴开始时,所有灯光都是亮的,且计数器设置为 0。
现在给定你某一时刻时,计数器记录的按钮总按下次数以及此时部分灯的状态,请你找出所有可能的全部灯状态有哪些。
输入格式
- 第一行包含整数 $N$ 表示灯的数量。
- 第二行包含整数 $C$ 表示按钮按下次数。
- 第三行包含若干个整数,表示一些(不一定是全部,也可能没有)亮着的灯的编号,最后以一个 -1 作为行结尾。
- 第四行包含若干个整数,表示一些(不一定是全部,也可能没有)灭着的灯的编号,最后以一个 -1 作为行结尾。
输出格式
每行输出一个可能的所有灯的状态,用一个长度为 $N$ 的由 $0$ 和 $1$ 构成的字符串来表示,字符串中第 $i$ 个字符如果是 $0$,则表示第 $i$ 个灯是灭的,如果是 $1$ 则表示第 $i$ 个灯是亮的。
将这些状态表示都看作二进制数,从小到大依次输出。
如果没有可能的所有灯状态,则输出 IMPOSSIBLE。
数据范围
$10≤N≤100$
$0≤C≤10000$
输入样例
10
1
-1
7 -1
输出样例
0000000000
0101010101
0110110110
思维 + 打表
该题一眼望去,执笔很久,不会,又灰溜溜跑回去看视频去了。
该题有两条基本性质:
- 对同一个按键按两次相当于没按。
- 与按键按的次序无关,只与按键按的总次数有关。
上述两条性质应该十分好理解,第一条性质其实就是对同一个按键改变两次状态,类似负负得正,其状态并没有发生变化,第二条性质则表示按键的状态只与按键状态改变的次数有关,第 1 次改变状态还是第 3 次改变状态其实并不重要,只要你改变了状态就行。
有了上述两条性质时,我们再来继续推。
一个按键可以选择按,也可以选择不按,此时有两种状态,总共有 $2^4 = 16$ 种情况,然而,按下 1 和 2 等价于按下 3,按下 1 和 3 等价于按下 2,按下 2 和 3 等价于 按下 1,由此该 $16$ 种情况可以继续进行优化。
0 0 0 0 --> 不按
1 0 0 0 --> 按下 1 号键
0 1 0 0 --> 按下 2 号键
0 0 1 0 --> 按下 3 号键
0 0 0 1 --> 按下 4 号键
1 1 0 0 --> 按下 12 号键 等价于按下 3 号键
1 0 1 0 --> 按下 13 号键 等价于按下 2 号键
1 0 0 1 --> 按下 14 号键
0 1 1 0 --> 按下 23 号键 等价于按下 1 号键
0 1 0 1 --> 按下 24 号键
0 0 1 1 --> 按下 34 号键
1 1 1 0 --> 按下 123 号键 等价于不按
1 1 0 1 --> 按下 124 号键 等价于按下 34 号键
1 0 1 1 --> 按下 134 号键 等价于按下 24 号键
0 1 1 1 --> 按下 234 号键 等价于按下 14 号键
1 1 1 1 --> 按下 1234 号键 等价于按下 4 号键
$16$ 种情况就可以优化为 $8$ 种情况,我们再仔细看一下这 8 种情况,如何进行分类讨论呢?
该 8 种情况为:
无、1、2、3、4、14、24、34
当 $C == 0$ 时,取 无。
当 $C == 1$ 时,取 1、2、3、4。
当 $C == 2$ 时,取 无、1(2、3)、2(1、3)、3(1、2)、14、24、34。
当 $C >= 3$ 时,取 无、1、2、3、4、14、24、34。
对 $C >= 3$ 时,为何能取到 $8$ 种情况进行讨论。
当 $C >= 3$ 且为奇数时
无:取一个 1,其余变化得到 1
1: 全为 1
2: 全为 2
3: 全为 3
4: 全为 4
14:取一个 4,其余变化得到 1
24:取一个 4,其余变化得到 2
34:取一个 4,其余变化得到 3
当 $C >= 3$ 且为偶数时,同理上述证明。
C++ 代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, c;
int state[8][6] = { // 打表
{1, 1, 1, 1, 1, 1}, // 0
{0, 0, 0, 0, 0, 0}, // 1
{1, 0, 1, 0, 1, 0}, // 2
{0, 1, 0, 1, 0, 1}, // 3
{0, 1, 1, 0, 1, 1}, // 4
{1, 0, 0, 1, 0, 0}, // 14
{0, 0, 1, 1, 1, 0}, // 24
{1, 1, 0, 0, 0, 1}, // 34
};
vector <int> on, off;
bool check(int s[6])
{
// 判断合法性
for (auto id : on) {
if (!s[id % 6]) {
return false;
}
}
for (auto id : off) {
if (s[id % 6]) {
return false;
}
}
return true;
}
void work(vector <int> ids)
{
// C++ 17 特性,按字典序排序
sort(ids.begin(), ids.end(), [](int a, int b) {
for (int i = 0; i < 6; ++i) {
if (state[a][i] != state[b][i]) {
return state[a][i] < state[b][i];
}
}
return false;
});
bool has_print = false;
for (auto id : ids) {
if (check(state[id])) {
has_print = true;
for (int i = 0; i < n; ++i) {
cout << state[id][i % 6];
}
cout << endl;
}
}
if (!has_print) {
puts("IMPOSSIBLE");
}
}
int main()
{
cin >> n >> c;
int id;
// 已知部分开着的灯
while (cin >> id && id != -1) {
on.push_back(id - 1);
}
// 已知部分关着的灯
while (cin >> id && id != -1) {
off.push_back(id - 1);
}
// 分类讨论所有情况
if (!c) {
work({0});
}
else if (c == 1) {
work({1, 2, 3, 4});
}
else if (c == 2) {
work({0, 1, 2, 3, 5, 6, 7});
}
else {
work({0, 1, 2, 3, 4, 5, 6, 7});
}
return 0;
}
补充一下:
之所以可以只看6盏灯的情况,是因为
第一个操作改变所有灯
第二个操作改变编号为2k+1的灯
第三个操作改变编号为2k的灯
第四个操作改变编号为3k+1的灯
取2,3最小公倍数,得到灯的状态每6个一循环,也就是说i和i + 6*x的状态相同。