信息学奥赛算法大全

前言

这是一篇博客，也可以说是一本书。这篇博客将带着读者们遨游 OI 的世界。在这里，你可以看到从基本的顺序结构到困难的 A* 算法。我们的学习过程中，需要使用到 Openjudge 和洛谷、 Acwing 几种 OJ，请各位读者提前注册好账号。通往 OI 的传送门现在开启！

——DijkstraPhoenix，2023/4/27

一、语法初期

学信奥是必须要学会语法的，语法是将思维变成实现的一种介质，没有语法，任何思维都无法变为现实。

1.1 环境搭建

Windows 环境

在 Windows 环境下，我们使用 Dev-C++ 作为编译器(也就是 IDE)，安装方式如下：

打开这个网址，下载安装包: https://sourceforge.net/projects/orwelldevcpp/

下载页面

运行刚刚下载的安装包，进行下载（一开始的语言选择就选 English 就行了）。安装完后启动 Dev-C++，这里再选择语言为简体中文。字体、颜色、图标自己选，尽量选可以看得清的。

然后就是这个样子：

Dev-C++

Linux 环境

我们在 Linux 环境下，没有 Dev-C++，所以，我们选择另一种不错的 IDE —— Code::Blocks。

如果不习惯 Code::Blocks 的话，可以使用 Geany （自行安装）。

在这里，我们仅展示 Debian 内核的 Linux 安装 Code::Blocks 的步骤，其它 Linux 版本请自行查询安装教程。

Tips: Debian 内核的 Linux 有 Kali、Ubuntu、Deepin、Noi linux 等。

我们打开终端，输入以下命令：

1	`sudo apt-get install codeblocks`

此时，我们需要输入当前用户的密码，才能进行安装（如果用的是超级用户的终端，可以不输入 sudo）。

等待安装完成，我们就可以通过菜单或者在终端里输入 codeblocks 就能启动了。如果无法启动，则可以在终端里输入 sudo codeblocks 或者重装该软件。

1.2 Hello, World！

注：以后我们的代码里会有很多注释，程序不会执行它,如：

//这是一行注释，它不会被执行
/*
这是一个多行注释，不会被执行
这一行也不会被执行
*/

任何一本学习编程的书，基本上第一课就是输出 Hello, World!。

本题请见 Openjudge 1.1.01 - Hello, World!

题目描述

输出一行字符串 “Hello, World!”

输入样例

无

输出样例

1	`Hello, World!`

这道题我们可以画一个简单的流程图：

1	`程序开始 -> 输出 "Hello, World!" -> 结束程序`

在 C++ 中，任何一个程序都是从主函数执行的，我们只需要将代码写在主函数里就行了。

主函数的定义：

int main(void) //int 表示主函数的返回值是 int(整数) 类型的（必须是 int），main 是主函数的名称（也必须是 main），void 表示它不传任何参数，可以省略
{
    //要执行的代码
}

当然，主函数还有其它的定义方式，比如以下几种(此处没有列举完)：

1 2	`int main(int argc){} int main(int argc,char *argv[]){}`

不过我们学习信奥不需要这些参数，有兴趣的读者可以自行查阅资料。

因为我们需要输出一些东西，而流输出函数 cout 定义在 iostream 头文件里，所以我们需要导入它。

cout 是流输出函数，它不需要加括号，只需要加上流输出符号，如:
cout<<1<<2;

完整代码（注释打不打也没有关系，这里做详细的讲解）：

#include<iostream>
//导入流输入输出所在的头文件
//我们还可以使用万能头（并不是万能的），定义如下：
//#include<bits/stdc+++.h>
//在一些编译器中，并不支持万能头（只是少数）
using namespace std;//为防止程序员定义和 iostream 里重名的函数，所以声明了一个 std 命名空间
//using 表示使用，namespace 表示命名空间，std 是命名空间的名称
//这个语句表示使用 std 命名空间。如果不加上这一句，那么用 std 里的东西就需要有单独的声明：比如用 cout 需要写成 std::cout
int main(void)//主函数
{
    cout<<"Hello, World!"<<endl;//C++ 里的语句需要加上分号（英文半角的）
    //字符串需要打上双引号，endl 表示换行
    return 0;
    //程序结束了，返回0
}

我们在 C++ 中，基本上是兼容 C 语言的代码的，所以，这个代码还可以这么写：

#include "stdio.h" 
//C语言的输出函数定义在 stdio.h 里
//C语言没有 std 命名空间，不需要声明
int main(void)
{
    printf("Hello, World!\n");//printf 是格式化输出函数，要加括号
    // \n 是换行符，相当于 C++ 里的 endl
    return 0;
}

我们把这个程序保存为 Helloworld.cpp（名字可以自己改，后缀名不要改），运行一下就成功啦！

如果我们用 C语言写的话，还可以把后缀名改为 .c。

1.3 变量

我们在编程中，不可避免的需要大量变量，本章我们来讲讲变量。

变量是一种可以储存值的容器，可取值也可写入。

常见的变量有以下几种：

short a;//短整型变量
int b;//整型变量
long c;//长整型变量（ps：在几乎所有的电脑上，它和int没有区别）
long long d;//超长整型变量
float e;//单精度浮点型变量（就是小数）
double f;//双精度浮点型变量
long double g;//超长浮点型变量
char h;//字符变量（只能存一个字符）
string i;//字符串
bool j;//布尔类型变量（取值只有“真”和“假”）
......

而一些变量名称前面还可以加上修饰符：

const int ca=10000;//整型常量（不能修改值，必须在定义是赋值）
unsigned int ui;//无符号整型（只能是正数）
signed int si;//带符号整型（可以是正数或负数）
......

不过变量也有取值范围，这里写出几种：

int: (-2^31-1)~(2^31-1)
long long:(-2^63-1)~(2^63-1)
unsigned long long: (0)~(2^64-1)
bool: true或false
......

超过变量的取值范围，变量将会顶破符号位（在位运算中会详细讲解），变成一个极小的负数。

在我们编程中，要选择合适的变量类型和名称，否则会造成不必要的错误。

变量的命名规则有以下几点：1.只能由大小写英文字母、数字和下划线组成（可以使用下划线或者大小写来表示空格）。2.不能以数字开头。3.要避免已经定义过的变量，不管是什么类型的，而且不能定义 C++ 自带的标识符（例如 cin、cout、printf 等）。

变量也可以互相运算，在 C++ 里，运算符分别是这样的：

a+b//加法
a-b//减法
a*b//乘法
a/b//除法
a%b//取余运算（模运算）
a==b//注意：C++表示两个两相等使用两个等号
a!=b//a不等于b
a<b//a小于b
a>b//a大于b
a<=b//a小于等于b
a>=b//a大于等于b

而变量的变化方式也有几种：

a=b//直接把b的值赋给a
a+=b//把a的值加上b
a-=b//把a的值减少b
a*=b//把a的值乘上b
a/=b//把a的值除以b
a++//相当于a=a+1;
a--//相当于a=a-1;

1.4 顺序结构

A+B Problem

洛谷 P1001 A+B Problem

题目描述

输入两个整数 a,b ，输出它们的和 ( |a|,|b| <= 1e9 )。

输入样例

20 30

输出样例

对于这道题，我们需要定义两个变量，来保存 a 和 b 的值，输入这两个变量，在输出它们的和就行了。

所以，我们可以写出这样的代码：

#include<iostream>
using namespace std;
int main(void)
{
    int a,b;//定义两个变量a、b
    cin>>a>>b;//输入a和b(此处使用了流输出，和cout一样，也在iostream头文件和std命名空间里，不过要区分流输入符号和流输出符号)
    cout<<a+b;//输出和
    return 0;
}

输出第2个整数

洛谷 B2003

题目描述

输入三个整数，整数之间由一个空格分隔。把第二个输入的整数输出。

输入样例

1	`123 456 789`

输出样例

本题我们需要定义三个变量，分别输入后再输出第二个变量的值，代码如下：

#include<iostream>
using namespace std;
int main(void)
{
    int a,b,c;
    cin>>a>>b>>c;
    cout<<b;//第二个变量
    return 0;
}

课后习题

1.计算 (a+b)×c 的值 (洛谷B2008)

2.输出保留 3 位小数的浮点数(洛谷B2021)

提示：保留3位小数可以用 printf("%.3f",float类型变量);，double类型需要是 %.3lf

3.带余除法 (洛谷B2010)

1.5 分支结构

奇偶数判断

openjudge 1.4-3

题目描述

给定一个整数 n，判断该数是奇数还是偶数。如果 n 是奇数，输出 odd；如果 n 是偶数，输出 even。

输入样例

输出样例

odd

这道题我们需要进行一个判断：如果(n是奇数) 输出”odd”；否则输出”even”。

而 C++ 里的判断语句，我们可以使用 “if……else if……else” 语句，if 后面的括号里是填判断的依据。

所以，代码可以这么写：

#include<iostream>
using namespace std;
int main(void)
{
    int n;
    cin>>n;
    if(n%2==1)//除2的余数是1
    {
        //奇数
        cout<<"odd";
    }
    else //否则是偶数
    {
        cout<<"even";
    }
    return 0;
}

输出绝对值

openjudge 1.4-2

题目描述

输入一个浮点数，输出这个浮点数的绝对值。

输入格式

输入一个浮点数，其绝对值不超过10000。

输出格式

输出这个浮点数的绝对值，保留到小数点后两位。

样例输入

-3.14

样例输出

3.14

这道题存在一个使用库函数 fabs() 的做法，在这里不做讲解，有兴趣的读者自行查阅。

绝对值是指一个数到 0 的距离，例如 | 123 | = 123, | -456 | = 456。

不难看出，正数和 0 的绝对值就是它本身，而负数的绝对值就是对它取反。

所以，本题可以分类列举大于等于 0 和小于 0 两种情况。

代码如下：

#include<iostream>
using namespace std;
int main(void)
{
    float x;//浮点数，需要 float 类型
    cin>>x;
    //对于这种问题，我们可以使用三目运算符，相当于一个微型的if-else语句
    cout<<(x>=0?/*正数*/x/*否则*/:/*负数*/-x);
    return 0;
}

其中的三目运算符 cout<<(x>=0?x:-x); 和这段代码等同：

if(x>=0)
{
    cout<<x;
}
else 
{
    cout<<-x;
}

逻辑运算

常见的逻辑运算有与、或、非三种。

与的两边同时成立，则表达式成立；或的两边只要有一个是成立的，则表达式成立；非的后面是成立的，则表达式不成立，否则成立。

它们分别写作 && 、 || 、 !，写在 if 语句里就会变成这样：

1
2
3

if(1+1==2 && 3*3==9)
if(1+1==2 || 3*3==10)
if(!(1+1==3))

课后习题

1.判断正负 (洛谷 B2035)

2.判断是否为两位数 (洛谷 B2040)

3.判断能否被 3，5，7 整除 (洛谷 B2043)

Tips：此题需要使用到逻辑运算。

1.6 循环结构

我们在编程中，总会需要循环，虽然一些可以不停地写同一行代码，但遇到无限循环或者不定次数循环就无能为力了。

常见的循环有三种：while 循环、do···while 循环和 for 循环。

首先说说 while 循环。

while 循环是一种条件循环，每次循环检测一次循环条件，成立的话就循环一次，然后再检查。

例如这样：

int i=1;
while(i<=10)
{
    cout<<"Hello"<<endl;
    i++;
}

而 do…while 循环则是先循环一次，再判断条件是否成立。

int i=1;
do
{
    cout<<"Hello"<<endl;
    i++;
}while(i<=10);//别忘了加分号

for 循环是一种很常用的循环，它的功能很多，甚至在 C++14 及以后的版本里可以直接遍历一个不定量数组。

它的模板是 for(定义（也可以直接使用已定义的）循环变量=初始值;循环条件;变化规则)，当然三个语句不一定都要写，但是分号不能省。如前两个样例也可以写成这样：

for(int i=1;i<=10;i++)
{
    cout<<"Hello"<<endl;
}

输出 n 次 “Hello, World!”

本题是自编题。

题目描述

给定一个 n ，输出 n 行 Hello, World!。

样例输入

样例输出

Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!

这道题是在 Hello, World! 的基础上加上了循环。根据它需要循环 n 次，不难想出这道题需要使用 for 循环。

所以代码可以这么写：

#include<iostream>
using namespace std;
int main(void)
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cout<<"Hello, World!"<<endl;
    return 0;
}

课后习题

N 个 A+B

本题是自编题。

题目描述

给定 N，接下来的 N 行每行两个整数 A、B，求 A+B，输出共 N 行。

输入样例

输出样例

1.7 一维数组

如果我们需要输入 10 个整数，并且输出它们的和，只用变量的话，我们就需要像 int a,b,c,d,e,f,g,h,i,j; 这样定义 10 个变量，非常麻烦。那么，如果可以把它们合并成一个长条，就方便多了。于是，C++ 里引进了数组的思想。

我们可以把数组看成这样的一个长条：

数组.png

我们在定义数组时，只需要在变量的基础上，在后面加速中括号并填上数组大小即可。如：定义一个长度为 10 的整型数组 A，就可以写作 int A[10]; ，如需访问一个值，就在中括号里写上下标位置即可。如输出 A 的第 6 个值，可以写作 cout<<A[5]。它的下标是0~9。

查找特定的值

洛谷 B2093

这道题我们可以使用顺序查找的方式，先看看数组的第0位（下标从零计）是不是目标值，如果是，输出下标。否则查找下一位。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int a[10005];//稍微开大一点
//数组尽量定义成全局变量（不要定义在函数里）
int n,x;
int main(void)
{
    cin>>n;
    for(int i=0;i<n;i++)//从0~n-1循环读入
        cin>>a[i];
    cin>>x;
    for(int i=0;i<n;i++)
    {
        if(a[i]==x)//找到了
        {
            cout<<i;
            return 0;//因为只需要找到第一个，所以找到后直接结束程序
        }
    }
    //遍历完数组后还是没有找到
    cout<<-1;
    return 0;
}

这样类型的题如果 n 太大的话（例如1 <= n <= 10^9），顺序查找就无法在指定时间内完成了（时间复杂度 O(n) ），对于一个有序的数组（单调递不增或单调不降），我们可以使用二分查找的方式解决，在后面会详细讲解。

课后习题

1.洛谷 B2089 数组逆序重存放

提示：此题可以使用两个循环变量实现，例如 for(int i=1,j=n;i<=n;i++,j--)

2.洛谷 B2104 矩阵加法

提示：此题需要循环嵌套（在一个循环里写循环）

二、基础算法

1.1 模拟算法

模拟是一种最基础的算法，它的策略是按照题目的要求，一步一步的进行模拟各个值的变化，从而获取答案。

Peter 的烟

洛谷 P1150

题目描述

Peter 有 n 根烟，他每吸完一根烟就把烟蒂保存起来，k(k > 1)个烟蒂可以换一个新的烟，那么 Peter 最终能吸到多少根烟呢？

与某些脑筋急转弯不同的是，Peter 并不能从异次元借到烟蒂，抽完后再还回去。

输入格式

每组测试数据一行包括两个整数 n,k (1 < n,k <= 1e8)。

输出格式

对于每组测试数据，输出一行包括一个整数表示最终烟的根数。

输入样例

4 3

输出样例

本题我们可以先吸一根烟，随后再检查一下能不能用烟蒂换一些烟，如果可以，就把烟蒂数清零，并且把烟的数量加 1，然后再抽一根烟……以此类推。

此处我们就需要刚才讲的循环了。

代码如下：

#include<iostream>
using namespace std;
int main(void)
{
    int n,k;
    cin>>n>>k;
    int num=0;//抽了的数量
    int m=0;//当前烟蒂数
    while(n>0)
    {
        //抽烟
        n--;
        num++;
        m++;
        //判断是否能换
        if(m==k)
        {
            n++;
            m=0;
        }
    }
    cout<<num;
    return 0;
}

#C++ #信息学 #算法

信息学奥赛算法大全

http://example.com/2023/04/22/信息学奥赛算法大全/

作者

DijkstraPhoenix

发布于

2023年4月22日

许可协议

洛谷[AT_agc006_f]Blackout题解上一篇

从0开始制作Minecraft模组下一篇