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

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

C++ Introductory Explosion Proof Zero Tutorial（Volume \(1\)）

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

编写时间：\(2023.10.5 \sim ?\)

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

出版社：美公鸡出版社

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 }\) 头文件和 \(\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 }\)	极高

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\) 快读快写（不推荐，比较麻烦）

模板：

快读：

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;
}

快写：

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{......}\)

完整代码：

#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\)。

输入样例：

6 12
4 5 7 6 3 5 6

输出样例：

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)\)）。

代码：

#include 
#include 
#include 
#include 

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！

代码：

#include 
#include 
#include 
#include 

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, !8]\)。

第 \(2\) 次：\(7\) 最大，与 \(4\) 交换位置，\([5, 7, 2, 4, !8] \gets [5, 4, 2, !7, !8]\)。

第 \(3\) 次：\(5\) 最大，与 \(2\) 交换位置，\([5, 4, 2, !7, !8] \gets[2, 4, !5, !7, !8]\)。

第 \(4\) 次：\(4\) 最大，与 \(4\) 交换位置，\([2, 4, !5, !7, !8] \gets[2, !4, !5, !7, !8]\)。

排序后：\([2, 4, 5, 7, 8]\)。

代码：

#include 
#include 
#include 
#include 

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;
}

未完待续