---
title: "竞赛相关技巧"
description: "竞赛技巧与复杂度估算等实战经验。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 竞赛相关技巧

![](https://img.dailyup.xyz/originals/8208462189589-932ce11e-8bc3-4617-b14f-6660b3f80c3b.png)

这里主要介绍一些与竞赛直接相关的技巧与用法，有些内容在每个主题的介绍内容中可能已经有讲到，但单独提出来方便查阅。

掌握这些技巧，可以避免一些坑，降低在竞赛中犯错的机率，但需要说明的是，**竞赛与工程的目标还是不一样，因此这些在竞赛中的技巧和用法，并不是都适用于在工程中使用，甚至有一些在竞赛中的建议与在工程中的建议刚好相反**。我们这里讨论的主要是针对信息学竞赛，当然也尽可能会介绍到为什么要这样用？适用的范围是什么。

## 头文件

每一类功能函数，都有对应的头文件，比如下面是几个比较常见的头文件：

```cpp
#include <iostream> // C++ 标准输入输入库
#include <cstdio> // 在 C++ 中使用 C 风格的输入输出库
#include <cmath> // 在 C++ 中使用 C 风格的数学库
#include <algorithm> // STL 中的算法库
#include <vector> // STL 中的 vector 容器
```

在竞赛中，有可能一下记不住要引入的头文件名称，可以使用一个万能头文件，该文件几乎包括了所有库函数的头文件，基本各大主流的 oj 平台也都是支持的。

```cpp
#include <bits/stdc++.h> // 万能头文件
```

既然有了万能头文件，那何必再像前面那样单独会引入呢，又麻烦又容易出错。了解使用万能头文件的优缺点对我们学习者来说是有必要的。

**优点：**

- 适合竞赛中使用，减少录入头文件的工作量，节约时间

**缺点：**

- 将包含没必要引入的库，这样会增加编译时间
- 万能头文件并不属于 C++ 标准的一部分，不可移植，在部分情况下也可能会失效


> 万能头文件适合在竞赛中使用，但在工程中应当避免使用。


在这份编程学习指南中，我们会根据需要来引入不同的头文件，从学习的角度来说这样更好。

## 命名空间

对于每一个初学 C++ 的人来说，像下面这样使用标准命名空间的方式应该是非常熟悉了。

```cpp
#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    cout << a + b << endl;
    return 0;
}
```

正是因为有第 2 行的命名空间说明，后面才可以直接使用 `cin` 和`cout`，没有 第 2 行，我们需要在所有 `cin` 和 `cout` 前加前缀 `std::`，像下面这样。

```cpp
#include <iostream>

int main() {
    int a, b;
    std::cin >> a >> b;
    std::cout << a + b << endl;
    return 0;
}
```

在竞赛中直接先进行命名空间说明当然更好一些的，在竞赛中一份源文件功能是比较单一的，几乎不会遇到有不同来源的同名函数出现，这样写方便且大大节约了输入的时间；

而在工程实践中，一个文件往往是多人协作，而且文件中往往包括大量不同来源的函数，很有可能会遇到同名的函数出现，因此单独以前缀的方式去写有时反而是推荐的。

## 数据的输入与输出

- `cin / cout`
- `scanf() / printf()`
- 空白读入与输出

### `cin / cout`

这是 C++ 中标准的输入输出函数，用法也比较简单。

下面的示例从外部输入两个整数，计算两个数的和并输出。

```cpp
#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    
    cout << "a+b=" << a + b << endl;
    return 0;
}
```

输入：

```
3 4
```

输出：

```
a+b=7
```

初学时要注意 `cin` 与 `cout` 箭头的方向，另外，由于这是标准的输入输出流，因此可以向上面例子中那样连续多个读入与输出。

**竞赛提示：效率优化**

在竞赛中，如果使用 `cin` 与 `cout` 进行输入输出，记着要在 `main()` 函数里开头加上下面这行优化的代码，不然容易超时（ `TLE` ，Time Limit Exceed）。

```cpp
#include <iostream>
using namespace std;

int main() {
    // IO 优化的代码，放在开头位置
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // 你自己的逻辑代码
    return 0;
}
```

这样使用后，会大幅度提升 `cin / cout` 输入输出的效率。

需要注意的是，优化后就不能与 `scanf() / printf()` 混用了。当然，为了简便，在竞赛题目中可能涉及到读取效率的问题时，建议直接使用 `scanf()` 和 `printf()`。

**竞赛提示：保留小数点位数**

如果在题目中遇到希望保留结果小数几位的明确要求，使用 `cout` 输出就稍微要麻烦一点，下面是一个例子，**将输出结果保留小数点后两位**。

```cpp
#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    const float PI = 3.1415926;
    cout << fixed << setprecision(2) << PI << endl;
    return 0;
}
```

输入结果为：

```
3.14
```

在使用 `cout` 带精度输出时，需要两点：

- 保留小数点后几位，一定要 `fixed` 与 `setprecision()` 配合使用，单独使用 `setprecision()` 保留的位数代表除开小数点共几位（包括小数点前的位数），而加上 `fixed` ，表示按小数后的位数计算。
- 需要加入头文件 `#include <iomanip>` 

### `scanf() / printf()`

对于带精度的格式化输出来说，C 风格的 `printf()` 更擅长，对于大数据的读入来说，`scanf()` 效率也更高，因此大家在看一些竞赛代码时，会发现 `scanf() / printf()` 的使用率反而更高一些。

上面同样保留小数后几位的例子，用 `printf()` 来完成，代码如下：

```cpp
#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    const float PI = 3.1415926;
    printf("%.2f\n", PI);
    
    return 0;
}
```

有两处变动，稍作解释：

- 第 2 行：使用 `scanf() / printf()` 需要引入 `<cstdio>` 头文件
- 第 6 行：`.2f` 指对于浮点数保留到小数点后两位；`\n` 是换行

关于 `scant() / printf()` 更详细的用法与解释，请见输入输出章节。

### 关于换行

在使用 `cout` 输出时，通常在行末配合使用 `endl` 来换行。

```cpp
cout << a << endl;
```

也可以使用 `"\n"` 来换行。

```cpp
cout << a << "\n";
```

由于 `endl` 相比 `"\n"` 在输出时做了更多的细节处理，在工程中使用更方便和安全；而在竞赛中，`"\n"` 的使用频率却更高，这是因为它的效率更高一些。

### 关于空白读入与输出

**带空白字符串读入**

如果要输入带空白字符串，建议使用 `getline()`，其字面意义就是按行去读入。

```cpp
#include <iostream>
using namespace std;

int main() {
    string s;
    getline(cin ,s);
    
    cout << s << endl;
    return 0;
}
```

**多余空白处理**

这一点要小心，比如说题目要求我们将结果数组 a 的 n 个元素输出，元素之间用空格隔开，习惯性会这样写。

```cpp
#include <iostream>
using namespace std;

int main() {
  
    for (int i = 0; i < n; i ++) {
      cout << a[i] << " ";
    }
    
    return 0;
}
```

输出结果为：

```
1 2 3 4 5 
```

看起来结果也没什么问题，但提交代码时，会得到 **PE（Presentation Error 格式错误）** 或 **WA （Wrong Answer 答案错误）**。

这是因为虽然数字看上去没问题，但在最行末多了一个空格，如果我们将空格换成下划线来显示就容易看出来。

```
1_2_3_4_5_
```

而题目的要求是

```
1_2_3_4_5
```

换行有同样的问题，那这种问题一般怎么解决呢，有很多方法，最简单的方法则是判断如果是最后一个元素则后面不用加空格。

```cpp
for (int i = 0; i < n; i++) {
  if (i == n - 1) cout << a[i]; // 最后一个元素后不加空格
  else cout << a[i] << " ";
}
```

也可以**设定一个标志位，除第一个元素外，在输出其它元素前都加一个空格**。

```cpp
bool is_first = true; // 代表第一个元素的标志位
    
for (int i = 0; i < n; i++) {
  if (!is_first) cout << " ";
  is_first = false;
  cout << a[i];
}
```

### 读入多行数据

如果题目是明确指定了要读入的数据数量，直接用 `for` 循环去读入即可。

例如，对于下面的输入
```
5
1 2 5 6 8
```

其中第一行为 n ，代表接下来要读入 n 个数，我们可以通过下面的方法直接将数据读入到一个一维数组 q 中去。

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, q[110];
  cin >> n;
  
  for (int i = 0; i < n; i ++) cin >> q[i];
  
  return 0;
}
```

如果要读入的数据数量并不知道呢？

例如，对于下面的输入

```
1 2 5 6 8
```

数据的数量我们并不知道，这里是 5 个元素，也可能是其它的数量，我们只知道，最多不超过 100 个数据。

这时我们可以用 `while` 像下面这样来读入：

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
  int x;  
  
  while (cin >> x) { // 遇到空白后自动停止读入
    cout << x << endl;
  }
  
  return 0;
}
```

## 简化代码

通常来说，我们可以使用 `typedef` 和 `macros` 来简化代码。

### typedef

typedef 是 C++ 中用于创建类型别名的关键字。它允许我们为现有的数据类型创建一个新的名称，使代码更易读、更易维护。

例如：

```cpp
typedef long long ll;
typedef vector<int> vi;

ll a = 123456789; // 可以用 ll 来定义长整型变量
vi v; // 可以用 vi 来定义向量
```

在这个例子中，我们为 `long long` 和 `vector<int>` 类型创建了别名，分别是 `ll` 和 `vi`，这样在程序中其它地方要用到长整型或向量的定义，就可以用 `ll` 和 `vi` 来替代了。


### macros

宏（macros）是 C++ 预处理器提供的一种强大工具，也可以用来简化代码、提高可读性和可维护性。

> 宏（macros） 实际上是在编译之前进行处理，本质上是文本替换。

例如：

```cpp
#include <bits/stdc++.h>
using namespace std;

#define MAX(a, b) ((a) > (b) ? (a) : (b)) 
#define SQUARE(x) ((x) * (x))


int main() {
  int a = 5, b = 8;
  cout << MAX(a, y) << endl;
  cout << SQUARE(a) << endl;
  
  return 0;
}
```

在上面的例子中，`MAX` 和 `SQUARE` 是函数宏。它们在使用时会被展开为相应的表达式。

当然，宏还有一些其它的高级应用方式（如用于条件编译），这里就不展开讲解了，感兴趣的可以去检索相关资料。

需要注意的是，typedef 和宏（macros）都可以用来简化代码，但它们本质上有很大的区别，下列举了几点不同之处：

- `typedef` 是在编译阶段处理；而 `macros` 在预处理阶段（编译前）处理
- `typedef` 创建了真正的类型别名；而 `macros` 本质上只是文本替换
- `typedef` 提供了完整的类型检查，编译器可以捕获类型错误；而 `macros` 不提供类型检查，可能导致意外的行为或错误
- `typedef` 遵循正常的作用域规则，可以在局部作用域中定义；而 `macros` 没有作用域限制，一旦定义就在整个文件夹中有效
- `typedef` 只能创建类型别名；而 `macros` 可以定义表达式或语句块，甚至使用参数

## 布尔变量与条件判断

布尔变量和条件判断是编程中非常重要的基础知识，但其中有一些细节和陷阱，初学者和一些有经验的程序员都可能会忽略。我们来深入探讨这些易错点，并通过示例加以说明。

### 布尔值的内部表示

在C++中，布尔类型 (`bool`) 有两个取值：`true` 和 `false`。但是，它们在内部是如何表示的呢？

- `true` 在内部表示为 `1`
- `false` 在内部表示为 `0`

### 非布尔类型的条件判断

在C++中，条件判断不仅仅局限于 `bool` 类型。任何非 `0` 的数都被解释为 `true`，而 `0` 被解释为 `false`。这意味着我们可以在条件判断中使用整数、浮点数等非布尔类型的数据。

下面通过几个例子来看看易错的地方。

#### 易错示例1

大家先阅读一下下面这个程序，该程序运行后会输出什么样的结果呢？

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n = 9;
  
  if (n % 3) {
    cout << "yes" << endl;
  } else {
    cout << "no" << endl;
  }
  
  return 0;
}
```

正确的输出结果是：no

初学者很容易判断失误，我们平时判断一个数是否能被另一个数整除，通常是这样的：

```cpp
if (n % 3 == 0) {
  cout << "yes" << endl;
} else {
  cout << "no" << endl;
}
```

上面是一个比较运算符，判断 n 除以 3 的余数是不是等于 0，由于 9 除以 3 的余数是 0，因此这个条件判断 `n % 3 == 0` 的结果是成立的（结果为 true），因此输出 yes。

而在前面的代码中，并不是判断是否等于 0，只是一个计算 `n % 3` ，余数应该是 0，实际上相当于下面这样的代码：

```cpp
if (0) {
  cout << "yes" << endl;
} else {
  cout << "no" << endl;
}
```

当然条件判断就不成立了，应该输出 no ，很容易出错。

#### 易错示例2

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n = 9;
  
  if (n = 3) {
    cout << "yes" << endl;
  } else {
    cout << "no" << endl;
  }
  
  return 0;
}
```

运行程序，正确输出应该是 yes。初学者晃眼一看，以为是判断变量 n 的值是否等于 3，当然是不等的，因此很容易得出错误的输出结果 no。

实际上，这是一种初学者容易犯的赋值错误，错误地使用 `=` 代替 `==`，导致赋值操作而不是比较操作。这里不管 n 是多少，`n = 3` 都会将 n 的值设置为 3，因此条件判断的结果始终是 `true`，因此程序会输出 yes。

## 数组的定义

在竞赛中，如果有遇到要定义一个超大位数的数组，比如要定义一个 1000 万大小的数组，就不能像下面这个去定义。

```cpp
#include <iostream>
using namespace std;

int main() {
    int a[10000000]; 
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) cin >> a[i];
    
    for (int i = 0; i < n; i ++) cout << a[i] << " ";
    return 0;
}
```

像上面第 5 行这样放到 `main()` 函数里，编译时很可能就会出现 MLE（Memory Limit Exceed 内在溢出）错误。

这是由于这里的数组 a 其实是一个局部变量，**局部变量是存放在栈区（Stack Segment）里的，而栈区的大小通常是由操作系统预先规定好的，通常只有几M的大小，如果申请的空间超过剩余的可用空间大小时，就会报内存溢出错误**。

因此如果遇到需要开一个很大的数组，我们**最好是放到全局变量中去**，下面是一个简单的示例。

```cpp
#include <iostream>
using namespace std;

const int MAX_LEN = 1e7 + 10; // 全局变量，科学计数法表式，多申请 10 个
int a[MAX_LEN];

int main() {
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) cin >> a[i];
    
    for (int i = 0; i < n; i ++) cout << a[i] << " ";
    
    return 0;
}
```

## 数组元素初始化

在使用数组时，经常会涉及数组数据的初始化及赋值问题。

比如说，要将整型数组 `a` 的所有元素初始化为 0 。通常有下面几种方式来完成。

### 定义时初始化

正常定义，在定义同时，立即初始化：

```cpp
int a[n] = {0};
```

### 全局默认初始化

如果数组定义为全局变量，默认情况下，编译器会根据类型来进行初始化。

```cpp
int a[n]; // int 类型数组，所有元素默认初始化为 0

int main() {
  // 主函数内容
}
```

### memset() 初始化方法

C++ 提供了专门用于初始化的函数`memset()`，关于它的使用重点说一说，因为容易用错。

要使用 `memset()` 函数，需要引入头文件：

```cpp
#include <cstring>
```



`memset()` 的函数原型是：

```cpp
void *memset(void *s , int ch , size_t n)
```

函数的作用是：将已经开辟内存空间的 `s` 的前 `n` 个字节的值设为 `ch`。需要注意，这里的 `n` 代表 n 个字节。

```cpp
int a[n];
memset(a, 0, sizeof(a));
```

注意，`sizeof()` 是返回一个对象或类型所占据的字节数，因此只有当初始化为 0 的时候才能这样用。

如果要将数组元素全部初始化为 1，下面这样写就有问题了。

```cpp
#include <iostream>
#include <cstring>
using namespace std;

int main() {
    int a[100];
    memset(a, 1, sizeof(a));
    
    cout << a[0] << endl;
    
    return 0;
}
```

**程序运行结果**

```
16843009
```

上面的代码（第 7 行）只是将每个字节初始化为 1，而一个 `int` 是 4 个字节，显然，这段代码并不能将 `int` 变量初始化为 1 。而是将每个字节初始化为 1 了。

```
00000001 00000001 00000001 00000001
```

上面的二进制转换为十进制刚好是 16843009 。

>  **实际上，使用 `memset()` 初始化对 `0` 和 `-1` 才有效。因为 0 的二进制表示中，所有位都是 0；-1 的二进制表示中，所有位都为 1 。**

除此之外，**`memset()` 更常用到的是对 `char` 类型的数组元素进行初始化**，这是因为在 C++ 中，每一个 `char` 都刚好占据一个字节的空间，而 `memset()` 的初始化也是按字节来进行的，匹配得很好。

### 用循环来手动初始化

使用 `for` 循环来手动初始化数组元素相信很多同学都用过了，这种方式比较好理解，写起来也并不复杂。

```cpp
int a[n];

for (int i = 0; i < n; i++) {
  a[i] = 1; // 将数组元素初始化为 1
}
```

## 浮点数的比较

（待补充）

Source: https://cppguide.xyz/competition/tips/index.mdx