526互联

C++ 入门防爆零教程（上册）

发布时间 2023-11-06 21:59:20作者: beautiful_chicken233
## C++ 入门防爆零教程（上册）

######  C++ Introductory Explosion Proof Zero Tutorial（Volume $1$）

编写者：美公鸡（洛谷账号：beautiful_chicken233，电话：$155****7747$，如有需要请随时联系）

编写时间：$2023.10.5 \sim ?$

地址：湖南省长沙市雨花区明升异城 $11$ 栋 $3902$

出版社：美公鸡出版社

价格：$0.38$ 元

### Part $0$ 目录

###### Directory

##### Part $1$ 赛时注意事项

###### $...$ Part $1.1$ 文件读写

$.....$ Part $1.1.1$ $\texttt{freopen}$

$.....$ Part $1.1.2$ $\texttt{fstream}$

$.....$ Part $1.1.3$ $\texttt{fopen}$

###### $...$ Part $1.2$ 源程序的存放

###### $...$ Part $1.3$ 恶意程序

###### $...$ Part $1.4$ 卡常

$.....$ Part $1.4.1$ 关闭同步流

$.....$ Part $1.4.2$ 关闭缓冲区自动刷新

$.....$ Part $1.4.3$ 快读快写

$.....$ Part $1.4.4$ 底层优化

##### Part $2$ 算法

###### $...$ Part $2.1$ 时间 & 空间复杂度

$.....$ Part $2.1.1$ 时间复杂度

$.....$ Part $2.1.2$ 空间复杂度

###### $...$ Part $2.2$ 枚举

###### $...$ Part $2.3$ 模拟

###### $...$ Part $2.4$ 排序

$.....$ Part $2.4.1$ 选择排序

###  Part $1$ 赛时注意事项

###### Games-time precautions

#### Part $1.1$ 文件读写

在 CSP 等重大比赛中，最重要的就是文件读写，在每一年都有许多竞赛选手因为文件读写而爆零。而文件读写都很多类，比如 `freopen` 等等。下面介绍的是 $3$ 种常用的文件读写。

##### Part $1.1.1$ $\texttt{freopen}$

在程序中加上 $\texttt{freopen("xxx.in/out", "r/w", stdin/stdout);}$ 之后，程序就会从 $\texttt{xxx.in}$ 中读取输入文件，在 $\texttt{xxx.out}$ 中输出。

##### Part $1.1.2$ $\texttt{fstream}$

首先需要在主函数外面定义 $\texttt{\#include <fstream>}$ 头文件和 $\texttt{ifstream fin("xxx.in")}$ 和 $\texttt{ifstream fout("xxx.out")}$。然后在程序中要文件读写的写成 $\texttt{fin}$ 和 $\texttt{fout}$ 即可。

##### Part $1.1.3$ $\texttt{fopen}$

首先要定义 $\texttt{FILE *file = fopen("xxx.in", "r+/w+")}$。然后在程序中使用 $\texttt{fscanf(file, "", ...)}$ 和 $\texttt{fprintf()}$ 即可。

#### Part $1.2$ 源程序的存放

在比赛中，源程序的存放是比较重要的，源程序的错误存放会导致失去分数。

一般的存放结构如下：

$\texttt{|-your name (folder)}$

$\texttt{|---T1 name (folder)}$

$\texttt{|------T1 name.cpp}$

$\texttt{|---T2 name (folder)}$

$\texttt{|------T2 name.cpp}$

$\texttt{|---T3 name (folder)}$

$\texttt{|------T3 name.cpp}$

$\texttt{|---T4 name (folder)}$

$\texttt{|------T4 name.cpp}$

#### Part $1.3$ 恶意程序

在比赛中，恶意程序的分数会变为 $0$，且会有相应的惩罚，**一定不要做**。

恶意程序的杀伤力如下表：

| 代码 | 杀伤力 |
| :-----------: | :-----------: |
| $\texttt{while (1) \& Sleep()}$ | 低 |
| $\texttt{system("")}$ | 中 $\sim$ 高 |
| $\texttt{\#include <con>}$ | 极高 |


### Part $1.4$ 卡常

##### Part $1.4.1$ 关闭同步流

C++ 的输入输出的缓冲区和 C 是同步的，我们可以用 $\texttt{ios::sync\_with\_stdio(0)}$ 关闭同步流而加快速度。

##### Part $1.4.2$ 关闭缓冲区自动刷新

程序会在输入和输出时刷新缓冲区（特别是 `endl`，想快一点就用 `'\n'`），我们可以用 $\texttt{cin.tie(0), cout.tie(0)}$ 关闭缓冲区自动刷新而加快速度。

##### Part $1.4.3$ 快读快写（不推荐，比较麻烦）

**模板：**

快读：

```cpp
int read() {
  int s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    (ch == '-') && (f = -1), ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = (s << 1 + s << 3) + ch - '0', ch = getchar();
  }
  return s * f;
}

```

快写：

```cpp
void write(int x) {
  (x < 0) && (putchar('-')) && (x = -x);
  if (x > 9) {
    write(x / 10);
  }
  putchar(x % 10 + '0');
}
```

##### Part $1.4.4$ 底层优化

**循环展开：**

恰当的循环展开可以让 CPU 多线程进行并发运算，可以提升速度。但是不恰当的循环展开可能会起副作用。

展开前：

$\texttt{for (int i = 1; i <= 300; ++ i) \{}$

$\texttt{  ans += i;}$

$\texttt{\}}$

展开后：

$\texttt{for (int i = 1; i <= 300; i += 6) \{}$

$\texttt{  ans += i;}$

$\texttt{  ans += i + 1;}$

$\texttt{  ......}$

$\texttt{  ans += i + 6;}$

$\texttt{\}}$

**火车头（指令优化）：**

Tips：**NOI 禁止。**

$\texttt{\#pragma GCC optimize(3)}$
$\texttt{\#pragma GCC target("avx")}$
$\texttt{\#pragma GCC optimize("Ofast")}$
$\texttt{\#pragma GCC optimize("inline")}$
$\texttt{\#pragma GCC optimize("-fgcse")}$
$\texttt{......}$

完整代码：

```cpp
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
```


###  Part $2$ 算法

######  Algorithm

#### Part $2.1$ 时间 & 空间复杂度

##### Part $2.1.1$ 时间复杂度

人们将程序运行次数的量级以及空间的量级成为时空复杂度，用大 $O$ 表示，一般会忽略常数。现代评测机大约每秒能够运行 $2 \times 10^7 \sim 10^9$ 次，但是使用了数组就比较慢了。需要**格外注意**你的时间复杂度是否都在题目限制以内。

**时间复杂度表：**

| 时间复杂度 | 少爷评测机 | 老爷评测机 |
| :-----------: | :-----------: | :-----------: |
| $O(\log n)$ | $2^{10^9}$ | $2^{2 \times 10^7}$ |
| $O(\sqrt n)$ | $10^{18}$ | $4 \times 10^{14}$ |
| $O(\log n\sqrt n)$ | $5 \times 10^{14}$ | $3 \times 10^{11}$ |
| $O(n^{\frac{3}{4}})$ | $10^{12}$ | $5 \times 10^9$ |
| $O(n)$ | $10^9$ | $2 \times 10^7$ |
| $O(n \log \log n)$ | $4 \times 10^8$ | $5 \times 10^6$ |
| $O(n \log n)$ | $4 \times 10^7$ | $10^6$ |
| $O(n \sqrt n)$ | $10^6$ | $8 \times 10^4$ |
| $O(n^2)$ | $3 \times 10^4$ | $5000$ |
| $O(n^2 \log n)$ | $9000$ | $1500$ |
| $O(n^2 \sqrt n)$ | $4000$ | $1000$ |
| $O(n^3)$ | $1000$ | $300$ |
| $O(n^4)$ | $150$ | $80$ |
| $O(n^5)$ | $60$ | $30$ |
| $O(2^n)$ | $30$ | $25$ |
| $O(2^n \times n)$ | $25$ | $20$ |
| $O(n!)$ | $12$ | $10$ |
| $O(n! \times n)$ | $11$ | $9$ |
| $O(n^n)$ | $9$ | $8$ |

**常用时间复杂度排序：**

$O(1) < O(\log n) < O(\sqrt n) < O(n) < O(n \log n) < O(n \sqrt n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$

##### Part $2.1.2$ 空间复杂度

类似地，算法所使用的空间随输入规模变化的趋势可以用空间复杂度来衡量。

如，开一个长度为 $n$ 的数组，那么空间复杂度是 $O(n)$。开一个长度为 $n \times n$ 的二维数组，那么空间复杂度是 $O(n^2)$。开一个长度为 $n \times 3$ 的二维数组或 $3$ 个长度为 $n$ 的数组，那么空间复杂度是 $O(3n)$。开一个长度为 $n$ 的数组和一个长度为 $m$ 的数组，那么空间复杂度是 $O(n + m)$。

#### Part $2.2$ 枚举

枚举的思想是不断地猜测，从可能的集合中一一尝试，然后再判断题目的条件是否成立。但是并非所有的情况都要枚举，有时要适当的进行一些剪枝。（如枚举 $a + b = c$ 且 $b > a$ 的个数那么 $b$ 要从 $a + 1$ 开始枚举）。

**例题：**

给出 $n$ 个数 $a_1, a_2, \cdots, a_n$ 和 $x$，求有多少对 $i, j$ 满足 $a_i + a_j = x$ 且 $j > i$。

输入样例：

```cpp
6 12
4 5 7 6 3 5 6
```

输出样例：

```cpp
2
```

数据范围：$1 \le n \le 10^3$，$1 \le x, a_i \le 10^9$。

分析：

我们可以先枚举 $i$，从 $1$ 枚举到 $n$。每次枚举到一个 $i$ 时枚举 $j$，从 $i + 1$ 枚举到 $n$（因为 $j > i$）。每枚举到一个 $i, j$ 时判断条件 $a_i + a_j = x$，如果满足把答案 $+1$。时间复杂度 $O(n^2)$。（准确来说是 $O\Big(\dfrac{n^2 - n}{2}\Big)$）。

代码：

```cpp
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

using ll = long long;

const int kMaxN = 1010, kInf = (((1 << 30) - 1) << 1) + 1;

int n, x, a[kMaxN], ans = 0; // ans 是满足条件的个数

int main() {
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
  cin >> n >> x; // 输入 n, x
  for (int i = 1; i <= n; ++ i) {
    cin >> a[i]; // 输入 ai
  }
  for (int i = 1; i <= n; ++ i) { // 枚举 i，范围 1 至 n
    for (int j = i + 1; j <= n; ++ j) { // 枚举 j，范围 i + 1 至 n
      (a[i] + a[j] == x) && (++ ans); // 如果 ai + aj = x，那么答案 +1（if 压缩）
    }
  }
  cout << ans << '\n'; // 输出答案
  return 0;
}
```

#### Part $2.3$ 模拟

模拟就是用代码模拟出题目所要求的操作。虽然本质上比较简单，但是码量大，很难调错。所以做模拟题的时候一定要先构思好再敲代码。

**例题：**

小蓝要和朋友合作开发一个时间显示的网站。在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从 $1970$ 年 $1$ 月 $1$ 日 $00:00:00$ 到当前时刻经过的毫秒数。

现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。

给定一个用整数表示的时间，请将这个时间对应的时分秒输出。

数据范围：给定的时间不超过 $10^{18}$。

分析：

我们直接把输入的时间 $t$ 除以 $1000$ 变成秒（毫秒和秒之间的进率为 $1000$）。然后再时间转换，天为 $t \bmod (60^2 \times 24) \div 60^2$，小时为 $t \bmod (60^2 \times 24) \bmod 60^2 \div 60$，分钟为 $t \bmod (60^2 \times 24) \bmod 60$。这里为了方便，我们定义 $d = 60^2 \times 24$，$h = 60^2$，$m = 60$。时间复杂度 $O(1)$。注意，一定要开 `long long`！

代码：

```cpp
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

using ll = long long;

const int kMaxN = -1, kInf = (((1 << 30) - 1) << 1) + 1;
const ll d = 24 * 60 * 60, h = 60 * 60, m = 60; // 定义常量 d, h, m

int main() {
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
  ll t;
  cin >> t; // 输入 t
  t /= 1000; // 把 t 除以 1000（把毫秒转换成秒）
  ll day = t % d / h, hour = t % d % h / m, _min_ = t % d % m;
  // 计算天，小时，分钟（注意这里 min 只能定义成 _min_）
  printf("%02d:%02d:%02d", day, hour, _min_); // 输出，格式为 dd:hh:mm
  return 0;
}
```

#### Part $2.4$ 排序

**凉心提醒：这一章比较长。**

排序就是将一个无序的序列排成有序的算法，下面为各个排序的性质：

| 排序算法 | 时间复杂度 | 空间复杂度 | 稳定性 | 特殊性质 |
| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |
| 选择排序 | $O(n^2)$ | $O(1)$ | 否 | 可以通过额外的 $O(n)$ 空间达到稳定 |
| 冒泡排序 | $O(n) \sim O(n^2)$ | $O(1)$ | 是 | 有序时速度快，可以进行剪枝 |
| 插入排序 | $O(n) \sim O(n^2)$ | $O(1)$ | 是 | 当 $n$ 较小时速度很快 |
| 快速排序 | $O(n \log n) \sim O(n^2)$ | $O(\log n) \sim O(n)$ | 否 | 最快的排序，有序时退化到平方级 |
| 归并排序 | $O(n \log n)$ | $O(n)$ | 是 | 不易被卡，很稳定 |
| 希尔排序 | $O(n) \sim O(n^2)$ | $O(1)$ | 否 | 是插入排序改进而来的排序 |
| 堆排序 | $O(n \log n)$ | $O(1)$ | 否 | 常数较大 |
| 桶排序 | $O(\max^{n}_{i = 1} a_i)$ | $O(n + m)$ | 是 | 空间比较大 |
| 基数排序 | $O(d(r + n))$ | $O(rd + n)$ | 是 | 非比较排序 |
| 计数排序 | $O(n + k)$ | $O(k)$ | 是 | 非比较排序 |

##### Part $2.4.1$ 选择排序

选择排序的思想就是在无序区里找到最大值，然后与无序区的最后一个交换位置，再把无序区的最后一个变成有序区。当有序区有 $n - 1$ 个元素时，排序完成。

例：（绿色代表有序区）

初始：$[5, 7, 2, 8, 4]$

第 $1$ 次：$8$ 最大，与 $4$ 交换位置，$[5, 7, 2, 8, 4] \gets [5, 7, 2, 4, \green{8}]$。

第 $2$ 次：$7$ 最大，与 $4$ 交换位置，$[5, 7, 2, 4, \green{8}] \gets [5, 4, 2, \green{7}, \green{8}]$。

第 $3$ 次：$5$ 最大，与 $2$ 交换位置，$[5, 4, 2, \green{7}, \green{8}] \gets[2, 4, \green{5}, \green{7}, \green{8}]$。

第 $4$ 次：$4$ 最大，与 $4$ 交换位置，$[2, 4, \green{5}, \green{7}, \green{8}] \gets[2, \green{4}, \green{5}, \green{7}, \green{8}]$。

排序后：$[2, 4, 5, 7, 8]$。

代码：

```cpp
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

using ll = long long;

const int kMaxN = 5050, kInf = (((1 << 30) - 1) << 1) + 1;

int n, a[kMaxN]; // 定义 n 和 a 数组

int main() {
  cin >> n; // 输入 n
  for (int i = 1; i <= n; ++ i) {
    cin >> a[i]; // 输入 ai
  }
  int maxa = -1e9, idx = 0; // 存最大值，idx 是下标
  for (int i = n; i >= 2; -- i) {
    maxa = -1e9; // 每次取最大值前要把 maxa 赋值成极小值
    for (int j = 1; j <= i; ++ j) { // 枚举最大值
      if (a[j] >= maxa) { // 如果大于等于最大值
        maxa = a[j], idx = j; // 更新最大值
      }
    }
    swap(a[idx], a[i]); // 交换位置
  }
  for (int i = 1; i <= n; ++ i) {
    cout << a[i] << ' '; // 输出
  }
  cout << '\n';
  return 0;
}
```