当前位置：首页 > article >正文

【C++】B2092 开关灯

article 2025/3/1 23:16:59

在这里插入图片描述

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C++

文章目录

💯前言
💯题目描述和解析
- 题目描述
- 输入格式
- 输出格式
- 解析
💯实现代码对比：我的做法和老师的做法
- 我的代码实现
- - 代码分析
  - 优点
  - 问题
- 老师的代码实现
- - 代码分析
💯优化思考
- 优点
💯概念解释
💯小结

在这里插入图片描述

💯前言

在编程与算法学习中，想要析解一个优雅且有效的解法，基于了解题目规划与算法选择是自上考的重要步骤。本文重点分析 B2092 题目，并对不同解法进行比较和优化。通过对传统实现和优化实现的设计，带领课题中处理问题的方法和思考。
C++ 参考手册

💯题目描述和解析

B2092 开关灯
在这里插入图片描述

题目描述

假设有 N 盏灯（N 为不超过 5000 的正整数），从 1 到 N 按顺序依次编号，初始时全部处于关闭状态：

第一个人（编号 1） 将所有灯打开；
第二个人（编号 2） 将编号为 2 的倍数灯切换为关闭；
第三个人（编号 3） 将编号为 3 的倍数灯切换为相反状态；以此类推；

最后问：当第 N 个人操作完成之后，有部分灯是关闭状态。问：这些关闭灯的编号是什么？

输入格式

一行，一个正整数 N，为灯的总量。

输出格式

一行，按顺序输出关闭灯的编号，编号与编号之间间隔一个空格。

解析

通过进一步分析可得：

灯被操作次数规则：
- 灯编号是一个正整数，被操作的次数等于该数的因子总数（包括自身）；
- 非完全平方数因子总是偶数；完全平方数的因子数是奇数。
灯最终状态：
- 被操作偶数次，灯为关闭状态；
- 被操作奇数次，灯为打开状态。
解析完全平方数特性：
- 对于每一个完全平方数，其因子数是奇数。例如，数 36 (= 6^2) 的因子为 1、2、3、6、9、18、36，共 9 个，是奇数。
- 非完全平方数，例如 12，其因子为 1、2、3、4、6、12，共 6 个，是偶数。

因此，最终只需要找出 1 到 N 中的非完全平方数的编号。

💯实现代码对比：我的做法和老师的做法

我的代码实现

以下是我的代码：

#include <iostream>
using namespace std;

const int N = 5000;
int arr[5000]; 

int main()
{
    int n = 0;
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        arr[i] = 1;
    }

    if (n == 1 || n == 2 || n == 3)
        cout << 1 << endl;    
    else if (n > 3)
    {
        for (int i = 1; i <= n; i++)
        {
            arr[i] = 0;
        }
        for (int i = 2; i <= n; i += 2)
        {
            arr[i] = 1;
        }

        for (int i = 3; i <= n; i++)
        {
            for (int j = i; j <= n; j += i)
            {
                if (arr[j] == 0)
                    arr[j] = 1;
                else
                    arr[j] = 0;
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (arr[i] == 0)
            cout << i << " ";
    }

    return 0;
}

在这里插入图片描述

代码分析

初始化数组：
- 使用 arr[i] 表示灯的状态，1 表示关闭，0 表示打开。
- 初始化为全关闭状态。
状态切换逻辑：
- 第一轮操作将所有灯置为打开。
- 第二轮操作将所有偶数编号的灯关闭。
- 从第三轮开始，依次对编号为当前轮数倍数的灯进行状态切换。
最终输出：
- 遍历数组，输出状态为关闭的灯编号。

优点

直观地模拟题目中每一轮的状态切换。
代码逻辑清晰易懂。

问题

时间复杂度较高，为 $O(N^2)$ 。
初始化和部分操作存在冗余。

老师的代码实现

以下是老师提供的代码：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 5010;
char arr[N]; // 下标为0的位置不使用

int main()
{
    int n = 0;
    cin >> n;

    int i = 0;

    // 第一人将所有灯关闭，因为数组开始全是0，直接跳过操作
    for (i = 2; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            if (j % i == 0)
            {
                if (arr[j] == 1)
                    arr[j] = 0;
                else
                    arr[j] = 1;
            }
        }
    }

    for (i = 1; i <= n; i++)
    {
        if (arr[i] == 0)
            cout << i << " ";
    }

    cout << endl;
    return 0;
}

在这里插入图片描述

代码分析

状态切换逻辑：
- 外层循环控制第几轮操作；
- 内层循环处理当前人的操作范围（倍数灯）。
优化建议：
- 条件 if (j % i == 0) 可以去掉，直接跳步循环 j += i。
- 状态切换 if (arr[j] == 1) 部分可以替换为 arr[j] = !arr[j];。

💯优化思考

基于完全平方数的性质，可以直接优化代码，只需输出 1 到 $ \sqrt{N} $ 的平方数：

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;

    for (int i = 1; i * i <= n; i++) {
        cout << i * i;
        if ((i + 1) * (i + 1) <= n) cout << " ";
    }

    return 0;
}