算法学习笔记：枚举与暴力

算法学习笔记：枚举与暴力

引用

CSDN

1.

https://m.blog.csdn.net/qq_42995393/article/details/145712158

枚举与暴力算法是算法学习中的基础策略，它们通过尝试所有可能的情况来解决问题。本文将详细介绍这两种算法的核心思想、典型特征，并通过两道具体的编程竞赛题目来展示它们的应用。

一、枚举算法

定义

枚举是基于已有知识来猜测答案的问题求解策略。即在已知可能答案的范围内，通过逐一尝试寻找符合条件的解。

核心思想

• 穷举验证：对可能答案集合中的每一个元素进行尝试
• 终止条件：找到满足条件的解，或遍历完所有可能性
• 适用场景：答案范围明确且有限的场景（如密码破解、组合优化）

二、暴力算法

定义

暴力算法直接模拟题目要求的操作来求解问题，强调严格遵循题目描述的步骤实现。

典型特征

进阶应用

• 剪枝优化：在暴力基础上增加条件判断减少无效尝试
• 预处理加速：提前计算并存储中间结果（如素数表）
• 分层暴力：对不同数据规模采用不同策略（小规模全遍历，大规模抽样）

三、算法关系与应用

关联性对比

枚举算法和暴力算法在实际应用中通常不做严格区分：

• 它们都属于比较基础和直接的算法策略，都是通过不断尝试所有可能情况来求解问题。
• 有时候枚举可以被看作是暴力算法的一种具体实现方式。通过合理运用这两种算法，我们可以解决很多基础的算法问题。

四、例题

枚举：铺地毯

题目描述

为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有n张地毯，编号从1到n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。

地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

输入格式

输入共n + 2行。
第一行，一个整数n，表示总共有n张地毯。
接下来的n行中，第i + 1行表示编号i的地毯的信息，包含四个整数a, b, g, k，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标(a, b)以及地毯在x轴和y轴方向的长度。
第n + 2行包含两个整数x和y，表示所求的地面的点的坐标(x, y)。

输出格式

输出共1行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。

输入输出样例 #1

输入 #1

3
1 0 2 3
0 2 3 3
2 1 3 3
2 2

输出 #1

3

输入输出样例 #2

输入 #2

3
1 0 2 3
0 2 3 3
2 1 3 3
4 5

输出 #2

-1

说明/提示

【样例解释 1】
如下图，1号地毯用实线表示，2号地毯用虚线表示，3号用双实线表示，覆盖点(2, 2)的最上面一张地毯是3号地毯。

【数据范围】
对于30%的数据，有n ≤ 2。
对于50%的数据，0 ≤ a, b, g, k ≤ 100。
对于100%的数据，有0 ≤ n ≤ 10^4,0 ≤ a, b, g, k ≤ 10^5。

题解

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

// 全局变量定义 
int n, ans;                // n: 矩形数量，ans: 最终找到的矩形编号 
int a[10005], b[10005];    // 矩形左下角坐标数组（a:x坐标，b:y坐标）
int x[10005], y[10005];    // 矩形尺寸数组（x:宽度，y:高度）
int sx, sy;                // 目标点坐标 

int main() {
    // 输入处理 
    scanf("%d", &n);
    ans = -1;  // 初始化未找到状态 
    for (int i = 1; i <= n; i++) {
        // 按顺序读取每个矩形的参数：
        // a[i]左下角x坐标，b[i]左下角y坐标 
        // x[i]矩形宽度，y[i]矩形高度 
        scanf("%d %d %d %d", &a[i], &b[i], &x[i], &y[i]);
    }
    // 读取目标点坐标 
    scanf("%d %d", &sx, &sy);

    // 逆向枚举所有矩形（关键设计）
    // 从最后输入的矩形开始检查，确保找到的是最上层覆盖的矩形 
    for (int i = n; i >= 1; i--) {
        // 坐标范围判断逻辑：
        // x方向：sx ∈ [a[i], a[i]+x[i]) 左闭右开区间 
        // y方向：sy ∈ [b[i], b[i]+y[i]] 闭合区间 
        // 注意坐标系设定：y轴方向可能向下增长（根据题目具体设定）
        if (sx >= a[i] && sx < a[i] + x[i] && 
            sy >= b[i] && sy <= b[i] + y[i]) {
            ans = i;  // 记录当前符合条件的最大编号 
            break;    // 找到后立即终止循环（逆向查找特性）
        }
    }

    // 输出结果（-1表示未被任何矩形覆盖）
    printf("%d\n", ans);
    return 0;
}

暴力：生活大爆炸版石头剪刀布

题目背景

NOIP2014 提高组 D1T1

题目描述

石头剪刀布是常见的猜拳游戏：石头胜剪刀，剪刀胜布，布胜石头。如果两个人出拳一样，则不分胜负。在《生活大爆炸》第二季第8集中出现了一种石头剪刀布的升级版游戏。

升级版游戏在传统的石头剪刀布游戏的基础上，增加了两个新手势：

• 斯波克：《星际迷航》主角之一。
• 蜥蜴人：《星际迷航》中的反面角色。

这五种手势的胜负关系如表一所示,表中列出的是甲对乙的游戏结果。现在，小A和小B尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的，但周期长度不一定相等。例如：如果小A以

石头-布-石头-剪刀-蜥蜴人-斯波克
长度为6的周期出拳,那么他的出拳序列就是
石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-...，
而如果小B以
剪刀-石头-布-斯波克-蜥蜴人
长度为5的周期出拳,那么他出拳的序列就是
剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-...。

已知小A和小B一共进行N次猜拳。每一次赢的人得1分，输的得0分；平局两人都得0分。现请你统计N次猜拳结束之后两人的得分。

输入格式

第一行包含三个整数：N, N_A, N_B，分别表示共进行N次猜拳、小A出拳的周期长度，小B出拳的周期长度。数与数之间以一个空格分隔。
第二行包含N_A个整数,表示小A出拳的规律,第三行包含N_B个整数，表示小B出拳的规律。其中，0表示剪刀，1表示石头，2表示布，3表示蜥蜴人，4表示斯波克。数与数之间以一个空格分隔。

输出格式

输出一行，包含两个整数，以一个空格分隔，分别表示小A、小B的得分。

输入输出样例 #1

输入 #1

10 5 6
0 1 2 3 4
0 3 4 2 1 0

输出 #1

6 2

输入输出样例 #2

输入 #2

9 5 5
0 1 2 3 4
1 0 3 2 4

输出 #2

4 4

说明/提示

对于100%的数据，0 < N ≤ 200, 0 < N_A ≤ 200, 0 < N_B ≤ 200。

题解

#include<iostream>
using namespace std;
// 胜负关系矩阵（A手势 vs B手势的胜负结果）
// 矩阵行索引表示A的手势类型（0-4），列索引表示B的手势类型（0-4）
// 值1表示A胜，0表示B胜（根据题目具体规则可能需要调整解释）
const int f[5][5] = {
    {0, 0, 1, 1, 0},  // A出0时的胜负情况 
    {1, 0, 0, 1, 0},  // A出1时的胜负情况 
    {0, 1, 0, 0, 1},  // A出2时的胜负情况 
    {0, 0, 1, 0, 1},  // A出3时的胜负情况 
    {1, 1, 0, 0, 0}   // A出4时的胜负情况 
};
int n,na,nb,a[205],b[205],x,y,an,bn;
int main()
{
    cin>>n>>na>>nb;
    for(int i=0;i<na;i++)
    cin>>a[i];
    for(int i=0;i<nb;i++)
    cin>>b[i];
    // 对战模拟
    for(int i=1;i<=n;i++)
    {
        an+=f[a[x]][b[y]];
        bn+=f[b[y]][a[x]];
        x=(x+1)%na;
        y=(y+1)%nb;	
    }
    cout<<an<<' '<<bn;
    return 0;
}