Lesson 1 - 枚举算法

算法思想

枚举算法其实就是一种“试一试”的方法。想象你在玩一个找宝藏的游戏，宝藏藏在某个小格子里，但是你不知道在哪一格。你可以一个格子一个格子去试，一直试到找到宝藏为止，这就是枚举算法的基本思想。

枚举算法的步骤

1. 确定要尝试的范围：先想清楚，宝藏可能会在哪些格子里，比如一共有 10 个格子，那就从第 1 格到第 10 格一个个去试。
2. 一个个地去试：从第 1 格开始，检查一下是不是宝藏。如果不是，就试下一格。
3. 找到目标，结束搜索：一旦找到宝藏，立即停下来，不需要再继续试其他格子。
4. 总结答案：找到宝藏后，把结果记录下来，这样你就知道宝藏在哪了。

例子说明： 假设我们要找的是 1 到 100 之间能被 7 整除的所有数字。枚举算法可以帮助我们快速找到这些数字。

解题步骤：

1. 确定范围：数字在 1 到 100 之间，所以我们要从 1 开始试到 100 。
2. 一个个尝试：对于每一个数字，检查一下能不能被 7 整除（判断条件是数 % 7 == 0）。
3. 找到符合条件的记录下来：如果某个数字能被 7 整除，就把它记录下来。
4. 最终输出：把所有符合条件的数字输出，这样我们就找到了所有满足条件的数字。

代码示例：

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 从1到100枚举每一个数字
    for (int i = 1; i <= 100; i++) {
        // 检查这个数字能不能被7整除
        if (i % 7 == 0) {
            // 如果能被7整除，就输出这个数字
            cout << i << " ";
        }
    }
    cout << endl;
    return 0;
}

思路总结

枚举算法就是从头到尾“一个个地去试”，只要按步骤去检查每个可能的答案，最后一定会找到正确的答案。

例题

2837 寻找水仙花数

提示

水仙花数是一个三位整数，其每一位的立方和等于这个整数本身。例如，153 是水仙花数，因为 $1^3+5^3+3^3=153$。我们的任务是找到所有这样的三位数。

问题分析

1. 定义范围：水仙花数的范围是三位数，即从 100 到 999。

2. 逐个检查：对于每个三位数 $abc$，我们将其拆分为百位 $a$、十位 $b$、个位 $c$，然后计算 $a^3+b^3+c^3$。

3. 条件判断：如果 $a^3+b^3+c^3$ 等于该数本身，则输出该数。

4. 输出格式：所有的水仙花数用空格隔开输出。

代码实现

#include<bits/stdc++.h>
using namespace std;

int main() {
    for (int num = 100; num < 1000; num++) { // 遍历三位数
        int a = num / 100; // 百位
        int b = (num / 10) % 10; // 十位
        int c = num % 10; // 个位

        // 判断是否为水仙花数
        if (a * a * a + b * b * b + c * c * c == num) {
            cout << num << " "; // 输出水仙花数
        }
    }
    return 0;
}

2838 四叶玫瑰数

提示

四叶玫瑰数是指四位整数 $abcd$ 满足 $a^4+b^4+c^4+d^4=abcd$。例如，1634 是一个四叶玫瑰数，因为 $1^4+6^4+3^4+4^4=1634$。我们的目标是找到所有这样的四位数。

问题分析

1. 定义范围：四叶玫瑰数的范围是从 1000 到 9999。

2. 逐个检查：对于每个四位数 $abcd$，我们将其拆分为千位 $a$、百位 $b$、十位 $c$、个位 $d$，然后计算 $a^4+b^4+c^4+d^4$。

3. 条件判断：如果 $a^4+b^4+c^4+d^4$ 等于该数本身，则输出该数。

4. 输出格式：所有的四叶玫瑰数用空格隔开输出。

代码实现

#include<bits/stdc++.h>
using namespace std;

int main() {
    for (int num = 1000; num < 10000; num++) { // 遍历四位数
        int a = num / 1000; // 千位
        int b = (num / 100) % 10; // 百位
        int c = (num / 10) % 10; // 十位
        int d = num % 10; // 个位

        // 判断是否为四叶玫瑰数
        if (a * a * a * a + b * b * b * b + c * c * c * c + d * d * d * d == num) {
            cout << num << " "; // 输出四叶玫瑰数
        }
    }
    return 0;
}

1252 不高兴的津津

提示

津津每天的学习时间是由上课时间和其他学习活动的时间组成的。若某一天的总学习时间超过 8 小时，津津就会感到不高兴。我们需要检查每一天的总时间，找出哪一天她最不高兴，或者如果每一天的时间都在 8 小时以内，输出 0。

问题分析

1. 输入数据：我们有 7 天的时间安排，每天记录学校上课时间和其他活动时间。

2. 计算总时间：对每一天计算总学习时间，公式为：

   $$\text{总时间}=\text{学校上课时间}+\text{其他学习时间}$$

3. 判断不高兴：若总时间超过 8 小时，记录下该天的不高兴程度（总时间 - 8），并比较不高兴程度，找出最大值。

4. 输出结果：如果没有超过 8 小时的天数，输出 0；否则输出不高兴程度最大的那一天。

代码实现

#include<bits/stdc++.h>
using namespace std;

int main() {
    int max_unhappy = 0; // 最不高兴的程度
    int day = 0; // 不高兴的日子
    for (int i = 1; i <= 7; i++) {
        int school_time, extra_time;
        cin >> school_time >> extra_time; // 输入上课时间和其他时间
        int total_time = school_time + extra_time; // 计算总时间
        if (total_time > 8) {
            int unhappy_level = total_time - 8; // 计算不高兴程度
            // 检查是否是更高的不高兴程度
            if (unhappy_level > max_unhappy) {
                max_unhappy = unhappy_level;
                day = i; // 记录不高兴的日子
            }
        }
    }
    cout << (day ? day : 0); // 输出结果，0 表示没有不高兴的日子
    return 0;
}

2842 安放地雷 1

提示

在一个 n*n 的矩阵中，地雷的位置用 0 表示，敌人的位置用 1 表示，而用 2 表示该位置上没有敌人。我们的任务是找到地雷的具体位置并输出其行和列的索引。

解题思路

1. 输入矩阵：读取矩阵的大小 n，以及 n*n 的矩阵元素。

2. 寻找地雷：遍历整个矩阵，找到值为 0 的元素，记录其位置。

3. 输出位置：输出找到的地雷位置的行列索引，注意行和列的输出格式。

代码实现

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n; // 输入矩阵的大小
    int x, y; // 地雷的位置
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int value;
            cin >> value; // 输入矩阵元素
            if (value == 0) { // 找到地雷
                x = i + 1; // 行索引（从1开始）
                y = j + 1; // 列索引（从1开始）
            }
        }
    }
    cout << x << ' ' << y; // 输出地雷位置
    return 0;
}

2844 安放地雷 2

提示

在一个 n*n 的矩阵中，地雷的位置用 0 表示，敌人的位置用 1 表示，而用 2 表示该位置上没有敌人。我们的任务是找到地雷的具体位置，并计算可以清除的敌人数量，即地雷所在行和列中的敌人总数。

解题思路

1. 输入矩阵：读取矩阵的大小 n，以及 n*n 的矩阵元素。

2. 寻找地雷：遍历整个矩阵，找到值为 0 的元素，记录其行列索引。

3. 计算敌人数量：统计地雷所在行和列中的敌人数量，注意同一位置的敌人只计算一次。

4. 输出数量：输出可以清除的敌人数量。

代码实现

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n; // 输入矩阵的大小
    int x, y; // 地雷的位置
    int matrix[100][100]; // 使用二维数组存储矩阵

    // 输入矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
            if (matrix[i][j] == 0) { // 找到地雷
                x = i; // 行索引
                y = j; // 列索引
            }
        }
    }

    int count = 0;

    // 计算地雷所在行的敌人数量
    for (int j = 0; j < n; j++) {
        if (matrix[x][j] == 1) {
            count++;
        }
    }

    // 计算地雷所在列的敌人数量
    for (int i = 0; i < n; i++) {
        if (matrix[i][y] == 1) {
            count++;
        }
    }

    cout << count; // 输出可以清除的敌人数量
    return 0;
}