各位未来的算法大佬们，大家好！👋 是不是刚听说 OI（信息学奥林匹克竞赛）时，以为是什么歪门邪道？其实非也非也，这玩意儿全称是信息学奥林匹克竞赛，说白了就是用代码解决数学和逻辑问题的 “脑力奥运会”🏆。今天咱就从最基础的语法开始，一步步爬向算法入门的门槛，保证全程无废话、多笑点、代码接地气，变量名绝不搞 “bad_apples [apple_number]” 这种花里胡哨的操作，主打一个 “b [n] 就能解决” 的朴实无华～

第一章：OI 入门先搭台 —— 环境配置像开黑前装游戏

在敲代码前，得先有个 “战场” 吧？就像打游戏要先装客户端，OIer 的第一站就是配置编程环境。目前主流的有 Dev-C++、Code::Blocks、VS Code，新手建议从 Dev-C++ 入手，轻便如 “手机小游戏”📱，不像 VS Code 那样需要装一堆插件，省事儿！

1.1 安装 Dev-C++：三步搞定，比泡方便面还快

1. 百度搜 “Dev-C++ 官方下载”，认准带 “Bloodshed” 标识的官网（别点到广告！❌）；

2. 下载后双击安装，一路点 “Next”，路径选个好记的（比如 D 盘根目录，别藏太深找不到）；

3. 安装完成后打开，看到 “File -> New -> Source File”，恭喜！你的代码 “草稿纸” 准备好了📝。

1.2 第一个程序：“Hello World”——OI 界的 “见面礼”

不管学啥编程语言，第一个程序必然是跟世界打个招呼，这是行业 “潜规则”😎。来，跟着敲：

#include <iostream>

using namespace std;

int main()

{

   cout << "Hello OI! I'm coming!" << endl;

   return 0;

}

代码解读（敲黑板！📌）：

• #include <iostream>：相当于 “请个秘书”，iostream是输入输出的 “工具箱”，没有它就没法打印文字、读入数据；

• using namespace std;：“秘书办公室地址”，std是标准命名空间，不写这个的话，每次用cout都得写成std::cout，麻烦得很；

• int main()：程序的 “正门”，所有代码都得从这儿进，int表示这个门 “出来时要带个整数”；

• cout << ... << endl;：“喇叭” 功能，把引号里的内容喊出来，endl是 “换行键”，喊完换一行；

• return 0;：从正门出来时带的 “凭证”，0 表示 “程序跑得很顺利，没出岔子”。

运行程序：

点 Dev-C++ 上的 “运行” 按钮（绿色三角，像播放键▶️），会弹出个黑框框，里面显示 “Hello OI! I'm coming!”，恭喜！你成功写出了第一行 OI 代码，比 90% 的路人强了～

第二章：C++ 语法基础 —— 代码的 “拼音和汉字”

如果把程序比作文章，语法就是 “拼音和汉字”，得先学会怎么组词造句，才能写长篇大论。咱从 “变量”“数据类型” 这些最基础的说起，保证比学英语语法简单！

2.1 变量：给数据 “起名字”，别搞复杂的！

变量就是 “装东西的盒子”📦，比如装年龄、装分数、装数量。起名字有讲究：

• 只能用字母、数字、下划线，且不能以数字开头（比如a1行，1a不行）；

• 不能用 C++ 的 “关键字”（比如int cout这些已经有特殊含义的词）；

• 别搞 “apple_number” 这种长名字，a b x y arr b[n]就行，OIer 讲究效率！

示例：定义变量

int a;          // 装整数（比如1、-5、100），像“小盒子”

double b;       // 装小数（比如3.14、0.618），像“大盒子”

char c;         // 装单个字符（比如'a'、'A'、'1'），像“迷你盒子”

bool d;         // 装布尔值，只有true（真，相当于1）和false（假，相当于0），像“开关盒子”

变量初始化：“盒子刚买回来先装东西”

定义变量后最好马上赋值，不然里面可能是 “垃圾数据”（就像新买的盒子里有灰尘）：

int a = 10;

double b = 3.14159;

char c = 'O';

bool d = true;

2.2 数据类型：不同 “盒子” 装不同 “东西”

刚才提到的int double就是数据类型，相当于 “盒子的尺寸”，装错了会出问题（比如把西瓜塞进火柴盒🚫）。常见的有这些：

数据类型	作用	范围（大概）	示例
int	存储整数	-20 亿～20 亿	10、-500
long long	存储大整数	-9e18 ~ 9e18	12345678901234
double	存储小数（双精度）	约 15 位小数	3.14、0.0001
float	存储小数（单精度）	约 6 位小数	1.23f（要加 f）
char	存储单个字符	ASCII 码范围	'A'、'5'、'+'
bool	存储真假	true/false	true

避坑提醒！⚠️

• 整数除法会 “丢小数”：比如5/2结果是 2，不是 2.5！要想得到小数，得把其中一个数改成小数，比如5.0/2或5/2.0；

• long long变量赋值要加LL：比如long long x = 12345678901234LL;，不然可能 “装不下” 导致出错；

• char类型用单引号：'a'是字符，"a"是字符串，别搞混！

2.3 运算符：给数据 “做运算”，像数学题一样

运算符就是 “计算器功能”🧮，加加减减乘乘除除都靠它。

算术运算符：最常用的 “加减乘除余”

int x = 10, y = 3;

cout << x + y << endl;  // 加，输出13

cout << x - y << endl;  // 减，输出7

cout << x * y << endl;  // 乘，输出30

cout << x / y << endl;  // 除，输出3（整数除法）

cout << x % y << endl;  // 取余，输出1（10除以3余1）

赋值运算符：“把右边的东西装进左边的盒子”

int a = 5;

a += 3;  // 相当于a = a + 3，结果a=8

a -= 2;  // 相当于a = a - 2，结果a=6

a *= 4;  // 相当于a = a * 4，结果a=24

a /= 6;  // 相当于a = a / 6，结果a=4

a %= 3;  // 相当于a = a % 3，结果a=1

比较运算符：“比大小”，结果是 bool 值

int x = 5, y = 8;

cout << (x > y) << endl;  // 大于，false（输出0）

cout << (x < y) << endl;  // 小于，true（输出1）

cout << (x == y) << endl; // 等于，false（输出0）—— 注意是两个等号！一个等号是赋值

cout << (x != y) << endl; // 不等于，true（输出1）

cout << (x >= y) << endl; // 大于等于，false（输出0）

cout << (x <= y) << endl; // 小于等于，true（输出1）

逻辑运算符：“与或非”，处理 “条件判断”

bool a = true, b = false;

cout << (a && b) << endl;  // 与：都真才真，输出0

cout << (a || b) << endl;  // 或：有真就真，输出1

cout << (!a) << endl;      // 非：取反，输出0

2.4 输入输出：和程序 “对话”，传递信息

程序不光要 “说话”（输出），还得 “听话”（输入），不然就是 “自说自话的哑巴”🗣️。输入用cin，输出用cout，记住 “箭头方向”：cin是 “数据流进变量”（>>），cout是 “数据流出屏幕”（<<）。

基本输入输出示例

#include <iostream>

using namespace std;

int main()

{

   int a;

   double b;

   char c;

   cout << "请输入一个整数、一个小数、一个字符：" << endl;

   cin >> a >> b >> c;  // 可以连续输入，用空格或回车分隔

   cout << "你输入的整数是：" << a << endl;

   cout << "你输入的小数是：" << b << endl;

   cout << "你输入的字符是：" << c << endl;

   return 0;

}

输入输出格式控制（进阶小技巧）

有时候输出小数要控制位数，比如保留 2 位小数，这时候需要 “请个专门的秘书”——iomanip库：

#include <iostream>

#include <iomanip>  // 格式控制库

using namespace std;

int main()

{

   double pi = 3.1415926535;

   cout << fixed << setprecision(2) << pi << endl;  // 保留2位小数，输出3.14

   cout << setprecision(6) << pi << endl;           // 保留6位小数，输出3.141593

   return 0;

}

2.5 分支结构：程序 “选路走”，像岔路口一样

生活中总要做选择：“如果下雨就带伞，否则不带”；程序里也一样，靠分支结构实现 “选路走”。主要有if和switch两种。

if 语句：“如果… 就… 否则…”

#include <iostream>

using namespace std;

int main()

{

   int score;

   cout << "请输入成绩：" << endl;

   cin >> score;

  

   if (score >= 90)

   {

       cout << "优秀！🎉" << endl;

   }

   else if (score >= 80)

   {

       cout << "良好！👍" << endl;

   }

   else if (score >= 60)

   {

       cout << "及格！🙂" << endl;

   }

   else

   {

       cout << "不及格，要加油！💪" << endl;

   }

   return 0;

}

避坑提醒！⚠️

• if后面的括号里是 “条件”，必须是 bool 值或能转成 bool 值的表达式（比如score >= 90）；

• 不要漏写大括号！如果if后面只有一句话，可以不写，但多句话必须写，不然程序会 “认错亲”（只执行第一句）；

• else总是跟着最近的未配对的if，别搞混层级。

switch 语句：“多选一”，像选择题一样

当条件是 “等于某个固定值” 时，用switch比if-else更清晰：

#include <iostream>

using namespace std;

int main()

{

   int day;

   cout << "请输入星期几（1-7）：" << endl;

   cin >> day;

  

   switch (day)

   {

       case 1:

           cout << "星期一，打工人的开始😩" << endl;

           break;  // 必须加break，不然会“串台”执行下一个case

       case 2:

           cout << "星期二，还没缓过来😮‍💨" << endl;

           break;

       case 3:

           cout << "星期三，周中了，加油💪" << endl;

           break;

       case 4:

           cout << "星期四，快周末了✨" << endl;

           break;

       case 5:

           cout << "星期五，狂喜！🎉" << endl;

           break;

       case 6:

           cout << "星期六，摆烂日😴" << endl;

           break;

       case 7:

           cout << "星期日，emo了😔" << endl;

           break;

       default:

           cout << "输入错误！😵" << endl;  // 没有匹配的case时执行

   }

   return 0;

}

switch 避坑！⚠️

• case后面必须是 “常量表达式”（比如 1、'A'，不能是变量）；

• 每个case后面一定要加break，不然会从匹配的case开始，一直执行到break或结束，比如输入 1 会输出所有 case 的内容，惨不忍睹；

• default可选，但加上能处理 “输入错误” 的情况，更严谨。

2.6 循环结构：程序 “重复做”，像复读机一样

如果要让程序 “打印 100 遍‘我爱 OI’”，总不能写 100 行cout吧？这时候就需要循环结构，相当于 “复读机开关”🔁。主要有for、while、do-while三种。

for 循环：“固定次数” 的循环，最常用！

格式：for (初始化; 条件; 更新)，像 “设定复读次数：从第 1 次开始，复读到 100 次，每次加 1”。

示例 1：打印 1 到 10

#include <iostream>

using namespace std;

int main()

{

   for (int i = 1; i <= 10; i++)

   {

       cout << i << " ";

   }

   // 输出：1 2 3 4 5 6 7 8 9 10

   return 0;

}

示例 2：计算 1 到 100 的和

#include <iostream>

using namespace std;

int main()

{

   int sum = 0;

   for (int i = 1; i <= 100; i++)

   {

       sum += i;  // 相当于sum = sum + i

   }

   cout << "1+2+...+100=" << sum << endl;  // 输出5050

   return 0;

}

while 循环：“满足条件就循环”，不知道次数时用

格式：while (条件)，像 “只要没吃饱，就一直吃”。

示例：计算 1 到 n 的和，直到和超过 1000

#include <iostream>

using namespace std;

int main()

{

   int sum = 0, n = 0;

   while (sum <= 1000)

   {

       n++;

       sum += n;

   }

   cout << "当n=" << n << "时，和超过1000，此时和为" << sum << endl;

   return 0;

}

do-while 循环：“先做一次，再判断条件”

格式：do { ... } while (条件);，和while的区别是 “先执行一次循环体，再判断”，像 “先吃一口，再看饱没饱”。

示例：至少打印一次 “Hello”

#include <iostream>

using namespace std;

int main()

{

   int x = 0;

   do

   {

       cout << "Hello" << endl;

       x++;

   } while (x > 1);  // 条件不满足，但还是执行了一次

   // 输出：Hello

   return 0;

}

循环避坑！⚠️

• 别写 “死循环”！比如for (;;)或while (true)，除非你想让程序 “无限复读” 直到电脑死机💻💥。一旦出现死循环，赶紧按 “Ctrl+C” 强制停止，不然你的电脑会像 “卡壳的录音机” 一样停不下来；

• 循环条件要 “能变化”：比如while (sum <= 1000)里的sum会不断增加，最终会不满足条件跳出循环；如果写成while (1 <= 1000)，条件永远为真，就成了死循环；

• for循环的 “更新语句” 别漏写：比如for (int i = 1; i <= 10; )，少了i++，i永远是 1，会一直循环下去。

2.7 数组：“一排盒子”，装多个同类型数据

如果要装 100 个学生的成绩，总不能定义 100 个变量a1 a2 ... a100吧？这时候就需要数组，相当于 “一排一模一样的盒子”📚，每个盒子有编号（下标），方便查找。

数组的定义：“指定盒子数量和类型”

格式：数据类型 数组名[长度];，长度必须是 “常量”（比如 100、5，不能是变量）。

int a[10];      // 10个装整数的盒子，编号0-9（注意！下标从0开始，不是1！）

double b[5];    // 5个装小数的盒子，编号0-4

char c[20];     // 20个装字符的盒子，编号0-19

数组的初始化：“给一排盒子装东西”

// 方式1：全部初始化

int a[5] = {1, 2, 3, 4, 5};  // a[0]=1, a[1]=2, ..., a[4]=5

// 方式2：部分初始化，未初始化的默认为0

int b[5] = {1, 2};  // b[0]=1, b[1]=2, b[2]=0, b[3]=0, b[4]=0

// 方式3：不写长度，让编译器自己数

int c[] = {10, 20, 30};  // 编译器会自动判断长度为3，下标0-2

数组的使用：“通过编号找盒子”

示例：输入 10 个整数，求它们的和

#include <iostream>

using namespace std;

int main()

{

   int a[10], sum = 0;

   cout << "请输入10个整数：" << endl;

   for (int i = 0; i < 10; i++)

   {

       cin >> a[i];  // 给第i个盒子装数据

       sum += a[i];  // 累加第i个盒子里的数据

   }

   cout << "这10个整数的和是：" << sum << endl;

   return 0;

}

数组避坑！⚠️

• 下标从 0 开始！这是 OI 新手最容易踩的坑！比如int a[5]的下标是 0-4，不是 1-5，访问a[5]会 “越界”，导致程序崩溃或输出乱码（相当于去翻别人的盒子，会被 “保安” 抓👮）；

• 数组长度不能是变量！比如int n = 10; int a[n];在 C++ 里是不允许的（某些编译器支持，但 OI 比赛里绝对不行），必须用常量，比如int a[10];；

• 数组不能直接赋值！比如int a[5] = {1,2,3,4,5}; int b[5]; b = a;是错误的，要赋值得用循环逐个元素复制。

2.8 字符串：“一串字符盒子”，装文字用

字符串就是 “字符数组的升级版”，用来装文字（比如 “OI 加油”），用string类型最方便，比字符数组好用 100 倍！👍

string 的定义和初始化

#include <string>  // 必须包含这个库！

using namespace std;

int main()

{

   string s1;          // 空字符串

   string s2 = "OI";   // 初始化字符串为"OI"

   string s3 = s2;     // 用另一个字符串初始化

   string s4(5, 'a');  // 5个'a'组成的字符串，即"aaaaa"

   return 0;

}

string 的常用操作

#include <iostream>

#include <string>

using namespace std;

int main()

{

   string s = "Hello";

   string t = " OI!";

  

   // 1. 拼接字符串（直接用+）

   string res = s + t;

   cout << res << endl;  // 输出"Hello OI!"

  

   // 2. 获取长度（用size()或length()，都一样）

   cout << "长度：" << res.size() << endl;  // 输出9

  

   // 3. 访问单个字符（和数组一样，下标从0开始）

   cout << "第一个字符：" << res[0] << endl;  // 输出'H'

  

   // 4. 输入输出字符串（直接用cin和cout，不用考虑空格）

   string s5;

   cout << "请输入一个字符串：" << endl;

   cin >> s5;  // 输入"Algorithm"

   cout << "你输入的是：" << s5 << endl;  // 输出"Algorithm"

  

   return 0;

}

字符串避坑！⚠️

• 用string必须包含<string>库！不然编译器会 “不认识”string类型；

• cin读字符串时会 “遇到空格就停”：比如输入 “Hello World”，cin >> s只会读入 “Hello”，如果要读入带空格的字符串，要用getline(cin, s)；

• 字符串下标也会越界！比如s = "OI"，访问s[2]会出错。

2.9 函数：“代码的‘积木块’”，重复使用更高效

如果多个地方都需要 “计算两个数的和”，总不能每次都写一遍加法代码吧？这时候就需要函数，相当于 “预制的积木块”🧱，写一次就能反复用。

函数的定义：“造一个积木块”

格式：返回值类型 函数名(参数列表)

{

函数体（要执行的代码）

return 返回值；// 和返回值类型对应

}

示例：定义一个求两个整数和的函数

#include <iostream>

using namespace std;

// 函数定义：返回值类型int，函数名add，参数列表int x, int y

int add(int x, int y)

{

   int z = x + y;

   return z;  // 返回和z

}

int main()

{

   int a = 5, b = 3;

   int sum = add(a, b);  // 调用函数，把a和b传给x和y，接收返回值

   cout << "5+3=" << sum << endl;  // 输出8

   return 0;

}

函数的参数：“给积木块传材料”

参数分 “形参” 和 “实参”：

• 形参：函数定义时的参数（比如add函数的x y），相当于 “积木块的接口”；

• 实参：函数调用时的参数（比如add(a, b)的a b），相当于 “传给接口的材料”。

函数的返回值：“积木块的产出”

• 返回值类型要和return后面的值类型一致：比如int add(...)，return后面必须是整数；

• 如果没有返回值，返回值类型写void，可以不写return：

void print_hello()

{

   cout << "Hello Function!" << endl;

}

int main()

{

   print_hello();  // 调用函数，输出"Hello Function!"

   return 0;

}

函数避坑！⚠️

• 函数要 “先声明后使用”：如果函数定义在main函数后面，必须在main前面声明，不然编译器会 “不认识” 函数：

#include <iostream>

using namespace std;

// 函数声明（告诉编译器有这个函数）

int add(int x, int y);

int main()

{

   int sum = add(5, 3);  // 可以正常调用

   return 0;

}

// 函数定义（在main后面）

int add(int x, int y)

{

   return x + y;

}

• 形参和实参类型要匹配：比如add(5.0, 3)，形参是int，实参是double，可能会出错；

• 不要在函数里定义 “全局变量”：函数里定义的变量是 “局部变量”，出了函数就 “消失” 了，全局变量在函数外定义，所有函数都能访问，但尽量少用（容易搞混）。

2.10 指针：“变量的‘地址牌’”，进阶知识点（入门了解即可）

指针是 C++ 的 “灵魂”，但对 OI 新手来说有点难，先简单了解：指针就是 “存储变量地址的变量”，相当于 “地址牌”🗺️，通过地址能找到变量本身。

指针的定义和使用

#include <iostream>

using namespace std;

int main()

{

   int a = 10;

   int *p = &a;  // 定义指针p，存储a的地址（&是取地址符）

  

   cout << "a的值：" << a << endl;       // 输出10

   cout << "a的地址：" << &a << endl;    // 输出a在内存中的地址（比如0x61fe14）

   cout << "p的值（a的地址）：" << p << endl;  // 输出和&a一样的地址

   cout << "p指向的值（a的值）：" << *p << endl;  // *是解引用符，输出10

  

   *p = 20;  // 通过指针修改a的值

   cout << "修改后a的值：" << a << endl;  // 输出20

   return 0;

}

指针避坑！⚠️

• 指针要 “初始化”：不然会指向 “垃圾地址”，修改*p会导致程序崩溃；

• 别解引用 “空指针”：int *p = NULL; *p = 10;会直接崩溃；

• 入门阶段用得少：OI 新手先掌握前面的内容，指针在进阶算法（比如链表）里才常用。

第三章：算法入门 —— 代码的 “解题思路”

语法学会了，就像学会了 “拼音和汉字”，但要写出 “好文章”（解决 OI 问题），还需要 “写作思路”（算法）。算法就是 “解决问题的步骤”，比如 “怎么找数组里的最大值”“怎么排序”，这些都是基础算法。

3.1 枚举算法：“暴力出奇迹”，最简单的算法

枚举算法就是 “一个一个试”，像 “找钥匙时把钥匙串上的钥匙挨个试”🔑，虽然笨，但对简单问题很有用。

适用场景：

问题的可能解数量不多，能一个个列举出来判断。

示例：找 1-100 中能被 3 和 5 同时整除的数

#include <iostream>

using namespace std;

int main()

{

   cout << "1-100中能被3和5同时整除的数：" << endl;

   for (int i = 1; i <= 100; i++)

   {

       if (i % 3 == 0 && i % 5 == 0)

       {

           cout << i << " ";

       }

   }

   // 输出：15 30 45 60 75 90

   return 0;

}

枚举避坑！⚠️

• 别 “枚举范围太大”：比如找 1-1e9 中的某个数，枚举会超时（程序运行时间太长，OI 比赛里会判错）；

• 优化枚举条件：比如找 “两个数的和为 100”，可以枚举一个数i，另一个数就是100-i，不用枚举两个数，节省时间。

3.2 查找算法：“找东西的技巧”，比枚举快

查找就是 “在一堆数据里找某个目标”，比如 “在成绩表里找小明的分数”，常用的有 “顺序查找” 和 “二分查找”。

3.2.1 顺序查找：“从头摸到尾”，简单但慢

顺序查找就是 “从第一个元素开始，挨个看是不是目标”，像 “在书架上一本本找书”📚。

示例：在数组中找目标值，返回下标（没找到返回 - 1）

#include <iostream>

using namespace std;

int search(int a[], int n, int target)

{

   for (int i = 0; i < n; i++)

   {

       if (a[i] == target)

       {

           return i;  // 找到，返回下标

       }

   }

   return -1;  // 没找到

}

int main()

{

   int a[5] = {10, 20, 30, 40, 50};

   int target = 30;

   int pos = search(a, 5, target);

   if (pos != -1)

   {

       cout << "找到目标，下标为：" << pos << endl;  // 输出2

   }

   else

   {

       cout << "没找到目标" << endl;

   }

   return 0;

}

3.2.2 二分查找：“折半找”，快但要求数据有序

二分查找就像 “猜数字游戏”：“我想的数字在 1-100 之间，你猜 50，我说太大，你就知道在 1-49 之间，再猜 25……”，前提是数据 “从小到大排好序”。

二分查找步骤：

1. 定义左边界l（初始 0）和右边界r（初始 n-1）；

2. 计算中间位置mid = (l + r) / 2；

3. 如果a[mid] == target，找到，返回 mid；

4. 如果a[mid] > target，目标在左边，r = mid - 1；

5. 如果a[mid] < target，目标在右边，l = mid + 1；

6. 重复 2-5，直到l > r，没找到，返回 - 1。

示例：有序数组中二分查找目标值

#include <iostream>

using namespace std;

int binary_search(int a[], int n, int target)

{

   int l = 0, r = n - 1;

   while (l <= r)

   {

       int mid = (l + r) / 2;

       if (a[mid] == target)

       {

           return mid;

       }

       else if (a[mid] > target)

       {

           r = mid - 1;

       }

       else

       {

           l = mid + 1;

       }

   }

   return -1;

}

int main()

{

   int a[5] = {10, 20, 30, 40, 50};  // 必须有序！

   int target = 40;

   int pos = binary_search(a, 5, target);

   if (pos != -1)

   {

       cout << "找到目标，下标为：" << pos << endl;  // 输出3

   }

   else

   {

       cout << "没找到目标" << endl;

   }

   return 0;

}

二分查找避坑！⚠️

• 数据必须有序！这是二分查找的 “生命线”，无序数组不能用；

• 防止l + r溢出：如果l和r很大（比如 1e9），l + r会超过int的范围，改成mid = l + (r - l) / 2就安全了；

• 边界条件别搞错：是l <= r还是l < r，r = mid - 1还是r = mid，搞混会导致死循环或漏找。

3.3 排序算法：“给数据排队”，OI 必备技能

排序就是 “把乱序的数据排成有序的”，比如 “给学生成绩从高到低排”“给名字按字母顺序排”，常用的有冒泡排序、选择排序、插入排序，进阶的有快速排序、归并排序（入门先掌握前三种）。

3.3.1 冒泡排序：“像气泡一样往上冒”

冒泡排序的思路是 “相邻元素比大小，大的往后挪”，就像水里的气泡往上冒一样🌊，每一轮都能把最大的元素 “冒” 到最后面。

冒泡排序步骤：

1. 从第一个元素开始，和第二个元素比，如果第一个大，就交换；

2. 接着和第三个元素比，大的交换，直到最后一个元素，这一轮结束，最大的元素到了末尾；

3. 重复 1-2，直到所有元素有序。

示例：对数组进行升序排序（从小到大）

#include <iostream>

using namespace std;

void bubble_sort(int a[], int n)

{

   for (int i = 0; i < n - 1; i++)  // 共需要n-轮（最后一个不用排）

   {

       for (int j = 0; j < n - 1 - i; j++)  // 每轮少比i个（后面的已经排好）

       {

           if (a[j] > a[j + 1])  // 前一个比后一个大，交换

           {

               int temp = a[j];

               a[j] = a[j + 1];

               a[j + 1] = temp;

           }

       }

   }

}

int main()

{

   int a[5] = {3, 1, 4, 2, 5};

   bubble_sort(a, 5);

   cout << "排序后：";

   for (int i = 0; i < 5; i++)

   {

       cout << a[i] << " ";

   }

   // 输出：1 2 3 4 5

   return 0;

}

3.3.2 选择排序：“选最小的放前面”

选择排序的思路是 “每轮选最小的元素，放到当前位置”，像 “挑苹果” 一样🍎，先挑最小的放第一个，再挑剩下的最小的放第二个。

选择排序步骤：

1. 从第一个位置开始，找整个数组里最小的元素，和第一个元素交换；

2. 从第二个位置开始，找剩下数组里最小的元素，和第二个元素交换；

3. 重复 1-2，直到所有元素有序。

示例：对数组进行升序排序

#include <iostream>

using namespace std;

void select_sort(int a[], int n)

{

   for (int i = 0; i < n - 1; i++)  // 共需要n-1轮（最后一个不用排）

   {

       int min_pos = i;  // 记录最小元素的下标

       for (int j = i + 1; j < n; j++)  // 找i后面的最小元素

       {

           if (a[j] < a[min_pos])

           {

               min_pos = j;  // 更新最小元素下标

           }

       }

       // 交换最小元素和当前位置元素

       int temp = a[i];

       a[i] = a[min_pos];

       a[min_pos] = temp;

   }

}

int main()

{

   int a[5] = {3, 1, 4, 2, 5};

   select_sort(a, 5);

   cout << "排序后：";

   for (int i = 0; i < 5; i++)

   {

       cout << a[i] << " ";

   }

   // 输出：1 2 3 4 5

   return 0;

}

3.3.3 插入排序：“像插扑克牌一样”

插入排序的思路是 “把元素插入到已排序的部分”，就像打扑克时整理手牌，新摸的牌插在合适的位置🃏。

插入排序步骤：

1. 认为第一个元素是 “已排序的”；

2. 取第二个元素，和已排序的元素比，插入到正确位置；

3. 取第三个元素，和已排序的元素从后往前比，插入到正确位置；

4. 重复 2-3，直到所有元素有序。

示例：对数组进行升序排序

#include <iostream>

using namespace std;

void insert_sort(int a[], int n)

{

   for (int i = 1; i < n; i++)  // 从第二个元素开始插入

   {

       int temp = a[i];  // 保存要插入的元素

       int j = i - 1;    // 已排序部分的最后一个元素下标

       // 从后往前找插入位置

       while (j >= 0 && a[j] > temp)

       {

           a[j + 1] = a[j];  // 元素后移

           j--;

       }

       a[j + 1] = temp;  // 插入元素

   }

}

int main()

{

   int a[5] = {3, 1, 4, 2, 5};

   insert_sort(a, 5);

   cout << "排序后：";

   for (int i = 0; i < 5; i++)

   {

       cout << a[i] << " ";

   }

   // 输出：1 2 3 4 5

   return 0;

}

排序算法对比与避坑！⚠️

排序算法	时间复杂度（大概）	特点	适用场景
冒泡排序	O(n²)	简单易写，稳定（相等元素不交换位置）	数据量小
选择排序	O(n²)	交换次数少，不稳定	数据量小
插入排序	O(n²)	接近有序时快，稳定	数据量小或接近有序

避坑提醒：

• 排序算法的 “稳定性”：比如数组里有两个相同的数，排序后它们的相对位置不变就是稳定的，对有 “优先级” 的数据（比如先按成绩排，再按姓名排）很重要；

• 别死记硬背代码：理解思路比背代码重要，比如冒泡排序是 “相邻交换”，选择排序是 “选最小交换”，插入排序是 “插入已排序部分”，理解后能自己写出来；

• 数据量小时用简单排序：如果数据量超过 1e4，O (n²) 的排序会超时，这时候需要用快速排序、归并排序等 O (nlogn) 的算法（入门阶段先了解，后续进阶）。

3.4 递推与递归：“用自己解决自己”

递推和递归都是 “从已知推未知” 的思路，就像 “多米诺骨牌”🀄，第一张倒下推第二张，第二张推第三张…… 直到最后一张。

3.4.1 递推：“从前往后推”

递推是 “从初始条件开始，一步步推出结果”，比如求斐波那契数列（1,1,2,3,5,8…），第 n 项 = 第 n-1 项 + 第 n-2 项。

示例：用递推求斐波那契数列第 n 项

#include <iostream>

using namespace std;

int main()

{

   int n;

   cout << "请输入n：";

   cin >> n;

   if (n == 1 || n == 2)

   {

       cout << "第" << n << "项是1" << endl;

       return 0;

   }

   int a = 1, b = 1, c;  // a是第i-2项，b是第i-1项，c是第i项

   for (int i = 3; i <= n; i++)

   {

       c = a + b;

       a = b;  // 更新a和b

       b = c;

   }

   cout << "第" << n << "项是" << c << endl;

   return 0;

}

3.4.2 递归：“从后往前推，再返回”

递归是 “把大问题拆成小问题，小问题和大问题解法一样，直到拆到最小问题（终止条件）”，比如求斐波那契数列第 n 项，f (n)=f (n-1)+f (n-2)，终止条件是 f (1)=1，f (2)=1。

示例：用递归求斐波那契数列第 n 项

#include <iostream>

using namespace std;

int fib(int n)

{

   // 终止条件：最小问题的解

   if (n == 1 || n == 2)

   {

       return 1;

   }

   // 递归调用：大问题拆成小问题

   return fib(n - 1) + fib(n - 2);

}

int main()

{

   int n;

   cout << "请输入n：";

   cin >> n;

   cout << "第" << n << "项是" << fib(n) << endl;

   return 0;

}

递推与递归对比与避坑！⚠️

方法	特点	优点	缺点
递推	从前往后，迭代计算	效率高，不占内存	需要找到递推公式
递归	从后往前，函数调用	代码简洁，思路清晰	效率低（重复计算），可能栈溢出

避坑提醒：

• 递归必须有 “终止条件”！不然会无限调用函数，导致 “栈溢出”（内存不够用），比如 fib (n) 如果没有 n1 和 n2 的终止条件，会一直调用 fib (n-1)、fib (n-2)…… 直到程序崩溃；

• 递归要避免 “重复计算”！比如 fib (5)=fib (4)+fib (3)，fib (4)=fib (3)+fib (2)，fib (3) 被计算了两次，n 越大重复越多，效率越低，解决办法是 “记忆化搜索”（把计算过的结果存起来，下次直接用）；

• 递推更适合 OI 比赛：递归虽然代码短，但效率低，比赛里尽量用递推，除非递归思路特别清晰且不会超时。

3.5 前缀和：“快速求区间和”，效率神器

前缀和是 “预处理数组的前缀和，然后快速计算任意区间的和”，就像 “提前算好 1-10 的和、1-20 的和，要算 11-20 的和直接用 1-20 的和减 1-10 的和”🧮，能把 O (n) 的区间和计算变成 O (1)。

前缀和定义：

设原数组为 a [0..n-1]，前缀和数组 s [0..n]，其中 s [0]=0，s [i] = a [0] + a [1] + ... + a [i-1]（s [i] 是前 i 个元素的和）。

区间和计算：

区间 [l..r]（下标从 0 开始，包含 l 和 r）的和 = s [r+1] - s [l]。

示例：用前缀和求数组任意区间的和

#include <iostream>

using namespace std;

int main()

{

   int n, m;

   cout << "请输入数组长度n和查询次数m：";

   cin >> n >> m;

   int a[1000], s[1001] = {0};  // s[0]初始为0

   // 输入原数组

   for (int i = 0; i < n; i++)

   {

       cin >> a[i];

   }

   // 计算前缀和数组

   for (int i = 1; i <= n; i++)

   {

       s[i] = s[i - 1] + a[i - 1];

   }

   // 处理m次查询

   for (int i = 0; i < m; i++)

   {

       int l, r;

       cout << "请输入区间[l, r]（0<=l<=r<n）：";

       cin >> l >> r;

       int sum = s[r + 1] - s[l];

       cout << "区间[" << l << "," << r << "]的和是：" << sum << endl;

   }

   return 0;

}

前缀和避坑！⚠️

• 前缀和数组要多开一个位置！s [0]=0，这样计算 s [1] = s [0]+a [0]，s [2]=s [1]+a [1]，逻辑更清晰，避免计算区间 [0..r] 时出错；

• 原数组和前缀和数组的下标要对应！别搞混 s [i] 对应的是前 i 个元素（a [0] 到 a [i-1]），区间 [l..r] 的和是 s [r+1]-s [l]，不是 s [r]-s [l-1]（除非 s [1] 是 a [0]，s [2] 是 a [0]+a [1]，但容易出错）；

• 适用于 “静态数组”！如果数组里的元素会修改，前缀和就失效了，这时候需要用 “树状数组” 或 “线段树”（进阶内容）。

第四章：OI 入门实战 —— 从 “懂” 到 “会用”

语法和算法都学了点，现在来实战！解决几个经典的 OI 入门问题，把知识用起来，就像 “学会了招式要打打靶子”🎯。

4.1 实战 1：求最大公约数（GCD）

问题：输入两个正整数 a 和 b，求它们的最大公约数（能同时整除 a 和 b 的最大整数）。

思路：辗转相除法（欧几里得算法）

辗转相除法的原理是 “gcd (a,b) = gcd (b,a% b)”，直到 b=0，此时 a 就是最大公约数。比如 gcd (18,12)=gcd (12,6)=gcd (6,0)=6。

代码实现：

#include <iostream>

using namespace std;

int gcd(int a, int b)

{

   while (b != 0)

   {

       int temp = b;

       b = a % b;

       a = temp;

   }

   return a;

}

int main()

{

   int a, b;

   cout << "请输入两个正整数：";

   cin >> a >> b;

   cout << "它们的最大公约数是：" << gcd(a, b) << endl;

   return 0;

}

代码解读：

• 辗转相除法效率很高，比 “枚举法找公约数” 快得多，即使 a 和 b 很大（比如 1e9）也能很快算出；

• 也可以用递归实现：int gcd(int a,int b){return b?gcd(b,a%b):a;}，一行代码搞定，很简洁。

4.2 实战 2：判断素数

问题：输入一个正整数 n，判断它是不是素数（只能被 1 和自身整除的大于 1 的整数）。

思路：

1. 特殊情况：n<=1 不是素数，n=2 是素数，n 是偶数不是素数；

2. 枚举从 3 到 sqrt (n) 的奇数，看有没有能整除 n 的，如果有就不是素数，否则是素数（因为如果 n 有大于 sqrt (n) 的因子，那么对应的另一个因子一定小于 sqrt (n)，不用重复判断）。

代码实现：

#include <iostream>

#include <cmath>  // 用sqrt函数

using namespace std;

bool is_prime(int n)

{

   if (n <= 1)

   {

       return false;

   }

   if (n == 2)

   {

       return true;

   }

   if (n % 2 == 1)
    {

        return false;

    }

    // 枚举到 sqrt (n)，步长为 2（只看奇数）

    for (int i = 3; i <= sqrt (n); i += 2)

    {

        if (n % i == 0)

         {

                return false;

         }

    }

        return true;

}

int main ()

{

    int n;

    cout << "请输入一个正整数：";

    cin >> n;

    if (is_prime (n))

    {

        cout << n << "是素数！" << endl;

    }

    else

    {

        cout << n << "不是素数。" << endl;

    }

    return 0;

}

代码解读与优化：

• 为什么枚举到sqrt(n)？假设n = a*b，且a <= b，那么a <= sqrt(n)，所以只要检查到平方根就够了，减少一半工作量；

• 为什么只枚举奇数？除了2以外的偶数都不是素数，跳过偶数能节省一半时间；

• 进阶优化：对于超大数（比如1e12），可以用“米勒-拉宾素性测试”，但入门阶段掌握上面的方法就够了。

4.3 实战3：前缀和进阶——二维前缀和

问题：输入一个n行m列的二维数组（矩阵），多次查询某个子矩阵的元素和，比如查询第x1行到x2行、第y1列到y2列的和。

思路：二维前缀和

一维前缀和是“一行的前缀和”，二维前缀和就是“矩阵的前缀和”📊，预处理后能快速计算任意子矩阵的和。

二维前缀和定义：

设原矩阵为a[n][m]（下标从1开始更方便），前缀和矩阵s[n+1][m+1]，其中s[i][j]表示“左上角(1,1)到右下角(i,j)的子矩阵和”。

二维前缀和公式：

s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1]

（原理：大矩阵和 = 当前元素 + 上方矩阵和 + 左方矩阵和 - 重复加的左上矩阵和）

子矩阵和计算：

子矩阵(x1,y1)到(x2,y2)的和 = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]

代码实现：

#include <iostream>

using namespace std;

const int N = 1010;  // 定义矩阵最大尺寸

int a[N][N], s[N][N];

int main()

{

   int n, m, q;

   cout << "请输入矩阵行数n、列数m、查询次数q：";

   cin >> n >> m >> q;

   // 输入原矩阵（下标从1开始）

   for (int i = 1; i <= n; i++)

   {

       for (int j = 1; j <= m; j++)

       {

           cin >> a[i][j];

       }

   }

   // 计算二维前缀和

   for (int i = 1; i <= n; i++)

   {

       for (int j = 1; j <= m; j++)

       {

           s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];

       }

   }

   // 处理q次查询

   while (q--)

   {

       int x1, y1, x2, y2;

       cout << "请输入子矩阵左上角(x1,y1)和右下角(x2,y2)：";

       cin >> x1 >> y1 >> x2 >> y2;

       int sum = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];

       cout << "子矩阵和为：" << sum << endl;

   }

   return 0;

}

二维前缀和避坑！⚠️

• 矩阵下标从 1 开始！这是二维前缀和的 “约定俗成”，能避免处理i=0或j=0时的边界问题（比如s[0][j]和s[i][0]都为 0）；

• 公式别记混符号！计算s[i][j]是 “减s[i-1][j-1]”，计算子矩阵和是 “加s[i-1][j-1]”，可以画图辅助理解（画个十字交叉，重复部分要减或加）；

• 数组开够尺寸！OI 比赛里要根据题目给出的 n、m 最大值定义数组（比如题目说 n<=1000，就定义 N=1010，留一点冗余）。

4.4 实战 4：递推应用 —— 爬楼梯问题

问题：有 n 级台阶，每次能爬 1 级或 2 级台阶，求有多少种不同的爬法。

思路：

• 第 1 级台阶：1 种方法（直接爬 1 级）；

• 第 2 级台阶：2 种方法（1+1 或直接 2 级）；

• 第 n 级台阶：到达第 n 级的前一步要么是从 n-1 级爬 1 级，要么是从 n-2 级爬 2 级，所以爬法数 = f (n-1)+f (n-2)（斐波那契数列的变形）。

代码实现（递推版，效率高）：

#include <iostream>

using namespace std;

int main()

{

   int n;

   cout << "请输入台阶数n：";

   cin >> n;

   if (n == 1)

   {

       cout << "1种方法" << endl;

       return 0;

   }

   if (n == 2)

   {

       cout << "2种方法" << endl;

       return 0;

   }

   int a = 1, b = 2, c;  // a=f(n-2), b=f(n-1), c=f(n)

   for (int i = 3; i <= n; i++)

   {

       c = a + b;

       a = b;

       b = c;

   }

   cout << c << "种方法" << endl;

   return 0;

}

代码解读：

• 为什么不用递归？如果 n=40，递归会计算大量重复的 f (n)（比如 f (38) 会被计算两次），效率极低；递推只计算一次，O (n) 时间复杂度，秒杀递归；

• 进阶拓展：如果每次能爬 1、2、3 级台阶，递推公式就是 f (n)=f (n-1)+f (n-2)+f (n-3)，初始条件 f (1)=1、f (2)=2、f (3)=4。

第五章：OI 入门避坑指南与进阶方向

学到这里，你已经从 “OI 小白” 进化成 “算法萌新” 了！但 OI 之路布满 “陷阱”，掌握避坑技巧能少走 99% 的弯路，同时明确进阶方向才能走得更远🚀。

5.1 那些年 OI 新手踩过的坑（避坑大全）

5.1.1 语法类坑

• 分号遗漏：for循环、if语句、变量定义后漏写分号，编译器会报错 “expected ';' before ...”，比如int a=5（漏分号）；

• 大括号不匹配：写嵌套循环或分支时，大括号成对遗漏，比如if(...) { for(...) { ... }（少了一个}），编译器可能报 “expected '}' at end of file”；

• 变量未初始化：定义变量后直接使用，比如int sum; sum += 5;，sum 初始值是垃圾数据，结果会出错；

• 数组下标越界：int a[5]; a[5] = 10;（下标最大 4），程序可能崩溃或输出乱码，OI 比赛里这种错误最难调试；

• 整数溢出：int a=1e9; a=a*2;（int 最大约 2e9，乘 2 后溢出），结果会变成负数，解决办法是用long long。

5.1.2 算法类坑

• 二分查找边界错误：把l <= r写成l < r，导致漏查目标；或者mid计算溢出，比如mid=(l+r)/2当 l 和 r 都是 1e9 时溢出；

• 递归无终止条件：写递归函数时漏写终止条件，比如int f(int n){return f(n-1);}，会无限递归导致栈溢出；

• 排序算法逻辑错误：冒泡排序的内层循环条件写成j < n-1（漏了-i），导致已经排好的元素重复比较；

• 前缀和下标混乱：把一维前缀和的区间和公式写成s[r]-s[l-1]，但s[0]没初始化为 0，导致区间 [0..r] 计算错误。

5.1.3 比赛类坑

• 输入输出方式错误：数据量大时用cin/cout会超时，要加ios::sync_with_stdio(false); cin.tie(0);加速；

• 文件名错误：比赛要求程序文件名是main.cpp，写成test.cpp会被判 0 分；

• 未考虑特殊情况：比如判断素数时漏了 n=2（唯一的偶素数），求 GCD 时漏了 a<b 的情况（其实辗转相除法会自动交换，但最好预处理）；

• 代码提交前未测试：写完代码直接提交，没测边界数据（比如 n=1、n=0），导致 WA（Wrong Answer）。

5.2 调试技巧（新手必备）

• 输出调试法：在关键位置加cout输出变量值，比如二分查找时输出l、r、mid的值，看是否符合预期；

• 注释调试法：怀疑某段代码有问题时，用/* */注释掉，看程序是否正常运行，定位错误位置；

• 边界数据测试：比如爬楼梯问题测 n=1、n=2，素数问题测 n=2、n=9（合数）、n=17（素数）；

• 编译器报错解读：编译器报错时看 “error: ... at line X”，直接定位到第 X 行，比如 “error: 'b' was not declared in this scope” 表示变量 b 未定义。

5.3 OI 进阶方向（从萌新到大佬的路径）

5.3.1 基础进阶（入门后 3 个月）

• 数据结构：学习栈、队列、链表、哈希表（入门级数据结构），掌握它们的基本操作和应用场景；

• 算法进阶：学习快速排序、归并排序（O (nlogn) 排序）、计数排序（特殊场景排序），以及贪心算法（比如活动安排问题）；

• 数学基础：补充数论基础（质数筛、最小公倍数 LCM、同余定理）、组合数学（排列组合、杨辉三角）。

5.3.2 中级进阶（入门后 6 个月）

• 数据结构：学习树（二叉树、二叉搜索树）、堆（大根堆、小根堆）、并查集（Union-Find）；

• 算法进阶：学习动态规划（DP，比如 01 背包、完全背包问题）、广度优先搜索（BFS，比如迷宫最短路径）、深度优先搜索（DFS，比如全排列问题）；

• 实战训练：在 OJ（在线判题系统）上刷入门题，比如洛谷 P1000-P2000 的题目。

5.3.3 高级进阶（入门后 1 年 +）

• 数据结构：学习线段树、树状数组（处理动态区间查询）、平衡树（进阶）；

• 算法进阶：学习图论（最短路径 Dijkstra 算法、最小生成树 Kruskal 算法）、高级动态规划（状态压缩 DP、树形 DP）；

• 比赛备战：参加 NOIP 普及组、CSP-J 等比赛，刷历年真题，提升代码速度和调试能力。

5.4 推荐工具与资源（新手必备）

5.4.1 编程工具

• Dev-C++：入门首选，轻便简洁，适合写基础代码；

• VS Code：进阶用，支持插件扩展（比如 C/C++ 插件、代码补全插件），界面美观；

• Code::Blocks：跨平台，调试功能强大，适合比赛用。

5.4.2 在线判题系统（OJ）

• 洛谷（luogu.com.cn）：国内最大的 OIer 社区，题目分类清晰，入门题丰富，支持在线编译；

• AcWing（acwing.com）：有入门到进阶的系统课程，题目难度梯度合理，适合系统学习；

• Codeforces（codeforces.com）：国际知名 OJ，比赛多，题目质量高，适合进阶后刷算法题。

5.4.3 学习资源

• 书籍：《C++ Primer Plus》（语法基础）、《算法图解》（算法入门，图文并茂）、《信息学奥赛一本通》（OI 专用教材）；

• 视频课程：AcWing 的 “算法基础课”、B 站 “正月点灯笼” 的算法入门视频（幽默易懂）；

• 社区：洛谷论坛、知乎 “信息学奥赛” 话题，遇到问题可以发帖求助。

第六章：总结 ——OI 之路，始于足下

看到这里，你已经掌握了 OI 的 “地基”：C++ 基础语法（变量、循环、数组、函数）和基础算法（枚举、二分、排序、递推、前缀和），还解决了几个经典实战问题，甚至知道了怎么避坑和进阶。

很多人觉得 OI 很难，其实难的不是语法或算法，而是 “坚持”—— 从写第一个 “Hello World” 到 AC（Accepted）第一道算法题，从调试半天的下标越界到轻松写出动态规划代码，每一步都需要练习。

最后送大家一句 OI 界的名言：“代码千万行，调试第一难；细节不注意，爆零两行泪。” 希望大家多写代码、多练算法、多踩坑（然后爬出来），终有一天能成为算法大佬，在比赛中拿到金牌🏅！

如果觉得这篇文章有用，别忘了点赞收藏～ 有任何问题可以在评论区留言，我会一一解答！祝大家 OI 之路一帆风顺！🎉

暴力出奇迹，打表进省一