信息学竞赛没入门就出门

T_TLucas_Yin · 2025-03-16 20:40:27 · 算法·理论

其实我打算把从 C++ 基本语法到我能学到的所有算法全部写在这里，所以这可以当作一个笔记或教程。

不管你什么时候打开这篇文章，请抱有以下心态：

• 这篇文章已经停更了，别指望作者再往后写新的东西。
• 一切知识和代码的介绍都是根据作者的个人理解解释的，未必专业。作者很菜的，文章中可能出现各种疏漏或错误，发现了及时私信作者指出即可。
• 有些专有名字第一次出现时，铺垫的前置知识可能不足，导致初见的人不知道是什么意思。作者会尽量在后文补全彻底理解所需的前置知识。
• 这篇文章的介绍顺序可能和别的文章不大一样，但是作者认为最适合初学者理解的顺序
• 作者的文笔很烂也很啰嗦。

当然，适当期待一下也可以。

一些前置知识：

• 关于 OI 比赛的内容、规则、考察范围等基本信息。
• 计算机的使用，软件、浏览器以及网站的使用。
• 简单了解计算机内部运行、存储的逻辑。
• 认识二进制数字。
• 初中数学和部分高中数学。

第一章 学会写代码

（说实话这一部分很多底层原理作者也没有系统的学过，解释只是为了理解起来更方便，可能十分不专业）

OI 使用的编程语言是 C++。目前常用版本为 C++98 至 C++17。所以想要学 OI，要先学会用 C++ 写代码。

首先需要下载一个 Dev-C++ 编译器，它可以编译并运行你的代码。版本从 5.11 到 6.0+ 都可。这是操作方式最简单，最适合初学者的编译器。目前正式考试使用的编译器是 Dev 5.11。

熟练后还可以使用更强大的 VS code 编译器。

关于编译器的简单使用请自行学习。

计算机使用 C++ 代码的方式可以理解为：

• 先进行编译操作，即读懂代码。
• 然后运行，即按照代码给出的指令做一些事情。

我们认为计算机是不会出错的，如果运行结果和你预想的不一样，肯定是你的代码写得有问题。

代码的通用规则

对于任何单独成行的代码，后面必须加英文分号 ;，类似于写句子时最后要加句号。

一些特殊代码

注释

先介绍一种特殊的代码格式：注释代码。

以下是单行注释。编译器中 // 后面的内容会自动变成注释。

注释的范围是同一行注释符号右面的内容//在任意一行代码的末尾加"//"就可以写出注释

还有一种多行注释。编译器中 /* 和 */ 之间的内容会自动变成注释。

/*
可以像这样
一次性给很多整行代码注释
*/

注释对代码的功能不会产生任何影响。一般用来向代码的读者解释一些信息。

头文件的使用

C++ 中的一些语句被封装在了头文件里，一个头文件相当于一个拓展包。实现很多我们需要的功能都需要使用头文件中的语句。

头文件有很多个。想要使用某一个头文件中的功能，就要调用该头文件。一般把头文件的引用语句写在程序的最开始。

引用头文件的语句格式如下：

#include<iostream>

其中 iostream 是一个头文件的名字，换成别的名字，就可以引用别的头文件。一个程序可以同时引用多个头文件。

下面这串代码调用了绝大多数平时常用的头文件：

#include<iostream>//标准输入输出流，提供了输入和输出语句
#include<cstdio>//提供了另一种输入输出语句和指向文件的输入输出流
#include<cmath>//提供了一些数学函数
#include<algorithm>//主要提供了可以排序数组的sort函数
#include<cstring>//提供了针对char类型的一些函数
#include<string>//提供了string数据类型和一些string的函数
#include<stack>
#include<vector>
#include<queue>
#include<map>
#include<set>//上面这些头文件分别提供了STL库中的同名数据结构和与其相关函数的功能，这样的头文件还有很多

但如今我们通常不会一次性引用这么多头文件，而是这样写，

#include<bits/stdc++.h>

这个被称为万能头，它包含了上述所有头文件，以及除此以外的很多很多其他的头文件（事实上是标准 C++ 语句库中的所有头文件）。这样任何功能都可以随心所欲地用了，更加方便。

万能头也有一定的缺点，例如增加编译时长、引用后使用一些特殊字符串作为变量名时会报错等。不过使用通常不会给代码的执行带来很大影响。

命名空间的使用

可以认为命名空间将 C++ 的所有代码划分为不同区域，不同区域间的代码可以重名。为了同时使用不同空间的代码，要在代码前写它所属的命名空间。例如命名空间 std 中的输出语句：

std::cout<<"123";

如果在整个程序前引用命名空间，后面该命名空间内的语句就可以不用加前缀。引用语句这样写：

using namespace std;

同理，把 std 换成别的，可以使用别的命名空间。一份代码只能引用一个命名空间。

引用命名空间 std 后，上面的输出语句就可以直接写成：

cout<<"123";

当相似的代码堆叠得很多时，引用命名空间就可以省下很多力气（但引用命名空间并不是必须的）。

目前我见过的所有 OI 代码都只需要使用 std 命名空间。

用户还可以直接在代码中创建自己的命名空间，但这是更高级的语法，而且通常没必要。

主函数的定义

一个解答 OI 问题的程序，通常只由一个个函数构成。

函数可以看成一段被封装成一个整体的语句。一个程序中的定义或声明语句可以写在函数外面，而所有可执行的代码必须写在某一个函数里面。

函数可以由一行代码调用。每调用一次函数即按顺序执行该函数内的每一行代码一次。当然，调用函数的语句也应写在函数内。

这里先介绍一个特殊的函数：主函数。

任何程序都要有主函数。在运行程序时，电脑会自动调用一次主函数，从而启动你的程序。你的代码运行时永远从主函数的第一行开始，并依次执行以下的每一行代码，直到主函数的最末尾。

主函数的基本结构是这样写的：

int main(){
    //一些代码
    return 0;
}

return 0; 是主函数的返回代码。主函数中必须有这条代码且必须像这样写（不能把 0 换成别的数字），否则程序运行会出错。

由大括号 {} 包裹起来的部分即是主函数包括的代码。程序运行的过程就是依次执行这些代码的过程。

综上所述，我们可以总结出 C++ 程序的基本结构框架：

#include<bits/stdc++.h>
using namespace std;
int main(){

    return 0;
}

通常任何程序都包含这样一个框架。

数据存储

数据的存储单位

首先要知道计算机用二进制存储数据。

一个二进制位（bit），简称位，即一个可以表示 0 或 1 两种状态的位置。一个二进制位可以用 1b 来表示。二进制位是计算机存储的最小单位。