题解：P1161 开灯

2011hym · 2025-06-07 16:30:34 · 题解

更好的阅读体验。

题目分析

给定一个无限长的序列，初始时所有灯都是关闭状态。进行 n 次操作，每次操作给定 a 和 t，将编号为\left \lfloor a \right \rfloor,\left \lfloor 2\times a \right \rfloor, \dots ,\left \lfloor t\times a \right \rfloor 的灯的状态切换。经过所有操作后，只有一盏灯是开着的，我们需要找出这盏灯的编号。

解题思路

每次操作实际上是转换灯的状态。我们可以用一个数组来记录每个灯被切换的次数。

初始时所有灯的状态为 0。对于每次操作，计算 \left \lfloor i\times a \right \rfloor（i 是从 1 到 t），并将对应位置的数异或 1（根据异或的性质可知，这其实就是状态转换）。

代码时间复杂度为 O(n\times t)，包能过的。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000001;
int light[MAXN];//状态表示。
int n, t;
double a;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a >> t;
        for (int j = 1; j <= t; j++) {
            int index = (int)(j * a);
            light[index] ^= 1;//切换状态。
        }
    }
    //找出唯一亮着的灯。
    for (int i = 2; i <= MAXN; i++) {
        if (light[i] == 1) {
            cout << i << endl;
            break;
        }
    }

    return 0;
}

update： 2025.7.24 修复了一处错误。