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

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

引用

CSDN

1.

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

枚举算法和暴力算法是算法学习中的基础策略，它们通过逐一尝试所有可能的情况来解决问题。本文将详细介绍这两种算法的核心思想、典型特征，并通过具体例题帮助读者理解它们在实际问题中的应用。

一、枚举算法

定义

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

核心思想

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

二、暴力算法

定义

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

典型特征

进阶应用

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

三、算法关系与应用

关联性对比

枚举算法和暴力算法通常不做严格区分：

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

四、例题

枚举：P1003 [NOIP 2011 提高组] 铺地毯

题目描述

为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有n nn张地毯，编号从
1 11到n nn。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

输入格式

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

输出格式

输出共1 11行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出
-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 11号地毯用实线表示，2 22号地毯用虚线表示，3 33号用双实线表示，覆盖点( 2 , 2 ) (2,2)(2,2)的最上面一张地毯是3 33
号地毯。

【数据范围】
对于30 % 30%30%的数据，有n ≤ 2 n \le 2n≤2。 对于50 % 50%50%的数据，0 ≤ a , b , g , k ≤ 100 0 \le a, b, g, k \le 1000≤a,b,g,k≤100。
对于100 % 100%100%的数据，有0 ≤ n ≤ 1 0 4 0 \le n \le 10^40≤n≤104,0 ≤ a , b , g , k ≤ 10 5 0 \le a, b, g, k \le {10}^50≤a,b,g,k≤105。

题解

#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;
}

暴力：P1328 [NOIP 2014 提高组] 生活大爆炸版石头剪刀布

题目背景

NOIP2014 提高组 D1T1

题目描述

石头剪刀布是常见的猜拳游戏：石头胜剪刀，剪刀胜布，布胜石头。如果两个人出拳一样，则不分胜负。在《生活大爆炸》第二季第 8
集中出现了一种石头剪刀布的升级版游戏。
升级版游戏在传统的石头剪刀布游戏的基础上，增加了两个新手势：
斯波克:《星际迷航》主角之一。
蜥蜴人:《星际迷航》中的反面角色。
这五种手势的胜负关系如表一所示,表中列出的是甲对乙的游戏结果。
现在，小 A 和小 B 尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的，但周期长度不一定相等。例如：如果小 A 以

石头-布-石头-剪刀-蜥蜴人-斯波克
长度为6 66的周期出拳,那么他的出拳序列就是
石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-...
，而如果小 B 以
剪刀-石头-布-斯波克-蜥蜴人
长度为5 55的周期出拳,那么他出拳的序列就是
剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-...
。
已知小 A 和小 B 一共进行N NN次猜拳。每一次赢的人得1 11分，输的得0 00分；平局两人都得0 00分。现请你统计N NN
次猜拳结束之后两人的得分。

输入格式

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

输出格式

输出一行，包含两个整数，以一个空格分隔，分别表示小 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 % 100%100%的数据，0 < N ≤ 200 , 0 < N A ≤ 200 , 0 < N B ≤ 200 0 < N \leq 200, 0 < N_A \leq 200, 0 < N_B \leq 2000<N≤200,0<NA ≤200,0<NB ≤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;
}