欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

小韦老师@神犇营-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;

}