正经题解｜灯光控制

题目分析

二进制模拟

有 $30$ 盏灯，编号为 $[0,29]$，一开始所有的灯都是熄灭的，灯只有两种状态开与关。

设 $s$ 初始为 $0$。
当第 $i$ 盏灯亮时，$s = s + 2^{i}$，当第 $i$ 盏灯熄灭时 $s = s - 2^{i}$。

对于第 $i$ 盏灯的状态，我们可以用二进制中的 $1$ 与 $0$ 表示，即 $s$ 在二进制下的第 $i$ 位。如编号为 $1,4,5$ 的灯亮， $s$ 在二进制中为 0b110010。

控制某个灯的开关，按照题目意思开着会变为关，关的会变为开，用异或就行了。

AC代码

#include <iostream>
using namespace std;
int main() {
    int t;
    cin >> t;
    int s = 0;
    while(t--) {
        int i;
        cin >> i;
        s ^= (1 << i);
        cout << s << endl;
    }
    return 0;
}

复杂度分析

$O(t)$。