二级
C++ 算法考级专栏
真题分析、矩阵探测、递归回溯与基础语法
🎨 视觉封面【GESP】C++二级练习 luogu-B2092, 开关灯
📅 2025-01-15·✍️ OneCoder·计算中...·⏱️ 4 分钟
#GESP#C++#多重循环
GESP二级练习，多层循环分支嵌套练习，难度★✮☆☆☆。
luogu-B2092 开关灯
题目要求
题目描述
假设有 盏灯（ 为不大于 的正整数），从 到 按顺序依次编号，初始时全部处于开启状态；第一个人（ 号）将灯全部关闭，第二个人（ 号）将编号为 的倍数的灯打开，第三个人（ 号）将编号为 的倍数的灯做相反处理（即，将打开的灯关闭，将关闭的灯打开）。依照编号递增顺序，以后的人都和 号一样，将凡是自己编号倍数的灯做相反处理。问当第 个人操作完之后，有哪些灯是关闭着的？
输入格式
输入为一行，一个整数 ，为灯的数量。
输出格式
输出为一行，按顺序输出关着的灯的编号。编号与编号之间间隔一个空格。
样例输入 #1
BASH
10
样例输出 #1
BASH
1 4 9
样例输入 #2
BASH
5
样例输出 #2
BASH
1 4
题目分析
- 初始化所有灯为关着的状态，确保每个灯的初始状态都是关闭的。
- 将2的倍数编号的灯打开，例如编号为2、4、6等的灯将被打开。
- 从3开始，依次处理每个数i，将编号为i的倍数的灯的开关状态切换。例如，处理3时，将编号为3、6、9等的灯的状态切换，处理4时，将编号为4、8、12等的灯的状态切换，以此类推。
- 最终输出所有关着的灯的编号，输出的编号将是最终状态下关闭的灯的编号。
示例代码
CPP
#include <iostream>
using namespace std;
int main() {
int n; // 输入的灯的数量
cin >> n;
int arr[n]; // 创建一个大小为n的数组，用于存储每个灯的状态
for (int i = 0; i < n; i++) {
arr[i] = false; // 初始化所有灯为关着的状态
}
for (int i = 1; i < n; i += 2) {
arr[i] = true; // 将2的倍数编号的灯打开
}
for (int i = 3; i <= n; i++) {
for (int j = i - 1; j < n; j += i) {
arr[j] = !arr[j]; // 根据每个数i，切换编号为i的倍数的灯的开关
}
}
for (int i = 0; i < n; i++) {
if (!arr[i]) {
cout << i + 1 << " "; // 输出关着的灯的编号
}
}
return 0;
}
还有一种快速算法，就是根据数学运算可以发现，最终关闭态的灯编号都是平方数，因为只有平方数会被操作偶数次，最终保持关闭状态。因此代码如下：
CPP
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
for (int i = 1; i * i <= n; i++) {
cout << i * i << " ";
}
return 0;
}
💡 OneCoder 资源指引
所有代码开源上传至 GitHub：yummy-code 仓库 · GESP 专题站：GESP WIKI
🤝 技术交流与答疑
欢迎加入：C++ GESP/CSP 考级答疑群（688906745） 与 Java/Python交流群（982860385），点击可直接加群。
📚
猜你想读 · 相关文章推荐
OneCoder (lihongzheshuai)
一个中年人的自留地，记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址：coderli.com
💬 读者留言与交流
还没有留言，快来成为第一个讨论者吧！