OI学习笔记 - 枚举与模拟

发表于 阅读次数： 本文字数： 4.9k 阅读时长 ≈ 9 分钟

OI学习笔记：枚举与模拟算法详解

一、枚举算法

1.1 一维枚举

核心原理

通过单层循环遍历所有候选解，适用于解空间较小的问题。关键优化点在于缩小搜索范围和减少无效检查。

例题：素数判定（洛谷P1075）

问题分析
给定整数n，判断是否为素数（只能被1和自身整除）

优化思考
1. 边界处理：n≤1直接返回非素数
2. 范围优化：若n有因数k，则必存在k≤\(\sqrt n\)，因此遍历范围缩小到[2, \(\sqrt n\)]
3. 奇偶剪枝：除2外所有偶数都不是素数，从3开始检查且步长为2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;

int main() {
    int n; 
    cin >> n;
    if (n <= 1) { 
        cout << "No"; 
        return 0;  // 特判边界
    }
    if (n == 2) {  // 处理唯一偶素数
        cout << "Yes";
        return 0;
    }
    for (int i = 3; i*i <= n; i += 2) {  // 优化：仅检查奇数
        if (n % i == 0) {
            cout << "No";
            return 0;  // 发现因数立即退出
        }
    }
    cout << "Yes";
    return 0;
}

1.2 二维枚举

核心原理

通过双重循环遍历二维组合，常见于矩阵问题。优化重点在于降低维度和重复计算。

例题：最大子矩阵和（洛谷P1585）

问题分析
在n×m矩阵中找出元素和最大的子矩阵

优化策略
1. 暴力解局限：四重循环O(n⁴)无法处理大数据
2. 前缀和降维：
- 预处理二维前缀和数组
- 将子矩阵和计算复杂度降至O(1)
3. 动态规划优化：固定上下边界后，使用Kadane算法求最大子数组和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;

const int N = 105;
int a[N][N], col_sum[N];  // 原始矩阵和列累加数组

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) 
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];
    
    int ans = -0x3f3f3f3f;
    // 枚举上边界
    for (int top = 1; top <= n; ++top) {
        fill(col_sum + 1, col_sum + m + 1, 0);  // 重置列累加
        // 枚举下边界
        for (int bottom = top; bottom <= n; ++bottom) {
            // 动态更新列累加值
            for (int j = 1; j <= m; ++j)
                col_sum[j] += a[bottom][j];
            // Kadane算法求最大子数组和
            int current = 0;
            for (int j = 1; j <= m; ++j) {
                current = max(col_sum[j], current + col_sum[j]);
                ans = max(ans, current);
            }
        }
    }
    cout << ans;
    return 0;
}

1.3 多维枚举

核心原理

通过递归或嵌套循环处理高维组合问题，需注意状态回溯和剪枝策略。

例题：全排列生成（洛谷P1083）

别用next_permutation

问题分析
生成1~n的所有排列组合

先来想想, 如果要生成1~5的所有排列, 可以这样写: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;

//嵌套循环
int main() {
    int a[6];
    for (int i = 1; i <= n; ++i) {
        a[1] = i;
        for (int j = 1; j <= n; ++j) {
            a[2] = j;
            for (int k = 1; k <= n; ++k) {
                a[3] = k;
                for (int l = 1; l <= n; ++l) {
                    a[4] = l;
                    for (int m = 1; m <= n; ++m) {
                        a[5] = m;
                        for (int i = 1; i <= n; ++i)
                            cout << a[i] << " ";
                        cout << endl;
                    }
                }
            }
        }
    }
    return 0;
}

你是否想到了

气功波

这只是5层循环的代码, 若是变成10层循环呢? 20层呢? 或是用户要求的n层呢? 它既不能灵活地修改生成范围, 而且代码也很不美观

优化思路 (拓展) 1. 回溯剪枝：使用used数组标记已选数字
2. 递归深度：通过u参数控制当前处理位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;

int n, a[15];
bool used[15];

void dfs(int u) {
    if (u > n) {  // 终止条件：生成完整排列
        for (int i = 1; i <= n; ++i)
            cout << a[i] << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (!used[i]) {  // 剪枝：未使用的数字
            used[i] = true;
            a[u] = i;
            dfs(u + 1);  // 递归处理下一位置
            used[i] = false;  // 回溯
        }
    }
}

int main() {
    cin >> n;
    dfs(1);  // 从第1位开始生成
    return 0;
}

二、模拟算法

2.1 直接模拟

核心原理

严格按题意步骤执行，关键在于流程分解和资源管理。

例题：接水问题（洛谷P1223）

问题分析
n个人使用m个水龙头接水，求总完成时间

优化思考
1. 贪心策略：每次选择最早空闲的水龙头
2. 时间更新：维护每个水龙头完成时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int taps[105] = {0};  // 记录每个水龙头完成时间
    // 输入接水时间（已排序）
    for (int i = 0; i < n; ++i) {
        int t; 
        cin >> t;
        // 找到最早空闲的水龙头
        int min_tap = 0;
        for (int j = 1; j < m; ++j)
            if (taps[j] < taps[min_tap])
                min_tap = j;
        taps[min_tap] += t;  // 分配任务
    }
    // 找出最大完成时间
    int ans = 0;
    for (int i = 0; i < m; ++i)
        ans = max(ans, taps[i]);
    cout << ans;
    return 0;
}

2.2 状态模拟

核心原理

通过状态转移方程描述系统变化，重点在状态定义和转移逻辑。

例题：红绿灯系统模拟

问题分析
模拟十字路口红绿灯的周期性变化

实现细节
1. 状态编码：用字符串表示各方向信号
2. 倒计时机制：统一管理状态持续时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;

struct TrafficLight {
    string state;  // 状态编码：例如"RRR"全红
    int timer;     // 状态剩余时间
    
    void update() {
        if (timer-- == 0) {  // 倒计时结束
            // 状态转移逻辑
            if (state == "RRR") {
                state = "GGR";  // 东西绿灯
                timer = 30;
            } else if (state == "GGR") {
                state = "RRG";  // 过渡黄灯
                timer = 5;
            } else {
                state = "RRR";  // 恢复初始
                timer = 60;
            }
        }
    }
};

int main() {
    TrafficLight light{"RRR", 60};
    for (int t = 0; t < 200; ++t) {
        light.update();
        cout << "Time " << t << ": " << light.state << endl;
    }
    return 0;
}

2.3 事件驱动模拟

核心原理

按事件发生顺序处理，常用优先队列管理事件流。

例题：银行窗口模拟（洛谷P1853）

问题分析
模拟m个窗口的客户排队过程

优化关键
1. 事件排序：使用小顶堆按时间排序
2. 窗口管理：动态跟踪空闲窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <queue>
using namespace std;

struct Event {
    int time;     // 事件时间
    int type;     // 0-到达事件，1-离开事件
    bool operator<(const Event& e) const {
        return time > e.time;  // 小顶堆
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    priority_queue<Event> pq;
    
    // 初始化到达事件
    while (n--) {
        int t; 
        cin >> t;
        pq.push({t, 0});
    }

    int available = m;  // 空闲窗口数
    int current_time = 0;
    
    while (!pq.empty()) {
        Event e = pq.top();
        pq.pop();
        current_time = e.time;
        
        if (e.type == 0) {  // 处理到达事件
            if (available > 0) {
                available--;
                pq.push({current_time + 10, 1});  // 生成离开事件
            } else {
                pq.push({current_time + 1, 0});  // 重新排队
            }
        } else {  // 处理离开事件
            available++;
        }
    }
    cout << current_time;
    return 0;
}

三、优化策略总结

优化类型 技术手段 复杂度变化 适用场景
数学剪枝 √n边界、奇偶跳跃 O(n)→O(√n) 数值计算问题
前缀和 二维前缀和预处理 O(n⁴)→O(n³) 矩阵区域求和
状态压缩 位运算/字符串编码 O(2ⁿ)→O(n) 组合状态问题
事件调度 优先队列管理 O(n²)→O(n log n) 异步事件处理