开关灯

题意

有 $N$ 盏灯。1 号人先把所有灯关闭；第 $i$ 号人把编号为 $i$ 的倍数的灯切换状态。操作到第 $M$ 人后，按升序输出仍关闭的灯号，灯号之间用逗号隔开。

思路

1 号人操作后，所有灯都处于关闭状态。用布尔数组记录每盏灯是否已被后续操作切换为打开；对每个 person，枚举 person, 2 * person, ... 并翻转对应状态。

最后按编号扫描数组，保留状态为关闭的灯号，再用 ",".join(...) 一次性处理逗号格式。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10light_count, person_count = map(int, input().split())

# 1 号操作后所有灯关闭；True 表示后来被切换为打开。
is_open = [False] * (light_count + 1)
for person in range(2, person_count + 1):
    for light in range(person, light_count + 1, person):
        is_open[light] = not is_open[light]

closed_lights = (str(light) for light in range(1, light_count + 1) if not is_open[light])
print(",".join(closed_lights))

C++代码

cpp

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#include <cstdio>

int a[50005] = {0};
int main(){
    int n,m;
    int i,j;
    scanf("%d%d",&n,&m);

    for (i=2;i<=m;i++){
        for(j=i;j<=n;j+=i){
            a[j] = !a[j];
        }
    }
    for (i=1;i<=n;i++){
        if( !a[i]){
            printf("%d",i);
            break;
        }
    }
    for( i++; i<=n;i++){
        if( !a[i]){
            printf(",%d",i);
        }
    }
    return 0;
}

复杂度

第 $i$ 个人操作约 $N/i$ 盏灯，总时间复杂度为 $O(N \log M)$ ，数组空间复杂度为 $O(N)$ 。

总结

“处理某个编号的所有倍数”可直接使用步长为该编号的 range，代码与题意一一对应。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结