[算法学习笔记]1. 枚举与暴力

一、枚举算法

定义

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

2. 核心思想

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

二、暴力算法

1. 定义

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

2. 典型特征

3. 进阶应用

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

三、算法关系与应用

1. 关联性对比

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

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

四、例题

枚举：

P1003 [NOIP 2011 提高组] 铺地毯

题目描述

为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有 $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\le 2$。 对于 $50\%$ 的数据，$0\le a,b,g,k\le 100$。
对于 $100\%$ 的数据，有 $0\le n\le 10^4$, $0\le a,b,g,k\le {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;
}

暴力

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

题目背景

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\le 200,0<N_A\le 200,0<N_B\le 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;
}