NOI C++ 课程体系 / 算法篇 / 第2讲
CSP-J 入门级 · 算法篇 · m4-02

枚举法 与 模拟法

暴力出奇迹,模拟考细节 —— 掌握信息学竞赛中最基础、最常用的两种算法思想,学会优化枚举、精准模拟。

6 大模块 3 种枚举优化 3 类模拟题型 2 个经典案例 12 道分层练习
本讲 · 第 26/56 讲枚举法与模拟法
模块 01

情景导航

用生活中的例子,直觉理解枚举和模拟的本质。

故事忘记密码的行李箱

小明出差回来,发现行李箱的三位密码锁忘了密码。他只记得密码是三个数字(0~9),但具体是哪三个完全不记得了。

怎么办?他决定从 000 试到 999,一个一个试过去。

这就是"枚举法"——逐一尝试所有可能!

幸运的是,当他试到 3-7-2 时,锁"咔嗒"一声开了!🎉

但如果密码是 9-9-9,他要试 1000 次才能打开。有没有更快的方法?如果他记得"三个数字之和是 12",就可以只试满足条件的组合,大大减少尝试次数。

缩小枚举范围 = 优化枚举法!

💡 枚举 vs 模拟

枚举法:把问题的所有可能解逐一列举,逐个检验是否满足条件。核心是"穷举+验证"。

模拟法:用程序忠实重现题目描述的实际过程。核心是"翻译题意"。

两者都是最朴素的算法思想,但在 CSP-J 中占比超过 40%!

①生活类比
🔑

试钥匙 = 枚举

一串钥匙开一把锁,一把一把试直到打开。

→ 线性枚举
📖

翻字典 = 枚举

从第一页翻到最后一页找某个词。

→ 有序枚举
🎲

下棋复盘 = 模拟

按棋谱一步一步重走,还原对局过程。

→ 过程模拟
🏗️

搭积木 = 模拟

按图纸一块一块搭建,重现设计效果。

→ 构造模拟
②核心定义

枚举法(穷举法):根据问题条件,确定解的范围,然后逐一列举该范围内的所有可能解,并用给定条件逐个检验,找出满足条件的解。

模拟法:按照题目描述的实际过程,用程序逐步重现该过程,从而得到结果。不需要特殊算法技巧,关键在于准确理解题意和处理细节。

📌 本讲核心知识地图

板块核心内容对应大纲
枚举法基础确定范围 → 逐一列举 → 逐个检验入门算法:枚举法
枚举法优化缩小范围、减少变量、数学推导枚举法优化策略
模拟法基础读题 → 建模 → 编码 → 验证入门算法:模拟法
模拟法分类过程模拟、图形模拟、字符串模拟模拟法典型题型
③核心口诀
🔑 枚举法三步曲

定范围:解在哪里找?上下界要清楚;
列可能:循环遍历不遗漏,嵌套层数要注意;
验条件:if 判断筛真解,满足才输出!

🔑 枚举优化三招

① 缩范围:利用约束砍掉无效区间
② 减变量:用等式消元,少一层循环
③ 换顺序:先枚举限制多的变量

🔑 模拟法四字诀

读清题意不遗漏,建好模型再动手;
编码忠实翻译题,验证样例保正确!

模块 02

知识探究

深入掌握枚举法的优化技巧和模拟法的分类实战。

1枚举法基础 核心

枚举法是最朴素、最可靠的算法。它的核心框架只有三步:

Step 1:确定范围
  • 解的最小值是多少?
  • 解的最大值是多少?
  • 有哪些已知约束?
  • 范围越小越好!
Step 2:逐一列举
  • 用 for/while 循环遍历
  • 多层循环 = 多维枚举
  • 注意循环变量的边界
  • 不要遗漏也不要重复
Step 3:逐个检验
  • 用 if 判断是否满足条件
  • 满足则记录/输出
  • 可以提前剪枝优化
  • 统计计数或收集结果
C++枚举法通用模板
// 枚举法通用框架
for (变量1 = 下界1; 变量1 <= 上界1; 变量1++) {
    for (变量2 = 下界2; 变量2 <= 上界2; 变量2++) {
        // ... 更多循环(如果需要)

if (满足所有条件) {
            // 找到一个合法解
            记录或输出该解;
        }
    }
}
时间复杂度
O(范围大小 × 检验代价)

枚举法的效率取决于搜索空间的大小。当范围在 10⁶~10⁷ 以内时,通常可以在 1 秒内完成。

2枚举法三大优化策略 提效

纯暴力枚举往往太慢,以下三种优化策略可以让枚举法快几十倍甚至上万倍:

🎯 策略一:缩小枚举范围
  • 利用题目约束条件缩小上下界
  • 例:x+y+z=100 → z=100-x-y,z≥1 → x+y≤99
  • 例:a×b≤n → b≤n/a,不必枚举到n
  • 效果:减少无效枚举,提速显著
🔢 策略二:减少枚举变量
  • 利用等式关系消去一个变量
  • 例:x+y+z=100 → 只枚举x和y,z=100-x-y
  • 三重循环 → 双重循环,提速 n 倍
  • 关键:找到变量间的依赖关系
🔄 策略三:调整枚举顺序
  • 优先枚举约束最多的变量
  • 约束多 → 有效值少 → 内层循环次数少
  • 例:x∈[1,100], y∈[1,x] → 先枚举x
  • 配合剪枝:不满足条件立即 break
📐 策略四(进阶):数学推导
  • 用数学公式直接计算,替代部分枚举
  • 例:求因子 → 只枚举到√n
  • 例:等差数列求和 → 公式代替循环
  • 最高效,但需要数学功底

💡 优化前后对比

问题:百钱买百鸡(公鸡5元,母鸡3元,小鸡1元/3只,100元买100只)

暴力三重循环:100×100×100 = 100万次运算

优化后(消元+缩范围):20×33 = 660次运算

提速 1500 倍!这就是优化的力量。

案例经典案例:百钱买百鸡 必会

公鸡5元/只,母鸡3元/只,小鸡1元/3只。用100元恰好买100只鸡,每种至少买1只,问有多少种买法?

❌ 暴力解法(三重循环)
C++暴力版 ~100万次
int count = 0;  // 买法计数
for(int g=1;g<=100;g++)
  for(int m=1;m<=100;m++)
    for(int x=1;x<=100;x++)
      if(g+m+x==100 &&
         5*g+3*m+x/3==100 &&
         x%3==0)
        count++;
✅ 优化解法(消元+缩范围)
C++优化版 ~660次
// z=100-g-m, 只需枚举g和m
int count = 0;  // 买法计数
for(int g=1;g<=20;g++)     // 5g≤100
  for(int m=1;m<=33;m++){  // 3m≤100
    int x=100-g-m;
    if(x>=1 && x%3==0 &&
       5*g+3*m+x/3==100)
      count++;
  }
运行结果
公鸡4  母鸡18  小鸡78
公鸡8  母鸡11  小鸡81
公鸡12 母鸡4   小鸡84
共 3 种买法

🔍 优化分析

缩范围:公鸡最多 100/5=20 只,母鸡最多 100/3=33 只

减变量:由 g+m+x=100 得 x=100-g-m,消去第三重循环

总运算量:从 100³ = 1,000,000 降至 20×33 = 660

3模拟法基础 核心

模拟法的核心思想:题目怎么说,程序就怎么做。不需要高深算法,但需要极强的读题能力和细节把控。

1
📖
精读题意

逐字逐句理解,标记关键条件和边界

2
🧩
建立模型

用什么数据结构表示状态?如何转移?

3
💻
忠实编码

一步步翻译题意,不加不减不改

4
✅
验证测试

手动模拟小样例,确认逻辑正确

🔑 模拟法的"坑"

① 边界条件:第一个、最后一个、空的情况
② 特殊情况:n=0、n=1、全相同、全不同
③ 数据类型:是否会溢出?用 long long?
④ 方向/索引:数组从0还是1开始?方向数组对不对?
⑤ 输出格式:空格、换行、大小写是否严格匹配?

4模拟法三大类型
🔄 过程模拟
  • 模拟一个动态过程
  • 如约瑟夫环、洗牌、排队
  • 关键:状态转移规则
  • 常用:数组、队列、指针
🖼️ 图形/矩阵模拟
  • 在网格/矩阵上操作
  • 如蛇形填数、螺旋矩阵、俄罗斯方块
  • 关键:方向控制、边界判断
  • 常用:二维数组、方向数组
📝 字符串/表达式模拟
  • 解析文本、表达式、指令
  • 如计算器、密码转换、文本替换
  • 关键:字符分类、状态机
  • 常用:string、栈、ASCII码
类型典型题目核心难点常用技巧
过程模拟约瑟夫环、报数游戏状态转移、循环取模数组/链表、取余运算
图形模拟蛇形矩阵、迷宫行走方向控制、越界判断dx/dy方向数组
字符串模拟简单计算器、编码解码字符解析、优先级栈、isdigit/isalpha
案例经典案例:蛇形矩阵 高频

将 1~n² 按蛇形(S形)填入 n×n 矩阵。例如 n=4 时:

列1列2列3列4
1267
35813
491214
10111516

观察规律:沿对角线方向填充,奇数条对角线从上往下,偶数条从下往上。

C++snake_matrix.cpp — 模拟法
#include <iostream>
using namespace std;

int a[105][105];

int main() {
    int n; cin >> n;
    int num = 1;

// 按对角线编号 d = 2, 3, ..., 2*n 枚举
    for (int d = 2; d <= 2 * n; d++) {
        if (d % 2 == 1) {
            // 奇数对角线:从上往下 (行递增)
            for (int r = 1; r <= d - 1; r++) {
                int c = d - r;
                if (r >= 1 && r <= n && c >= 1 && c <= n)
                    a[r][c] = num++;
            }
        } else {
            // 偶数对角线:从下往上 (行递减)
            for (int r = d - 1; r >= 1; r--) {
                int c = d - r;
                if (r >= 1 && r <= n && c >= 1 && c <= n)
                    a[r][c] = num++;
            }
        }
    }

for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cout << a[i][j] << " ";
        cout << endl;
    }
    return 0;
}
运行结果 (n=4)
1 2 6 7
3 5 8 13
4 9 12 14
10 11 15 16

💡 模拟法的关键技巧

方向数组:用 dx[]={0,1,0,-1}, dy[]={1,0,-1,0} 表示右/下/左/上四个方向

边界检查:每次移动前判断新位置是否在矩阵内且未被填充

手动模拟:写代码前先在纸上画出 n=3 或 n=4 的结果,确认规律正确

模块 03

实践应用

通过分析题和编程题,巩固枚举优化和模拟实战能力。

题1枚举范围分析

题目:找出所有满足 a²+b²=c² 且 a<b<c≤100 的勾股数三元组。请分析如何优化枚举范围,使运算量最小。

提示:利用 a<b<c 和 c≤100 的约束来缩小每个变量的范围。
查看参考答案

优化分析:

• a 的范围:a≥1,且 a² < 100²/3 → a ≤ 57(因为 a

• b 的范围:b > a,且 b² < 100²-a² → b ≤ √(10000-a²)

• c 不需要枚举!c = √(a²+b²),直接计算并检验是否为整数且 ≤100

优化效果:从三重循环 100³=100万次 → 双重循环约 2000次

for(int a=1; a<=57; a++)
  for(int b=a+1; b*b<=10000-a*a; b++){
    int c2 = a*a + b*b;
    int c = (int)sqrt(c2);
    if(c*c==c2 && c<=100)
      cout << a << " " << b << " " << c << endl;
  }
题2模拟过程追踪

题目:有 n=6 个人站成一排,编号 1~6。执行以下操作:每次将队伍最前面的人移到队尾,然后让新的队首出列。重复直到所有人出列。请手动模拟,写出出列顺序。

查看参考答案

模拟过程:

轮次当前队列移到队尾出列者
1[1,2,3,4,5,6]1→尾 [2,3,4,5,6,1]2
2[3,4,5,6,1]3→尾 [4,5,6,1,3]4
3[5,6,1,3]5→尾 [6,1,3,5]6
4[1,3,5]1→尾 [3,5,1]3
5[5,1]5→尾 [1,5]1
6[5]—5

出列顺序:2, 4, 6, 3, 1, 5

这实际上就是经典的"发牌问题",可以用队列(queue)高效模拟。

题3综合实战:回文数枚举

题目:找出 1~10000 之间所有的回文素数(既是回文数又是素数)。请用枚举法实现,并注意优化。

查看参考答案
C++palindrome_prime.cpp
#include <iostream>
using namespace std;

// 判断素数
bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

// 判断回文
bool isPalindrome(int n) {
    int rev = 0, orig = n;
    while (n > 0) {
        rev = rev * 10 + n % 10;
        n /= 10;
    }
    return rev == orig;
}

int main() {
    for (int i = 1; i <= 10000; i++) {
        if (isPalindrome(i) && isPrime(i))
            cout << i << " ";
    }
    cout << endl;
    return 0;
}
运行结果
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929

优化思路:也可以反过来枚举回文数(构造回文而非逐一检验),再判断是否为素数,这样只需枚举约 200 个回文数而非 10000 个数。

模块 04

总结提升

1核心要点总结
知识板块必须记住的核心
枚举法三步定范围 → 列可能 → 验条件
枚举优化缩范围、减变量(消元)、调顺序、数学推导
枚举适用场景解空间小(≤10⁷)、无明显规律、求所有解
模拟法四步读题 → 建模 → 编码 → 验证
模拟三类型过程模拟、图形/矩阵模拟、字符串模拟
模拟法关键细节!边界、特殊值、方向、输出格式
两者关系枚举是"找答案",模拟是"走过程"
2拓展:时间复杂度速判

💡 枚举法能不能过?看数据范围!

CSP-J 复赛每题时限通常为 1秒,约可执行 10⁸ 次简单运算。

数据规模 n可接受的复杂度枚举可行性
n ≤ 20O(2ⁿ) / O(n!)✅ 可以暴力枚举子集/排列
n ≤ 100O(n³)✅ 三重循环可行
n ≤ 1000O(n²)✅ 双重循环可行
n ≤ 10⁵O(n log n)⚠️ 需优化枚举或换算法
n ≤ 10⁶O(n)❌ 只能线性扫描
n ≤ 10⁹O(√n) / O(log n)❌ 必须数学推导

经验法则:看到 n≤100 想枚举,n≤1000 想双重循环,n≤10⁵ 以上就要想更优算法!

3思考与启发

💡 学完本讲,你应该掌握的6项能力

1. 能识别一个问题是否适合用枚举法解决。

2. 能对枚举法进行至少一种优化(缩范围/减变量)。

3. 能根据数据范围快速判断枚举法是否会超时。

4. 能准确理解模拟题的题意,忠实翻译为代码。

5. 能处理模拟中的边界条件和特殊情况。

6. 能在竞赛中灵活运用"不会做就先枚举/模拟"骗分策略。

模块 05

学习检测

5 个初学者最常犯的错误。

易错1

枚举范围没算对导致 TLE

❌ 错误
不看数据范围,直接三重循环 1~10⁵,结果 10¹⁵ 次运算,超时。
✅ 正确
写代码前先估算运算量。10⁸ 以内才安全。超了就优化或换算法。
口诀:先算复杂度,再写循环体!
易错2

枚举漏掉边界值

❌ 错误
for(int i=1; i
✅ 正确
仔细确认边界是 < 还是 <=。用 n=1, n=2 的小样例验证。
口诀:边界用 <= 还是 <,小样例测一下就知!
易错3

模拟题不看特殊数据

❌ 错误
只测了正常样例,没考虑 n=0、n=1、全相同等极端情况。
✅ 正确
写完代码后主动构造边界测试用例:最小值、最大值、空输入、单元素。
口诀:正常过了不算过,边界对了才算对!
易错4

模拟方向搞反

❌ 错误
矩阵模拟中"向右"写成 row++ 而不是 col++,行列搞混。
✅ 正确
使用方向数组 dx/dy 统一管理方向,避免手写 if-else 出错。
口诀:方向用数组,别靠脑子记!
易错5

以为枚举法太简单不屑用

❌ 错误
"枚举太暴力了,我要想高级算法",结果想了半天没想出来,0分。
✅ 正确
竞赛中先拿分再优化!先用枚举/模拟拿 30~60 分,有时间再想正解。
口诀:暴力出奇迹,骗分也是分!
速查枚举法与模拟法速查表
知识点关键结论
枚举三步定范围 → 列可能 → 验条件
优化四招缩范围 / 减变量 / 调顺序 / 数学推导
安全上限1秒 ≈ 10⁸ 次运算
模拟四步读题 → 建模 → 编码 → 验证
模拟三型过程 / 图形矩阵 / 字符串
模拟避坑边界、特殊值、方向、输出格式
竞赛策略不会做 → 先枚举/模拟骗分
📌知识点笔记卡

🔍 枚举法

定范围 → 列可能 → 验条件

暴力但可靠

优化是关键

⚡ 枚举优化

缩范围:利用约束

减变量:等式消元

调顺序:限制多的先枚举

🎮 模拟法

题目怎么说就怎么做

忠实翻译题意

细节决定AC

📋 模拟三型

过程模拟(队列/状态)

图形模拟(方向数组)

字符串模拟(解析)

⏱️ 复杂度速判

n≤100 → O(n³)

n≤1000 → O(n²)

n≤10⁵ → O(nlogn)

🏆 竞赛策略

先暴力拿部分分

有时间再优化

骗分也是本事

课后练习

分层练习作业

A基础 / B提高 / C挑战,难度递增,点击展开答案与解析。

🟢 A组 · 基础(4题)

A1选择题

以下关于枚举法的说法,错误的是()

A. 枚举法一定能找到正确答案
B. 枚举法的时间复杂度一定很高
C. 枚举法可以通过缩小范围来优化
D. 枚举法适用于解空间较小的问题

查看参考答案

答案:B

枚举法的时间复杂度取决于搜索空间大小。如果范围很小(如 n≤20),枚举法非常快。"一定很高"是错误的。

考点:枚举法的运算量由搜索空间(循环层数 × 每层范围)决定,范围小的时候非常快。

易错:把“枚举=暴力=一定超时”当成结论,忽略了数据范围很小时枚举反而是最省事的正解。

A2选择题

"百钱买百鸡"问题中,将三重循环优化为双重循环的关键是()

A. 缩小公鸡的枚举范围
B. 利用 x=100-g-m 消去小鸡变量
C. 改变枚举顺序
D. 使用数学公式

查看参考答案

答案:B

由 g+m+x=100 可得 x=100-g-m,从而消去第三重循环,这是"减少枚举变量"的典型应用。

考点:利用等量关系把第三个变量表示出来,从而消去一层循环,属于“减少枚举变量”。

易错:只想着少写一层循环,却忘了被消掉的变量仍要用 if 校验取值合法(如 ≥1、能被 3 整除)。

A3选择题

以下哪种题型最适合用模拟法解决?

A. 求最短路径
B. 按规则洗牌并输出结果
C. 求最大公约数
D. 求图的连通分量

查看参考答案

答案:B

洗牌是一个明确的过程,按题目描述的步骤一步步执行即可,是典型的过程模拟。A/D 是图论算法,C 是数学算法。

考点:模拟法适用于“过程明确、按题目描述的步骤照做即可”的题型。

易错:把求最短路、图论最值这类需要搜索算法的问题也当成简单模拟,写出的程序既不正确也会超时。

A4编程题

用枚举法找出 1~500 之间所有同时满足以下条件的数:① 是偶数 ② 各位数字之和能被3整除。输出个数。

查看参考答案
#include <iostream>
using namespace std;
int main() {
    int cnt = 0;
    for (int i = 2; i <= 500; i += 2) { // 只枚举偶数
        int sum = 0, t = i;
        while (t > 0) { sum += t % 10; t /= 10; }
        if (sum % 3 == 0) cnt++;
    }
    cout << cnt << endl;
    return 0;
}

答案:83

优化点:循环步长设为2,只枚举偶数,减少一半运算。

思路:外层只枚举偶数(i+=2)省掉一半工作量,内层用 while 循环拆出各位数字并累加数位和。

易错:拆位时先执行 t/=10 再取 t%10,会漏掉个位,导致数位和偏小、计数偏少。

🟡 B组 · 提高(4题)

B1枚举优化

找出所有满足 a+b+c+d=20 且 1≤a≤b≤c≤d≤10 的四元组个数。请写出优化后的枚举代码。

查看参考答案
int cnt = 0;
for(int a=1; a<=5; a++)           // a≤20/4=5
  for(int b=a; b<=10; b++)         // b≥a
    for(int c=b; c<=10; c++){      // c≥b
      int d = 20 - a - b - c;       // 消去d
      if(d>=c && d<=10) cnt++;     // d≥c 且 d≤10
    }
cout << cnt << endl; // 输出 41

优化点:① a≤5(因为4a≤20)② b≥a, c≥b 保证有序 ③ d=20-a-b-c 消去第四重循环 ④ 只需检验 d≥c 且 d≤10

思路:利用 a≤b≤c≤d 排序去重保证不重不漏,a 最多取 20/4=5,d 由等式算出后校验 d≥c 且 d≤10。

易错:不加 a≤b≤c≤d 的限制,会把同一组数重复计数多次;或漏掉 d≤10 的上界校验,把不合法解也算进去。

B2模拟法

模拟"报数游戏":n个人围成一圈,从1号开始报数,报到m的人出局,下一个人重新从1开始报。求最后剩下的人的编号。(n=10, m=3)

查看参考答案
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n=10, m=3;
    vector<int> v;
    for(int i=1;i<=n;i++) v.push_back(i);
    int idx = 0;
    while(v.size() > 1) {
        idx = (idx + m - 1) % v.size();
        v.erase(v.begin() + idx);
    }
    cout << v[0] << endl; // 输出 4
    return 0;
}

答案:4。这就是经典的约瑟夫问题,用 vector + erase 模拟即可。

思路:用 vector 模拟圆圈,出局位置用 idx=(idx+m-1)%v.size() 递推,删除元素后下标恰好指向下一个人。

易错:写成 idx=(idx+m)%v.size() 会多报一个人;或删除元素后又额外 ++idx,跳过一个未报数的人。

B3枚举+数学

找出 1~1000 中所有"完全数"(等于其所有真因子之和的数,如 6=1+2+3)。用枚举法实现,并分析如何优化因子枚举。

查看参考答案
#include <iostream>
using namespace std;
int main() {
    for(int n=2; n<=1000; n++){
        int sum = 1; // 1总是因子
        for(int i=2; i*i<=n; i++){ // 只枚举到√n
            if(n%i==0){
                sum += i;
                if(i != n/i) sum += n/i; // 配对因子
            }
        }
        if(sum == n) cout << n << " ";
    }
    cout << endl;
    return 0;
}
运行结果
6 28 496

优化关键:因子成对出现,只需枚举到 √n。若 i 是因子,则 n/i 也是因子。将 O(n) 降为 O(√n)。

思路:枚举每个 n,只用 2~√n 试除,找到因子 i 时同时把配对因子 n/i 也累加进因子和。

易错:漏加“1 总是因子”这一项;或当 n 是完全平方数时把 √n 重复加了两次。

B4图形模拟

编写程序,输入 n,输出 n 层的数字金字塔(n=5 时如下所示):

    1
   121
  12321
 1234321
123454321
查看参考答案
#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n-i; j++) cout << " ";  // 前导空格
        for(int j=1; j<=i; j++) cout << j;         // 升序
        for(int j=i-1; j>=1; j--) cout << j;     // 降序
        cout << endl;
    }
    return 0;
}

这是典型的图形模拟题,关键是分析每行的结构:空格数 + 升序数字 + 降序数字。

思路:每行拆成“前导空格 + 升序 1..i + 降序 i-1..1”三段依次输出。

易错:前导空格数写成 i 而不是 n-i,输出的金字塔会向左倾倒,形状完全不对。

🔴 C组 · 挑战(4题)

C1初赛真题

下列关于枚举法的叙述中,正确的是()

A. 枚举法只能用于求解计数问题
B. 枚举法的时间复杂度一定是 O(n²)
C. 枚举法可以通过减少枚举变量来降低时间复杂度
D. 枚举法不适合用于竞赛

查看参考答案

答案:C

A错(枚举可用于求最值、存在性等),B错(复杂度取决于循环层数和范围),D错(枚举是竞赛重要策略)。C正确,如三重循环消元变双重循环。

考点:枚举法可用于求最值、计数、判断存在性等多种题型,复杂度由循环层数和范围共同决定。

易错:断言“枚举只能用来计数”或“枚举一定比 DP、贪心差”,忽略了它适用范围广这一优点。

C2初赛真题

某程序中,外层循环执行 n 次,内层循环每次执行 i 次(i 从 1 到 n)。该程序的总运算次数约为()

A. O(n)   B. O(n log n)   C. O(n²)   D. O(n³)

查看参考答案

答案:C. O(n²)

总运算次数 = 1+2+3+…+n = n(n+1)/2 ≈ n²/2 = O(n²)。这是最常见的双重循环模式。

考点:运算次数是等差数列 1+2+…+n,按大 O 记法只保留最高阶项。

易错:把 n(n+1)/2 的系数保留下来写成 O(n²/2),大 O 记号应当省略常数系数。

C3综合枚举

CSP-J 真题改编:给定正整数 n(n≤10⁶),求有多少对正整数 (a,b) 满足 a×b=n 且 a≤b。要求时间复杂度不超过 O(√n)。

查看参考答案
#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int n; cin >> n;
    int cnt = 0;
    for(int a=1; (long long)a*a<=n; a++){
        if(n % a == 0){
            int b = n / a;
            if(a <= b) cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

关键优化:因子成对出现,a≤√n 时 b=n/a≥√n,所以只需枚举 a 从 1 到 √n。时间复杂度 O(√n),n=10⁶ 时仅需 1000 次运算。

思路:只需枚举到 √n:每找到一个约数 a 就同时得到配对约数 b=n/a,再判断 a≤b 即可按大小去重。

易错:循环上界写成 n 而不是 √n,复杂度退化成 O(n) 直接超时;或漏掉 a≤b 的判断,每对约数被统计两次。

C4综合模拟

模拟"螺旋矩阵":将 1~n² 按顺时针螺旋方向填入 n×n 矩阵。输入 n=4,输出矩阵。

查看参考答案
#include <iostream>
using namespace std;
int a[105][105];
int dx[]={0,1,0,-1}; // 右↓左↑
int dy[]={1,0,-1,0};
int main() {
    int n; cin >> n;
    int x=1, y=1, dir=0;
    for(int num=1; num<=n*n; num++){
        a[x][y] = num;
        int nx = x + dx[dir], ny = y + dy[dir];
        if(nx<1||nx>n||ny<1||ny>n||a[nx][ny]!=0)
            dir = (dir+1) % 4; // 转向
        x += dx[dir]; y += dy[dir];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) cout << a[i][j] << " ";
        cout << endl;
    }
    return 0;
}
运行结果 (n=4)
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7

核心技巧:使用方向数组 dx/dy 管理四个方向。碰到边界或已填格子时右转(dir=(dir+1)%4)。这是图形模拟的标准套路。

思路:用方向数组 (dx,dy) 配合“走到边界或下一格已填过就右转”的规则,按 1~n² 依次填数。

易错:只判断越界而忘了判断“下一格是否已填过”,转弯不及时会导致已填的数字被覆盖。