洛谷 P1161 开灯题解

# 前言

我一开始完全没想明白怎么写的，问了GPT才一知半解。

# 题目描述

在一条无限长的路上，有一排无限长的路灯，编号为 $1,2,3,4,\dots$。

每一盏灯只有两种可能的状态，开或者关。如果按一下某一盏灯的开关，那么这盏灯的状态将发生改变。如果原来是开，将变成关。如果原来是关，将变成开。

在刚开始的时候，所有的灯都是关的。小明每次可以进行如下的操作：

指定两个数，$a,t$（$a$ 为实数，$t$ 为正整数）。将编号为 $\lfloor a\rfloor,\lfloor 2 \times a\rfloor,\lfloor3 \times a\rfloor,\dots,\lfloor t \times a\rfloor$ 的灯的开关各按一次。其中 $\lfloor k \rfloor$ 表示实数 $k$ 的整数部分。

在小明进行了 $n$ 次操作后，小明突然发现，这个时候只有一盏灯是开的，小明很想知道这盏灯的编号，可是这盏灯离小明太远了，小明看不清编号是多少。

幸好，小明还记得之前的 $n$ 次操作。于是小明找到了你，你能帮他计算出这盏开着的灯的编号吗？

# 输入格式

第一行一个正整数 $n$，表示 $n$ 次操作。

接下来有 $n$ 行，每行两个数，$a_i,t_i$。其中 $a_i$ 是实数，小数点后一定有 $6$ 位，$t_i$ 是正整数。

# 输出格式

仅一个正整数，那盏开着的灯的编号。

# 样例 #1

# 样例输入 #1

1
2
3
4
3
1.618034 13
2.618034 7
1.000000 21

# 样例输出 #1

1
20

# 提示

记 $T=\sum \limits_{i=1}^n t_i = t_1+t_2+t_3+\dots+t_n$。

对于 $30%$ 的数据，满足 $T \le 1000$；
对于 $80%$ 的数据，满足 $T \le 200000$；
对于 $100%$ 的数据，满足 $T \le 2000000$；
对于 $100%$ 的数据，满足 $n \le 5000$，$1 \le a_i<1000$，$1 \le t_i \le T$。

数据保证，在经过 $n$ 次操作后，有且只有一盏灯是开的，不必判错。而且对于所有的 $i$ 来说，$t_i\times a_i$ 的最大值不超过 $2000000$。

# 题解

这道题不用判错，就不用写错误处理了。

其实比较简单，维护一个列表，遍历操作过的灯，如果已经在列表内那就删除，不在就添加。然后最后打印出该列表内的值就好。

这是我最开始写出来的代码，虽然样例没问题，但是测试全炸：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
n = int(input())
switch_list = []
for i in range(n):
    str_input = input()
    a = float(str_input.split()[0])
    t = int(str_input.split()[1])

    for j in range(t):
        if a * j in switch_list:
            switch_list.remove(a * j)
        else:
            switch_list.append(a * j)

print(int(switch_list.pop()))

下面的是经过 GPT 优化的代码。GPT 说优化了以下内容：

在计算灯的编号时，使用 int(a * j) 来确保灯的编号是整数，避免浮点精度问题引起错误。但是好像感知不明显。
最后输出改为列表的第一项而非pop，理论上来说应该没有区别。但是套int是没有必要的。

其实只需要把 int() 去掉就可以了。上面一份就错在这里。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
n = int(input())
switch_list = []

for _ in range(n):
    str_input = input()
    a = float(str_input.split()[0])
    t = int(str_input.split()[1])

    for i in range(1, t + 1):
        lamp = int(a * i)
        if lamp in switch_list:
            switch_list.remove(lamp)
        else:
            switch_list.append(lamp)

print(switch_list[0])

所以我让GPT重写了所有代码，最终 AC 了：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
n = int(input())
operations = [tuple(map(float, input().split())) for _ in range(n)]

lit_lamps = set()

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

print(lit_lamps.pop())

根据 GPT 自己的说法，set 的时间复杂度是 O(1), list 则是 O(n)，n 为列表长度，在处理大量数据时 set 能明显节省时间。所以我将我代码中的 list 修改为 set 后就 AC 了，GPT 所言不虚。