竞赛相关技巧

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

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

头文件

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

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

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

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

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

优点：

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

缺点：

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

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

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

命名空间

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

#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::，像下面这样。

#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++ 中标准的输入输出函数，用法也比较简单。

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

#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）。

#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 输出就稍微要麻烦一点，下面是一个例子，将输出结果保留小数点后两位。

#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() 来完成，代码如下：

#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 来换行。

cout << a << endl;

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

cout << a << "\n";

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

关于空白读入与输出

带空白字符串读入

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

#include <iostream>
using namespace std;

int main() {
    string s;
    getline(cin ,s);

    cout << s << endl;
    return 0;
}

多余空白处理

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

#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

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

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

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

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 中去。

#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 像下面这样来读入：

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

int main() {
  int x;

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

  return 0;
}

简化代码

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

typedef

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

例如：

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） 实际上是在编译之前进行处理，本质上是文本替换。

例如：

#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

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

#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

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

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，实际上相当于下面这样的代码：

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

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

易错示例2

#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 万大小的数组，就不能像下面这个去定义。

#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的大小，如果申请的空间超过剩余的可用空间大小时，就会报内存溢出错误。

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

#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 。通常有下面几种方式来完成。

定义时初始化

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

int a[n] = {0};

全局默认初始化

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

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

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

memset() 初始化方法

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

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

#include <cstring>

memset() 的函数原型是：

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

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

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

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

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

#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 循环来手动初始化数组元素相信很多同学都用过了，这种方式比较好理解，写起来也并不复杂。

int a[n];

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

浮点数的比较

（待补充）

执行效率估算

在竞赛中，对于程序执行效率的估算是一个必备的基础技能。

根据输入数据在大小量级来估算所期望的算法时间复杂度。

输入数据大小	期望的时间复杂度
$n \le 10$	$O(n!)$
$n \le 20$	$O(2^n)$
$n \le 500$	$O(n^3)$
$n \le 5000$	$O(n^2)$
$n \le 10^6$	$O(n log n)$ 或 $O(n)$

字符串与数字转换