usaco-2.2.4 派对灯

题目描述

$N$ 盏灯排成一排，初始全部点亮。四个按钮分别翻转：所有灯、奇数号灯、偶数号灯、 $3k+1$ 号灯。给定总按压次数 $C$ ，以及最终必须亮/灭的灯号集合（以 -1 结束），求所有满足约束的最终状态（1 亮 0 灭），按二进制从小到大输出；无解输出 IMPOSSIBLE。 $10 \le N \le 100$ ， $0 \le C \le 10000$ 。

思路

同一个按钮按两次等于没按，故只需考虑四个按钮各按 $0/1$ 次的 $2^4=16$ 种奇偶组合。各按钮影响周期分别为 $1,2,2,3$ ，最小公倍数为 $6$ ，因此只需算出前 $6$ 盏灯的翻转图案即可平铺到全部 $N$ 盏灯。对每种组合，最少按压次数为 $s$ ，恰好按 $C$ 次可行的充要条件是 $s \le C$ 且 $C-s$ 为偶数。枚举 $16$ 种图案，保留满足亮灭约束的，排序去重输出。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 03:44
# update_at: 2026-10-01 03:44

import sys
from collections.abc import Iterator
from itertools import product

# 同一个按钮按两次等于没按，所以每个按钮只需考虑按 0/1 次，共 16 种奇偶组合；
# 又因奇数灯归按钮 2、偶数灯归按钮 3、3k+1 灯归按钮 4，各按钮的覆盖范围
# 以 6 为周期重复，所以整个结局只由"前 6 盏灯的翻转图案 + 总按压次数的奇偶"决定。
BUTTONS = tuple(product((0, 1), repeat=4))  # (按钮1, 按钮2, 按钮3, 按钮4) 各按 0/1 次


def flip_pattern(presses: tuple[int, ...]) -> int:
    """一组按钮奇偶对前 6 盏灯的翻转图案：第 k 位为 1 表示第 k+1 盏灯被翻转。"""
    p1, p2, p3, p4 = presses
    mask = 0
    for k in range(6):
        # 灯 k+1 受按钮 2/3 之一（看灯号奇偶）与按钮 4（灯号是 3k+1）共同作用
        if p1 ^ (p2 if k % 2 == 0 else p3) ^ (p4 if k % 3 == 0 else 0):
            mask |= 1 << k
    return mask


# 16 种奇偶组合的图案两两不同（由图案可反解出 p2、p3、p4 和 p1），
# 于是每种图案对应唯一的最少按压次数 = 四个按钮按压次数之和。
STATES = sorted((sum(presses), flip_pattern(presses)) for presses in BUTTONS)


def lamp_set(tokens: Iterator[int]) -> set[int]:
    """读到哨兵 -1 为止的一组灯号。"""
    lamps: set[int] = set()
    while (lamp := next(tokens)) != -1:
        lamps.add(lamp)
    return lamps


def lamp_state(pattern: int, lamp: int) -> int:
    """灯 lamp 的最终状态：初始全亮，被翻转过则变 0。"""
    return 1 ^ (pattern >> (lamp - 1) % 6 & 1)


def solve() -> None:
    tokens = iter(map(int, sys.stdin.buffer.read().split()))
    n, c = next(tokens), next(tokens)
    on, off = lamp_set(tokens), lamp_set(tokens)

    rows = sorted({
        ''.join(str(lamp_state(pattern, lamp)) for lamp in range(1, n + 1))
        for min_press, pattern in STATES
        # 恰好按 c 次：先够到最少次数，剩下的次数两两成对补进任意按钮
        if min_press <= c and (c - min_press) % 2 == 0
        # 亮灯与灭灯约束全部满足
        if all(lamp_state(pattern, lamp) == 1 for lamp in on)
        if all(lamp_state(pattern, lamp) == 0 for lamp in off)
    })
    print('\n'.join(rows) if rows else 'IMPOSSIBLE')


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 09:51
 * update_at: 2026-10-06 09:51
 */
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

typedef long long ll;

int n, c;
int on_lamps[105], off_lamps[105]; // 存储亮灯与灭灯约束
int on_cnt, off_cnt;

// 16 种奇偶组合对应的最少按压次数与前 6 盏灯的翻转图案（6 位二进制）
struct State {
    int press;   // 最少按压次数
    int pattern; // 前 6 盏灯的翻转图案，第 k 位为 1 表示第 k+1 盏灯被翻转
};

State states[16];
int state_cnt;

// 计算一组按钮奇偶对前 6 盏灯的翻转图案
int calc_pattern(int p1, int p2, int p3, int p4) {
    int mask = 0;
    for (int k = 0; k < 6; k++) {
        int flip = p1;
        if (k % 2 == 0) flip ^= p2; // 奇数号灯（k=0 对应灯号 1）
        else flip ^= p3;             // 偶数号灯
        if (k % 3 == 0) flip ^= p4;  // 3k+1 号灯（k=0,3 对应灯号 1,4）
        if (flip) mask |= 1 << k;
    }
    return mask;
}

// 预处理 16 种奇偶组合
void init_states() {
    state_cnt = 0;
    for (int p1 = 0; p1 <= 1; p1++)
    for (int p2 = 0; p2 <= 1; p2++)
    for (int p3 = 0; p3 <= 1; p3++)
    for (int p4 = 0; p4 <= 1; p4++) {
        states[state_cnt].press = p1 + p2 + p3 + p4;
        states[state_cnt].pattern = calc_pattern(p1, p2, p3, p4);
        state_cnt++;
    }
}

// 获取第 lamp 盏灯（1-based）的最终状态：初始全亮，被翻转则为 0
int lamp_state(int pattern, int lamp) {
    int pos = (lamp - 1) % 6;
    int flipped = (pattern >> pos) & 1;
    return 1 ^ flipped;
}

// 检查某个图案是否满足所有亮灯与灭灯约束
bool check(int pattern) {
    for (int i = 0; i < on_cnt; i++)
        if (lamp_state(pattern, on_lamps[i]) != 1) return false;
    for (int i = 0; i < off_cnt; i++)
        if (lamp_state(pattern, off_lamps[i]) != 0) return false;
    return true;
}

// 生成长度为 n 的灯状态字符串
string build_str(int pattern) {
    string s;
    s.resize(n);
    for (int i = 1; i <= n; i++)
        s[i - 1] = '0' + lamp_state(pattern, i);
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    init_states();

    cin >> n >> c;

    on_cnt = 0;
    while (true) {
        int x;
        cin >> x;
        if (x == -1) break;
        on_lamps[on_cnt++] = x;
    }

    off_cnt = 0;
    while (true) {
        int x;
        cin >> x;
        if (x == -1) break;
        off_lamps[off_cnt++] = x;
    }

    vector<string> ans;
    for (int i = 0; i < state_cnt; i++) {
        int press = states[i].press;
        int pattern = states[i].pattern;
        // 恰好按 c 次：最少次数不超过 c，且差值为偶数（多出来的次数成对抵消）
        if (press > c || (c - press) % 2 != 0) continue;
        if (!check(pattern)) continue;
        ans.push_back(build_str(pattern));
    }

    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());

    if (ans.empty()) {
        cout << "IMPOSSIBLE\n";
    } else {
        for (size_t i = 0; i < ans.size(); i++)
            cout << ans[i] << "\n";
    }

    return 0;
}

目录

题目描述

思路

参考代码