开灯

GitHub跳转原题关系图返回列表

用集合保存当前开着的灯，每次操作到某灯就按存在性切换其开关状态。

OJ: luogu

题目 ID: P1161

难度:入门

标签:模拟集合python

日期: 2026-07-15 18:54

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. Pythonic 写法
  6. 复杂度
  7. 总结

题意

初始所有灯都是关的。每次操作给出实数 a 和整数 t，依次切换编号：

text
floor(a), floor(2a), ..., floor(ta)

所有操作完成后，题目保证恰好只有一盏灯是开的，输出它的编号。

思路

灯只关心“当前是否开着”。可以用集合 on_lights 保存所有当前开着的灯。

当某盏灯被按一次：

  • 如果它已经在集合里，说明原来开着，按完变关，从集合删除；
  • 如果它不在集合里，说明原来关着，按完变开，加入集合。

这正好是“切换状态”的含义。

所有操作结束后，集合里只剩一个元素，用 next(iter(on_lights)) 取出来输出。

这题是集合模拟开关状态，不创建额外 brute.py。

Python 知识

  • /home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：每行混合实数和整数时，可以先 split() 再分别转换。
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：set 适合保存当前打开的灯，并支持快速增删查。
  • int(a * k) 对正数等价于向下取整。
  • next(iter(on_lights)) 从只含一个元素的集合中取出这个元素。

代码

python
n = int(input())

on_lights = set()

for _ in range(n):
    a_text, t_text = input().split()
    a = float(a_text)
    t = int(t_text)

    for k in range(1, t + 1):
        light = int(a * k)
        if light in on_lights:
            on_lights.remove(light)
        else:
            on_lights.add(light)

print(next(iter(on_lights)))
cpp
/**
 * 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-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

bool lights[2000005]; // lights[id] = true 表示灯亮，false 表示灯灭
int n;

int main() {
    cin >> n;
    double a;
    int t;
    for (int i = 1; i <= n; i++) {
        cin >> a >> t;
        for (int k = 1; k <= t; k++) {
            int id = int(a * k); // 取整得到灯编号
            lights[id] = !lights[id]; // 切换开关
        }
    }
    // 找到唯一亮着的灯
    for (int i = 1; ; i++) {
        if (lights[i]) {
            cout << i;
            return 0;
        }
    }
}

Pythonic 写法

集合对称差 on_lights ^= {light} 一键切换开关：

python
n = int(input())
on_lights = set()
for _ in range(n):
    a, t = input().split()
    a, t = float(a), int(t)
    for k in range(1, t + 1):
        on_lights ^= {int(a * k)}
print(next(iter(on_lights)))

复杂度

总操作次数为 T = sum(t_i)，每次集合增删查均摊 O(1)O(1)，总时间复杂度是 O(T)O(T)。空间复杂度取决于同时开着的灯数量，最坏 O(T)O(T)。

总结

开关题最适合用集合表示“当前为开”的对象。每次被按到就把成员关系反转，最后集合中剩下的就是答案。