【GESP】C++三级练习 luogu-P1161 开灯
GESP C++三级练习，一维数组练习，难度★★☆☆☆。
luogu-P1161 开灯
题目要求
题目描述
在一条无限长的路上，有一排无限长的路灯，编号为 $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$。
题目分析
解题思路
本题的解题思路如下：
- 问题本质：
- 给定一系列操作，每次操作会按指定规则改变一些灯的状态
- 每个操作包含两个参数：实数 $a$ 和正整数 $t$
- 每次操作会改变编号为 $\lfloor a \rfloor$, $\lfloor 2 \times a \rfloor$, …, $\lfloor t \times a \rfloor$ 的灯的状态
- 最终只有一盏灯是亮着的，需要找出这盏灯的编号
- 解题关键：
- 核心思路 - 状态模拟：
- 使用数组记录每盏灯的状态：
- 创建一个足够大的数组 $array$（根据题目提示 $2000005$ 大小足够）
- $0$ 表示灯是关闭的，$1$ 表示灯是打开的
- 模拟每次操作：
- 对于每次操作的参数 $a$ 和 $t$
- 计算需要改变状态的灯的编号：$\lfloor i \times a \rfloor$ ($i$ 从 $1$ 到 $t$)
- 使用异或操作($\oplus 1$)切换对应灯的状态
- 最后遍历数组，找到值为 $1$ 的位置，即为答案
- 使用数组记录每盏灯的状态：
- 核心思路 - 状态模拟：
- 复杂度分析：
- 时间复杂度：$O(n \times t_{max})$，其中n为操作次数，t_max为单次操作最大次数
- 空间复杂度：$O(2000005)$，需要一个固定大小的数组存储灯的状态
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
// 用于存储每个灯的状态的数组，0表示关闭，1表示打开
int array[2000005];
int main() {
// n表示操作次数
int n;
std::cin >> n;
// 循环处理每次操作
for (int i=0; i < n; i++) {
// a为实数倍数，t为操作次数上限
double a;
int t;
std::cin >> a >> t;
// 对于每次操作，计算需要改变状态的灯的编号
for (int j = 1; j <=t; j++) {
// 计算当前需要改变状态的灯的编号
int idx = a * j;
// 使用异或操作切换灯的状态（0变1，1变0）
array[idx] ^= 1;
}
}
// 遍历所有可能的灯，找出唯一一个打开的灯
for (int i=0; i < 2000005; i++) {
// 如果找到值为1的位置，说明这盏灯是打开的
if (array[i] == 1) {
std::cout << i << " ";
}
}
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP各级别考纲、真题讲解、知识拓展和练习清单等详见【置顶】【GESP】C++ 认证学习资源汇总
“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
