首页 > 编程语言 >C++ 入门防爆零教程（上册）

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

时间：2023-11-07 22:00:42浏览次数：50  
标签：10 GCC texttt C++ 上册 防爆 Part pragma optimize

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

模板：

快读：

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 <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！

代码：

#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, !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 <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;
}

未完待续

标签：10,GCC,texttt,C++,上册,防爆,Part,pragma,optimize
From： https://www.cnblogs.com/bc2qwq/p/17816144.html

相关文章

  • 关于C++中STL的简单入门（updating）
    前言：本篇文章将对STL（标准模板库）进行一个简单的介绍，以方便在算法竞赛中节省时间并方便使用。C++STL（标准模板库）是一套功能强大的C++模板类，提供了通用的模板类和函数，这些模板类和函数可以实现多种流行和常用的算法和数据结构，如向量、链表、队列、栈。C++标准模板库的核心包括以......
  • 【Cpp 语言基础】C++中的 getline() 函数
    一、string类的getline函数（全局函数）getline(cin,str)函数是处理string类的函数。第二个参数为string类型的变量。读入时第二个参数为string类型，而不是char*，要注意区别     getline（）函数的定义如下所示    1.istream&getline(istream&is,string&str,ch......
  • C/C++ __builtin 超实用位运算函数总结
    以__builtin开头的函数，是一种相当神奇的位运算函数，下面本人盘点了一下这些以__builtin开头的函数，希望可以帮到大家。1__builtin_ctz()/__buitlin_ctzll()用法:返回括号内数的二进制表示数末尾0的个数//eg:#include<bits/stdc++.h>usingnamespacestd;intmain......
  • c++右值引用、移动语义、完美转发
    1. 左值、右值、左值引用以及右值引用左值：一般指的是在内存中有对应的存储单元的值，最常见的就是程序中创建的变量右值：和左值相反，一般指的是没有对应存储单元的值（寄存器中的立即数，中间结果等），例如一个常量，或者表达式计算的临时变量intx=10inty=20intz=x+y//x......
  • Windows10+VSCode+CMake+shell脚本编译C/C++程序
    一、概述想要在Windows10上做C++验证/编译类库，借助VSCode（其实这东西要不要都行，它就是来方便查看代码的）+CMake+shell脚本做程序的编译运行。下面写一个小例子记录一下准备工作：1.编译环境用的是mingw64，使用其再带的g++编译，ps：记得要配置其环境变量2......
  • 【01】安装与配置 C++/Visual Studio 22 | PDCurses on Windows
    参考：https://www.cnblogs.com/yapingxin/p/15936414.html实践、概括、优化：编译生成下载源码，解压后进入其中的wincon目录；如果需要为多个Platform（x86和x64）以及多个分支（Debug和Release），多复制备份几个wincon文件夹，分别命名好；编辑其中的Makefile.vc文件，在11行下新建一行，写入：PL......
  • 11 个最佳 C++ IDE（和代码编辑器）
    C++是一种功能强大、用途广泛的编程语言。它也可以是一个艰难的大师。这意味着在您的工具带中拥有正确的工具以帮助您更高效、更有效、更自信地编写代码至关重要。在为C++编程寻找最佳IDE或代码编辑器时，您应该从哪里开始？IDE选项列表几乎是无限的，很难判断哪个是最适合您的软......
  • C++中的高阶函数 -- std::function实现回调
    C++中的高阶函数：以std::function优雅地实现回调1.简介1.1C++高阶函数的概念在函数式编程语言中，高阶函数（Higher-orderFunction）是一个常见的概念，它通常被定义为满足下列条件之一的函数： 接受一个或多个函数作为输入（参数）输出（返回值）是一个函数C++作为一门多范式编程语言，也......
  • C++ lambda函数总结
    C++lambda函数1lambda函数简介名称lambda来自lambdacalculus(lambda演算)，一种定义和应用函数的数学系统。这个系统中可以使用匿名函数，对于接收函数指针或伪函数的函数，可以使用匿名函数定义(lambda)作为其参数。1.1为什么使用lambda函数？距离：定义位于使用的地方附近很有用，由于......
  • Microsoft Visual C++ 14.0 is required.
    问题：配置detectron2的时候报错，MicrosoftVisualC++14.0isrequired.解决：按照上面的网址去下载MicrosoftC++BulidTools这个工具，安装对应的包即可 ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99