小韦老师@神犇营-my0184-开关灯
程序员文章站
2024-03-18 21:50:28
...
小韦老师@神犇营-my0184-开关灯
题目:
描述
假设有 N 盏灯 (N 为不大于 5000 的正整数),从 1 到 N 按顺序依次编号,初始时全部处于开启状态;有 M 个人 (M 为不大于 N 的正整数)也从 1 到 M 依次编号。
第一个人 (1 号)将灯全部关闭,第二个人 (2 号)将编号为 2 的倍数的灯打开,第三个人 (3号) 将编号为 3 的倍数的灯做相反处理(即,将打开的灯关闭,将关闭的灯打开)。依照编号递增顺序,以后的人都和 3 号一样,将凡是自己编号倍数的灯做相反处理。
请问:当第 M 个人操作之后,哪几盏灯是关闭的,按从小到大输出其编号,其间用逗号间隔。
输入
输入正整数 N 和 M,以单个空格隔开。
输出
顺次输出关闭的灯的编号,其间用逗号间隔。
输入样例
10 10
输出样例
1,4,9
题解:
思路:
思路:
1.定义一个 bool 数组用作标记数组,用来表示灯的状态,下标表示灯的编号,值为 fasle 表示该灯灭,true 表示灯亮。因为第一个人 (1 号)将灯全部关闭,所以数组初始化为 false(全局 bool 数组会自动初始化为 false)。
const int N = 5e3 + 10;
bool light[N];
2.用 for 循环枚举 2~n,将编号为 2 的倍数的灯打开(标记数组对应置为 true),这里循环变量 i 的变化为 i += 2(想一想为什么)。
for (int i = 2; i <= n; i += 2) {
light[i] = true;
}
3.将从编号为 3 的灯开始,将它们编号倍数的灯置为相反状态:开的灯变灭,灭着的灯打开(标记数组为 false 置为 true,true 置为 false),这里用双层 for 循环来完成(注意内层循环变量 j 的变化是 j = j + i,想一想为什么):
for (int i = 3; i <= m; i++) {
for (int j = i; j <= n; j = j + i) {
if (light[j]) light[j] = false;
else light[j] = true;
}
}
4.最后输出标记数组的的值为 false 的对应的下标即可。 两个灯的编号之间用逗号隔开,最后一个编号后无逗号(循环变量 i != 1,输出逗号,想一想为什么)。
完整代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10;
// 标记数组,下标表示灯的编号,值为fasle表示该灯灭,true表示灯亮
bool light[N];
int main() {
freopen("5.in", "r", stdin);
freopen("5.out", "w", stdout);
int n, m;
cin >> n >> m;
// 编号为2的倍数的灯打开,标记数组置为true
for (int i = 2; i <= n; i += 2) {
light[i] = true;
}
// 从编号为3的灯开始,将它们编号倍数的灯置为相反状态
for (int i = 3; i <= m; i++) {
for (int j = i; j <= n; j = j + i) {
if (light[j]) light[j] = false;
else light[j] = true;
}
}
cout << 1; // 先将1输出,因为编号为1的灯一定是关闭的
for (int i = 2; i <= n; i++) {
if (!light[i]) {
if (i != 1) cout << ","; // 除了第1个,前面输出逗号
cout << i;
}
}
return 0;
}