题解：P1161 开灯

题目分析

给定一个无限长的序列，初始时所有灯都是关闭状态。进行

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)

，包能过的。

代码实现

CPP

#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 修复了一处错误。

文章操作

题目分析

解题思路

代码实现

相关推荐

评论

题解：P1161 开灯