Fidel's Lab

从 C++98 到 C++14 —— OIer 升级指南

2021-09-12T16:00:00.000Z

2021 年 9 月 1 日，NOI 赛事终于对 C++ 语言支持了 C++14 标准。

由于 C++14 相比于 C++98 新增了不少内容，而大部分 OIer 此前的练习、比赛都基于 C++98 标准，为帮助大家快速上手 C++14 的重要好用的特性，这里给大家对 C++14 的新增内容作简单梳理。

本文仅针对 OI 介绍 C++14 相对于 C++98 的新增内容，因此部分 C++11 新增的内容也会在本文中出现。

本文所述「等价于」仅表示在大多数情况下运行代码产生的效果相同，并不表示在具体实现和汇编层面完全等价。

# 启用 C++14

确保 GCC 版本为 5 或以上，或 Clang 版本为 3.4 或以上。

更多关于编译器支持 C++14 的版本的信息

C++14 - cppreference.com

在编译命令中加入以下选项指定 C++ 标准：

-std=c++14

# 新特性

# `auto`

顾名思义，根据赋值表达式自动指定类型。

	int a = 114514;
	auto b = a + 1919810; // auto -> int

等价于：

	int a = 114514;
	int b = a + 1919810;

参考资料

占位类型说明符 (C++11 起) - cppreference.com

# `decltype`

顾名思义，推断传入的参数的类型。

	int a = 114514;
	decltype(a) b = 1919810; // int

参考资料

decltype 说明符 - cppreference.com

# 范围 `for` 循环

从 C++11 起，可以使用范围 for 循环遍历数组中的每一个元素：

	int a[N];
	for (int x : a) {
	func(x);
	}

等价于：

	int arr[N];
	for (int i = 0; i < N; i++) {
	int x = arr[i]; // copy
	func(x);
	}

与 auto 结合起来的等价写法：

	int arr[N];
	for (auto x : arr) {
	func(x);
	}

注意这里的 x 是 arr[i] 的拷贝，对 x 进行操作不会影响 arr[i] 的值。

使用 auto 和范围 for 循环，可以使原本复杂的迭代器遍历变得十分简洁：

（以下代码以 std::vector 为例）

	std::vector<int> arr;
	for (auto x : arr) {
	func(x);
	}

等价于原本的一大坨：

	for (std::vector<int>::iterator i = arr.begin(); i != arr.end(); i++) {
	int x = *i; // copy
	func(x);
	}

注意这里的 x 是 arr 的拷贝，对 x 进行操作不会影响 arr 的值。

如果想修改遍历的内容，可以使用 auto& ：

	std::vector<int> arr;
	for (auto &x : arr) {
	func(x);
	}

等价于：

	for (std::vector<int>::iterator i = arr.begin(); i != arr.end(); i++) {
	func(*i);
	}

注意这里的 x 是 arr 的引用，对 x 进行操作会影响 arr 的值。

使用 std::vector<bool> 时，慎用 auto ，因为 std::vector<bool> 采用了特殊的实现方法。详见下面的参考资料。

参考资料

基于范围的 for 循环 (C++11 起) - cppreference.com
[Brief Talk] auto, auto&, const auto & 以及其它形式的 auto 变种在 for-range loop 的选择 - 知乎

# 模板相关

# 变量模板

从 C++14 起，可以对变量使用模板。

template < 形参列表 > 变量声明

引用 cppreference.com 中的例子：

	template <class T>
	constexpr T pi = T(3.1415926535897932385L); // 变量模板

	template <class T>
	T circular_area(T r) { // 函数模板
	return pi<T> * r * r; //pi<T> 是变量模板实例化
	}

# 可变模板形参

从 C++11 起，允许模板中传入可变个数的参数。

template <typename... T>

现在，你可以使用可变模板形参实现 C++98 做不到的输出多个变量和自适应变量类型的 Debug 输出：

	#include <iostream>
	#include <string>

	#define DEBUG

	void debug_out() { std::cerr << '\n'; }
	template <typename Head>
	void debug_out(Head H) {
	std::cerr << H << std::endl;
	}

	template <typename Head, typename... Tail>
	void debug_out(Head H, Tail... T) {
	std::cerr << H << ", ";
	debug_out(T...);
	}

	#ifdef DEBUG
	#define debug(...) std::cerr << "[" #__VA_ARGS__ "]: ", debug_out(__VA_ARGS__)
	#else
	#define debug(...)
	#endif

改写自：【杂项】缺省源 - 滑蒻稽的博客

参考资料

变量模板 (C++14 起) - cppreference.com
模板形参与模板实参 - cppreference.com
【杂项】缺省源 - 滑蒻稽的博客

# Lambda 表达式

Lambda 表达式，换种说法就是行内 (inline) 匿名函数。（个人理解）

比如以下的 Lambda 表达式写法：

	std::sort(arr.begin(), arr.end(),
	[](int a, int b) { return a > b; }); // desending sort

等价于：

	bool cmp(int a, int b) { return a > b; }

	std::sort(arr.begin(), arr.end(), cmp);

与 auto 结合起来：

	std::sort(arr.begin(), arr.end(),
	[](auto a, auto b) { return a > b; }); // desending sort

Lambda 表达式的完整语法结构为： [ 捕获 ] ( 形参 ) lambda 说明符约束 (可选) { 函数体 }

再举个例子：

	int lim = 114514;
	auto function = ([lim](int x) -> bool {
	if (x > lim) {
	x = lim;
	return false;
	}
	return true;
	})
	function();

[ ] 中的捕获参数列表允许局部变量在函数中调用。

-> 指定了函数的返回类型。

更多关于 Lambda 的用法详见下面的参考资料。

参考资料

Lambda 表达式 (C++11 起) - cppreference.com
C ++ Lambda 表达式详解 - CSDN

# 二进制字面量 & 数位分隔符

从 C++14 起，可以在代码中直接书写二进制常量。

从 C++14 起，可以以单引号 ' 表示数位分隔符，会在编译时忽略。

	int var = 0b11011111101010010;
	int var = 0b0001'1011'1111'0101'0010;
	int var = 114'514;

等价于：

int var = 114514;

参考资料

整数字面量 - cppreference.com

# 新 STL 库功能特性

# `<unordered_set>` & `<unordered_map>`

<set> 和 <map> 的更快的 Hash 实现，用法与 <set> 和 <map> 相同。

# `<regex>`

正则表达式 (Regular Expression)，是一种用于在字符串中匹配模式的微型语言，可实现对字符串的匹配、搜索、分词和替换操作。字符串处理神器。

正则表达式的时间复杂度取决于表达式的复杂度，在平均情况下正则表达式的时间复杂度为 $O(n)$ 。

如果读者还不了解正则表达式，建议先在这里学习一下。

# 正则语法

std::regex 默认使用 ECMAScript 语法：

符号	释义
`^`	匹配行的开头
`$`	匹配行的结尾
`.`	匹配任意单个字符
`[…]`	匹配 `[]` 中的任意一个字符
`(…)`	设定分组
`\`	转义字符
`\d`	匹配数字 `[0-9]`
`\D`	`\d` 取反
`\w`	匹配字母 `[a-z]` ，数字，下划线
`\W`	`\w` 取反
`\s`	匹配空格
`\S`	`\s` 取反
`+`	前面的元素重复 $1$ 次或多次
`*`	前面的元素重复任意次
`?`	前面的元素重复 $0$ 次或 $1$ 次
`{n}`	前面的元素重复 $n$ 次
`{n,}`	前面的元素重复至少 $n$ 次
`{n,m}`	前面的元素重复至少 $n$ 次，至多 $m$ 次
`\|`	逻辑或

注意在 C++ 中书写正则表达式时，需要以 2 个反斜杠 \\ 代替所有转义字符的单个反斜杠 \ 。

更多正则表达式的语法详见参考资料。

# 匹配 ( `std::regex_match` )

传入 2 个参数：待匹配字符串和模式字符串 ( std::regex )。当待匹配字符串与模式字符串完全对应时，则返回 true ，否则返回 false 。

以下例子使用 regex_match 来匹配 XML 格式（或是 HTML 格式）的字符串。其中， "<.*>.*</.*>" 为模式字符串。

	std::regex pattern("<.>.</.*>");
	bool ret = std::regex_match("<html>value</html>", pattern); // true
	ret = std::regex_match("<xml>value<xml>", pattern); // false

# 搜索 ( `std::regex_search` )

传入 3 个参数：待匹配字符串、用于储存匹配结果的字符串 和模式字符串 ( std::regex )。当模式字符串在待匹配字符串中能匹配一次时，则返回 true ，否则返回 false 。用于储存匹配结果的字符串 ( std::cmatch ) 中会存入匹配的子串。

其中，用于储存匹配结果的字符串的常用类型为 std::cmatch 和 std::smatch ，分别对应 C 风格字符串 char* 和 std::string 。

	std::regex pattern("<(.)>(.)</(\\1)>");
	std::cmatch m;
	auto ret = std::regex_search("begin<xml>value</xml>end", m, pattern);

在以上的示例中，用于储存匹配结果的字符串 m 有以下调用方法：

m.str()
- m.str() ，等价于 m.str(0) ，返回匹配的完整字符串。在上述例子中，返回 "<xml>value</xml>" 。
- m.str(n) ，返回匹配的字符串中的第 $n$ 个元素（从 $1$ 开始），以模式串中的括号 () 划分。在上述例子中， m.str(1) 返回 "xml" ， m.str(2) 返回 "value" ， m.str(3) 返回 "xml" 。
m.size()

返回匹配的字符串中的元素个数加 1。在上述例子中，返回 4 。
m.prefix()

返回匹配的字符串的前缀（匹配的子串前的不匹配部分）。在上述例子中，返回 "begin" 。
m.suffix()

返回匹配的字符串的后缀（匹配的子串后的不匹配部分）。在上述例子中，返回 "end" 。

使用迭代器，可以遍历搜索出所有匹配的子串：

	std::regex pattern("<(.)>(.)</(\\1)>");
	std::string content(
	"begin<xml>value</xml>end<widget>example</widget>I<luogu>AK</luogu>IOI");
	std::smatch m;
	for (auto pos = content.cbegin(), end = content.cend();
	std::regex_search(pos, end, m, pattern); pos = m.suffix().first) {
	std::cout << m.str() << std::endl;
	}

其中， m.suffix().first 返回指向后缀的第一个字符的迭代器，即匹配结束的位置。

# 分词 ( `std::regex_token_iterator` )

模板类 std::regex_token_iterator 提供了分词迭代器：

	std::string content("kkksc03@luogu.com.cn,i@ak.ioi,114@514.1919.810");
	std::regex pattern(",");
	std::sregex_token_iterator pos(content.begin(), content.end(), pattern, -1);
	for (decltype(pos) end; pos != end; ++pos) {
	std::cout << pos->str() << std::endl;
	}

其中， std::sregex_token_iterator 是针对 string 类型的特化。构造函数传入 4 个参数：待匹配字符串的开始和结束迭代器、模式字符串 ( std::regex ) 和捕获模式。

当捕获模式为 -1 时，返回的迭代器指向匹配的字符串前的内容。当捕获模式为 0 时，返回的迭代器指向匹配的字符串，即在上述例子中的分隔符 "," 。

# 替换 ( `std::regex_replace` )

std::regex_replace 函数实现了正则替换功能。

	std::string content("1:Luogu,2:kkksc03,3:AKIOI");
	std::regex pattern("(\\d+):(\\w+)");
	std::cout << std::regex_replace(content, pattern, "id=$1, name=$2\n");
	// OUTPUT: {id=1,name=Luogu},{id=2,name=kkksc03},{id=3,name=AKIOI}

std::regex_replace 函数传入 3 个参数：待处理的字符串、模式字符串 ( std::regex ) 和替换字符串。

可以在模式字符串中使用括号 () 分组，在替换字符串中使用 $n 表示分组序号（从 1 开始），实现部分替换。

参考资料

正则表达式库 - cppreference.com
C++ 正则表达式 - cpluspluser - 博客园
正则表达式 - 语法 | 菜鸟教程
What's the Time Complexity of Average Regex algorithms? - Stack Overflow

# `<tuple>`

元组， std::pair 的推广，支持多个元素。

	std::tuple<int, float, int, float> tu = std::make_tuple(1, 14.f, 5, 14.f);
	std::tuple<int, float, int, float> tu(1, 14.f, 5, 14.f);

使用 std::forward_as_tuple 或 std::tie 构造引用值的元组，使用 std::get<n> 修改引用指向的值：

	int a = 1;
	float b = 14.f;
	int c = 5;
	float d = 14.f;

	auto tu = std::forward_as_tuple(a, b, c, d);
	auto tu = std::tie(a, b, c, d);

	// 修改引用指向的值
	std::get<0>(tu) = 19;
	std::get<1>(tu) = 1.9f;
	std::get<2>(tu) = 8;
	std::get<3>(tu) = 1.0f;

使用 std::tuple_cat 拼接多个元组：

	std::tuple<int, int, int, int> a(1, 1, 4, 5);
	std::tuple<int, int, int, int> b(1, 4, 1, 9);
	std::tuple<int, int, int, int> c(1, 9, 8, 1);
	auto d = std::tuple_cat(a, b, c);

支持按字典序比较。

参考资料

std::tuple - cppreference.com
C++Tuple 元组的详细用法 - 知乎

「机房利器」、Coding on iPad? —— 记一次使用 Cloud Studio 云端开发的尝试

2021-05-21T16:00:00.000Z

曾经，Fidel's Lab 的部署平台在 Github Pages 和 Coding Pages 之间反复横跳。这篇文章所介绍的「Cloud Studio」（原「腾讯云开发者平台」）就是由 Coding 提供的在线 IDE。Cloud Studio 基于 VS Code，只需要一个~~现代的~~浏览器和~~正常的~~网络连接即可在线使用。

早在一年半前，我就对 Coding 当时的「腾讯云开发者平台」有所关注（当时好像不叫这个）。只不过由于极其有限的免费使用额度、需要购买云服务器才能获得良好的体验等门槛，最终并没有采用。经过一年多的升级迭代，现在的 Cloud Studio 「每个用户每日可以（免费）使用工作空间共四小时」，足以承担轻度的开发任务。

经过一段时间的体验，个人认为 Coding Studio 的最佳使用场景之一是 OIer 们在校内机房短时间上机练习，由于只需配置一次环境即可快速启动，堪称 「机房利器」。

这篇文章主要记录我使用 Cloud Studio 进行 OI 练习和编辑维护 Hexo 博客、以及尝试使用移动端（iPad）进行开发的过程。此文章全程在 Cloud Studio 上编辑。

~~Coding 赶紧给我打钱~~

# 前置准备

首先在 coding.net 注册一个 Coding 账户。~~我相信这一步是个人都会，就不详细描述了。~~

「Coding」是什么？

你可以理解为是一个类似于 GitHub，在国内体验良好的代码托管仓库。关于 Coding 主站的功能，这里不详细讲述，有兴趣的 OIer 们可以自行研究。

从左侧菜单栏进入「Cloud Studio」，或者从 cloudstudio.net 使用 Coding 账号登陆。

# OI on Cloud Studio

# 创建工作空间

现在你进入了你的 Cloud Studio 面板。点击上方 「新建工作空间」。

关于 「运行环境」：这里我们选择 「预置环境」。（有服务器的大佬也可以连接云服务器使用，风险自行承担。）

对于使用 C++ 的 OI 编程，我们选择 「Ubuntu」。

「Ubuntu」是什么？

Linux 的发行版之一。
关于 「代码来源」：选择 「空」。

注意 Cloud Studio 自带的仓库同步不稳定。如果需要同步远程仓库代码，建议进入工作空间后使用 Git 手动配置。

# 初步探索

进入工作空间，你会发现 Cloud Studio 的界面与 VS Code ~~完全一致~~高度相似。熟悉 VS Code 的读者可以跳过此部分。

# 命令面板 (Commands Panel)

按下 Ctrl + Shift + P 打开命令面板。

在命令面板里可以找到 VS Code 中所有的操作（包括插件）及对应的快捷键。

# 命令行 / 终端 (Terminal)

Cloud Studio 的本质是一台云服务器，通过 VS Code 控制。如何仅通过一个编辑器控制一个操作系统呢？

接下来介绍 Linux 中最强大的工具：命令行 (Terminal)。

在 VS Code 中，按下 Ctrl + ` 打开终端。

Linux 命令行的基本用法

左侧的 RemoteWorking 表示当前所在的目录。

pwd 查看完整的目录路径。
mkdir <dirname> 在当前目录下新建名为 <dirname> 的文件夹。
ls 列出当前目录下的所有文件和文件夹。
cd <dirname> 进入当前目录下名为 <dirname> 的文件夹。
- cd .. 返回上一级目录。
- cd ~ 前往家目录（如用户 root 的家目录为 /root ）。
- cd / 前往根目录 ( / )。
touch <filename> 在当前目录下创建名为 <filename> 的文件。
rm <filename> 删除当前目录下名为 <filename> 的文件。
- rm -r <dirname> 删除当前目录下名为 <filename> 的文件夹。
- rm -r * 删除当前目录下的所有文件和文件夹。
- 参数 -f 不经过确认直接删除。

# 设置 (Settings)

在 VS Code 界面左上角选择 「文件 - 打开文件夹…」，可以设置左侧资源管理器的根目录。

按下快捷键 Ctrl + , 或在左上角选择 「文件 - 首选项 - 设置」 进入设置界面。

值得介绍的 VS Code 设置项

在设置页面搜索左侧的 index 即可转到相应设置。也可以从设置界面右上角打开 Json 文件修改设置。

terminal.integrated.cwd Terminal 的默认启动路径。

editor.fontSize 编辑器字体大小。

editor.fontFamily 编辑器字体。我使用的配置是 Monaco, Consolas, Menlo, 'Courier New', monospace ，在 Windows 和 MacOS 下都有不错的效果。

editor.wordWrap 启用长行自动换行（仅影响显示效果）。

VS Code 的界面我认为还是非常清晰的，相信大家简单摸索之后就能很快了解。

# C++ 相关组件安装及配置

# 编译器 (LLVM / Clang)

这里以 LLVM / Clang 的安装举例。GCC 等编译器的安装过程大致相似。

「Clang」是什么？

与大家熟悉的 GCC (G++) 类似，Clang (Clang++) 是 C (C++) 的编译器之一。相比于 GCC，Clang 有着更快的编译速度、更友好的错误提示等优点。同时，与 Clang 配套的调试器 LLDB（对应 GCC 的 GDB）对 MacOS 更加友好。

Linux 下有极其方便的软件包管理工具：apt。

只需要在终端中输入四行指令：

	apt update
	sudo apt install llvm
	sudo apt install clang
	sudo apt install lldb

一切完成。

~~比屑百度出来的大一堆下载源码手动编译的方法方便百倍。~~

Cloud Studio 默认配置了清华镜像源，按理来说下载速度应该很快。

提示如果下载进度卡了，按下 Ctrl + C 终止并重新执行命令。

# 插件 (Extensions)

在 VS Code 左侧工具栏选择最后一项 「Extensions」图标进入插件列表。在上方搜索框输入插件名称关键字即可在插件商店中搜索。点击 「Install」 即可一键安装。极其方便！

# C / C++

微软出品的 C / C++ 配套插件，包括代码高亮、自动补全、调试等功能。

在 Panel 中使用命令 C/C++: 编辑配置 (UI) 打开编辑器，或使用命令 C/C++: 编辑配置 (JSON) 切换到 c_cpp_properties.json 文件进行配置。

可以根据需要修改编译器参数、C / C++ 标准等设置。

# Code Runner

代码快捷运行工具，适用多种代码语言。

进入设置界面或 settings.json ，修改 code-runner.executorMap 项，将编译程序从 gcc /g++ 改为 clang /clang++。

	- "c": "cd $dir && gcc $fileName -o $fileNameWithoutExt && $dir$fileNameWithoutExt",
	+ "c": "cd $dir && clang $fileName -o $fileNameWithoutExt && $dir$fileNameWithoutExt",

	- "cpp": "cd $dir && g++ $fileName -o $fileNameWithoutExt && $dir$fileNameWithoutExt",
	+ "cpp": "cd $dir && clang++ $fileName -o $fileNameWithoutExt && $dir$fileNameWithoutExt",

注意默认通过 Code Runner 运行的代码无法直接从 VS Code 接收键盘输入，所以需要使用文件读入。如果需要从键盘输入，可在设置中启用 code-runner.runInTerminal ，代码将在 Terminal 中运行。（感谢 @Zxc200611 提醒）

个人建议还是使用文件读写，一是方便 Debug，二是为日后竞赛养成良好习惯。

# Compile and Run!

编写好 C++ 程序后，在编辑器右上角点击 「运行」图标或按下快捷键 Ctrl + Alt + N 编译并运行代码。

按下快捷键 Ctrl + Alt + M 强制停止运行中的代码。

# Debug

在 VS Code 左侧工具栏选择第三项 「Run」图标进入调试菜单。

点击 「运行和调试 (Run and Debug)」，选择 「C++ (GDB/LLDB)」-「clang++」，并保存 launch.json 。

代码打断点，然后点击左上角小三角开始调试。

左侧菜单的各个部分的含义和作用分别为：

变量：当前代码中的局部变量。
监视：全局 / 局部变量，需要手动添加。
调用堆栈 & 断点：顾名思义。

提示可以直接对左侧的变量值进行修改。

# 用户代码片段

以配置 C++ 的用户代码片段为例，点击 「左下角齿轮图标（管理）- 用户代码片段」，选择 「cpp」。

按照注释中的提示编辑 cpp.json 。

这里以我的 cpp.json 为例：

	{
	"C++ program": {
	"prefix": "cpp",
	"body": [
	"#include <cstdio>",
	"",
	"inline int read() {",
	" int x = 0, c = getchar(), f = 0;",
	" while (c < '0' \|\| c > '9') f \|= c == '-', c = getchar();",
	" while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();",
	" return f ? -x : x;",
	"}",
	"",
	"int main() {",
	"#ifndef ONLINE_JUDGE",
	" freopen(\"test.in\", \"r\", stdin);",
	" freopen(\"test.out\", \"w\", stdout);",
	"#endif",
	"",
	" $0",
	"",
	"#ifndef ONLINE_JUDGE",
	" fclose(stdin);",
	" fclose(stdout);",
	"#endif",
	" return 0;",
	"}"
	]
	}
	}

在后缀为 .cpp 的代码文件中，输入 cpp ( prefix ) 并按下 Tab ，将会自动补全为：

	#include <cstdio>

	inline int read() {
	int x = 0, c = getchar(), f = 0;
	while (c < '0' \|\| c > '9') f \|= c == '-', c = getchar();
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f ? -x : x;
	}

	int main() {
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif

	/* Code */

	#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	#endif
	return 0;
	}

同时，编辑光标会移到 /* Code */ ( $0 ) 的位置。

利用预编译判断指令 #ifndef ONLINE_JUDGE ，这份模板提交到洛谷时不需要删除文件读写，极其好用。

# 代码格式化 (clang-format)

随手对写完的代码 Shift + Alt + F 格式化是一个好习惯。

VS Code 的 C / C++ 插件里，使用的格式化程序是 clang-format。

修改设置中的 C_Cpp.clang_format_fallbackStyle 项配置格式化选项。

我的配置是： { BasedOnStyle: Google, IndentWidth: 4, UseTab: Never } 。

BasedOnStyle: Google 使得大括号不独占一行。可以根据个人喜好修改。

# Hexo on Cloud Studio

以下内容为 Cloud Studio 的拓展进阶玩法，需要你掌握以下前置知识：

Hexo 博客的搭建
Git 的使用

假设，你已经搭建过你的 Hexo 博客，并已经将源代码上传至代码托管平台。

如果没有，请参阅 Hexo 文档直接搭建博客，或将源代码上传至代码托管平台。

# 创建工作空间

「运行环境」：选择「预置环境 - Node.js」。
「代码来源」：选择 「空」。

注意 Cloud Studio 自带的仓库同步不稳定。如果需要同步远程仓库代码，建议进入工作空间后使用 Git 手动配置。

# 源代码迁移

使用 git clone 下载源代码至本地。

按照惯例，在主目录下运行 hexo 命令。但是这时候你会发现运行不了的：

zsh: command not found: hexo

输入以下命令，在 /usr/local/bin/ 目录下创建 hexo 程序的软链接到 RemoteWorking/<dirname>/hexo/node_modules/hexo/bin/hexo 。

ln -s ~/RemoteWorking/<dirname>/hexo/node_modules/hexo/bin/hexo /usr/local/bin/hexo

再次运行 hexo 命令，发现可以正常使用了。

# 运行服务器 & 网页预览

输入 hexo s 启动预览。

得益于 Cloud Studio 的 Browser Preview Lite 插件，你可以非常方便地预览你的 Hexo 博客。

Ctrl + Shift + P 打开 Panel，输入 preview ，在命令列表中点击 Preview: Open Preview Tab ，输入端口号 4000 ，即可打开预览。

或者你也可以通过配置 preview.yml ，一键启动服务器并打开预览。

打开 Panel，输入 preview ，在命令列表中点击 Preview: Generate Preview Config File ，编辑配置文件。

这是我的配置：

	# .vscode/preview.yml
	autoOpen: false # 打开工作空间时是否自动开启所有应用的预览
	apps:
	- port: 4000 # 应用的端口
	run: hexo s -p 4000 # 应用的启动命令
	root: hexo # 应用的启动目录
	name: Hexo # 应用名称
	description: hexo s # 应用描述
	autoOpen: false # 打开工作空间时是否自动开启预览（优先级高于根级 autoOpen）
	- port: 4001
	run: hexo s --drafts -p 4001
	root: hexo
	name: Hexo (Show Drafts)
	description: hexo s --drafts
	autoOpen: false

注意由于 Browser Preview Lite 以 port 作为索引关键字， port 必须是唯一的。可以使用参数 -p 指定端口号。

配置完毕后，打开 Panel，输入 preview ，在命令列表中点击 Preview: Open Preview Tab ，即可快速选择预览选项。

# VS Code 配置

Terminal 的初始路径可以通过 terminal.integrated.cwd 修改。

# 额外组件安装及配置

# Markdown Preview Enhanced

强大的 Markdown 预览插件。

# markdownlint

强大的 Markdown 格式检查工具，~~强迫症福音~~。

我的配置 ( .markdownlint.json )：

	{
	"single-title": false,
	"ol-prefix": false,
	"line-length": false,
	"no-alt-text": false,
	"no-emphasis-as-heading": false,
	"no-blanks-blockquote": false,
	"no-trailing-punctuation": {
	"punctuation": ".,;:。，；："
	},
	"no-inline-html": false,
	"no-duplicate-header": false
	}

对着 markdownlint's Rules.md file 自行研究吧。

# Pangu-Markdown

在中文与英文、数字与符号之间加入空格是个好习惯。

在 Panel 中输入 Pangu Format ，可以自动添加空格。

汉学家称这个空白字元为「盘古之白」，因为它劈开了全角符和半角符之间的混沌。另有研究显示，打字的时候不喜欢在中文和英文之间加空格的人，感情路都走得很辛苦，有七成的比例会在 34 岁的时候跟自己不爱的人结婚，而其余三成的人最后只能把遗产留给自己的猫。毕竟爱情跟书写都需要适时地留白。

摘自：https://github.com/vinta/pangu.js

# MarkDown Table Format

Shift + Alt + F 对表格进行格式化。

至于不少人推荐的 Markdown All in One：我觉得不好用。真的一点也不好用。试着输入一下多行引用块就知道了。

# Coding on iPad?

抱着「你的下一台电脑何必是电脑」的想法，我尝试着在 iPad 上使用 Cloud Studio 写代码。毕竟，只要带一台 iPad 而不用背着~~重如砖块的~~电脑到处跑可太香了。

测试平台：iPad 8 (iPadOS 14.5)，Microsoft Edge 浏览器。

Cloud Studio（或者说网页版的 VS Code）对于触控的优化还是不错的。滑动、点击、长按调出右键菜单等操作都可以顺利完成。

然而输入的体验就不那么好了。写代码就别~~手戳玻璃~~敲虚拟键盘了，老老实实用蓝牙键盘吧。

受限于设备性能和网络，输入时略有延迟，不太跟手。

最大的问题，来源于 Cloud Studio 自行实现了一套与 iPadOS 系统级别不同的输入逻辑。

由于 Cloud Studio 自行实现了输入光标，在切换窗口后，内部的输入光标有时不能聚焦到正确的位置，反映为 iPadOS 系统级别的输入光标聚焦在编辑器上，而 Cloud Studio 内部的输入光标还在别的位置，无法通过键盘输入，需要点击其他位置再聚焦到编辑器才能正常输入。

Cloud Studio 的剪切板与 iPadOS 系统剪切板是独立的，且由于适配问题不能互通，只能在 Cloud Studio 内部复制粘贴。这使我差点因为代码复制不出去而交不了作业，最终通过 cat 指令将文件在 Terminal 中 print 出来，才能复制出去。

总体来说，Cloud Studio 在 iPad 上的使用体验还远远达不到能顺畅使用的级别。~~你的下一台电脑还得是电脑。~~

# 彩蛋

在 Terminal 中，输入 lscpu 可查看 CPU 信息。

Intel(R) Xeon(R) Gold 6148 CPU @ 2.40GHz!

输入 free -m 查看内存信息（单位 MiB）。

2 GiB 内存！

输入 df -h 查看硬盘分区信息。

唔……

# References

Cloud Studio 文档
Linux 命令大全

【转载】还能这样玩——关于一些 OI 的黑 (sao) 科 (cao) 技 (zuo) 优化

2021-02-13T16:00:00.000Z

编者注：虽然标题中提到了 OI，但个人认为本文对追求极限的代码调优的价值远大于对 OI 的价值。

转载修改内容：

修复了原文滥用 $\LaTeX$ 问题。
对代码进行了格式化。
修改了原文汇编代码的错误注释。（汇编的注释符号是 ; 而不是 // ！）
修改原文符号的不规范使用。
删除或修改了存在争议或错误的内容。

# 免责声明

本文仅供参考，由读者引发的一切后果，任何责任由读者自行承担。后果包括但不限于：

优化后程序变慢。

某些 OJ/OI 上导致的编译错误。

文章中的某些错误引起的争论。

# GCC 系列

关于 GCC 的黑科技想必大家也就知道这几句吧：

	#pragma GCC optimize(3)
	#pragma GCC optimize(2)
	#pragma GCC optimize(1)

俗称 “吸氧”。

在这里小编就简单地讲一下 -O1 , -O2 , -O3 , -Os （怎么还有个 -Os ）。

# O 系列

# `-O1`

包含下列选项：

	-fauto-inc-dec
	-fcprop-registers
	-fdce
	-fdefer-pop
	-fdelayed-branch
	-fdse
	-fguess-branch-probability
	-fif-conversion2
	-fif-conversion
	-finline-small-functions
	-fipa-pure-const
	-fipa-reference
	-fmerge-constants -fsplit-wide-types
	-ftree-builtin-call-dce
	-ftree-ccp
	-ftree-ch
	-ftree-copyrename
	-ftree-dce
	-ftree-dominator-opts
	-ftree-dse
	-ftree-fre
	-ftree-sra
	-ftree-ter
	-funit-at-a-time
	-fomit-frame-pointer

# `-O2`

除了加载 -O1 的选项外，还加载：

	-fthread-jumps
	-falign-functions -falign-jumps
	-falign-loops -falign-labels
	-fcaller-saves
	-fcr-Ossjumping
	-fcse-follow-jumps -fcse-skip-blocks
	-fdelete-null-pointer-checks
	-fexpensive-optimizations
	-fgcse -fgcse-lm
	-findirect-inlining
	-foptimize-sibling-calls
	-fpeephole2
	-fregmove
	-freorder-blocks -freorder-functions
	-frerun-cse-after-loop
	-fsched-interblock -fsched-spec
	-fschedule-insns -fschedule-insns2
	-fstrict-aliasing -fstrict-overflow
	-ftree-switch-conversion
	-ftree-pre
	-ftree-vrp

# `-O3`

除了加载 -O2 外，还加载：

	-finline-functions
	-funswitch-loops
	-fpredictive-commoning
	-fgcse-after-reload
	-ftree-vectorize

# `-Os`

在研究编译驱动的 makefile 的时候，发现 GCC 的命令行里面有一个 -Os 的优化选项。

遍查 GCC 文档，发现了 -O0 , -O1 , -O2 , -O3 ，就是没有发现 -Os 。

祭出 GOOGLE，搜了一下，终于发现这篇文章说明了 -Os 的作用：

http://www.linuxjournal.com/article/7269

原来 -Os 相当于 "-O2.5"。是使用了所有 -O2 的优化选项，但又不缩减代码尺寸的方法。
除了包含 -O2 的开关外， -Os 还会使得下列开关禁用。

	-falign-functions
	-falign-jumps
	-falign-loops
	-falign-labels
	-freorder-blocks
	-freorder-blocks-and-partition
	-fprefetch-loop-arrays
	-ftree-vect-loop-version

另外，对于多个 -O 选项的情形，最后一个加载的为有效。比如 gcc -O1 -Os -O3 –o test test.c ，有效的优化开关为 -O3 。

一般来说，用的最多的是 -O3 和 -Os ，如果遇到程序运行不正常的问题，请降低优化级别，如把 -O3 改为 -O2 （情况很少见）。

# 针对目标机器

# `-march=cpu-type`

为 cpu-type 所针对的机器开启需要的指令集。

cpu-type 可以为 pentium4、core2、athlon-4 等（具体参见文档），比如 -march=core2 时，则会开启 core2 所支持的 MMX、SSE、SSE2、SSE3、SSSE3 指令集。

另外还支持 native 类型，为编译器所在目前的 CPU 类型优化指令集，指定 -march=native 。

# `-mfpmath=unit`

选择浮点运算单元。

unit 可以为 387 和 sse 。

387 为 x86 系列的默认值，使用标准的 387 浮点协处理器。

sse 为 x64 的默认值，使用 sse 指令集。

一般你的程序如果有大量的浮点运算的话，在 P4 和 K8 以上级别的处理器上推荐开启 -mfpmath=sse 。

# 加载指定指令集

可以使用 -msse2 或 -msse4.1 加载指定的指令集。

# 其他比较有效的选项

# `-ftracer`

执行尾部复制以扩大超级块的尺寸，它简化了函数控制流，从而允许其它的优化措施做的更好。单独使用没啥意义，和其他优化选项一起使用很有效。

# `-ffast-math`

违反 IEEE/ANSI 标准以提高浮点数计算速度，是个危险的选项，仅在编译不需要严格遵守 IEEE 规范且浮点计算密集的程序考虑采用。不考虑精度时使用这个选项速度会加快。

# `-fivopts`

在 trees 上执行归纳变量优化。

# `-ftree-parallelize-loops=n`

使循环并行化。只当循环无数据依赖时使用，在多核 CPU 上时使用才会有利。

# `-ftree-loop-linear`

在 trees 上进行线型循环转换。它能够改进缓冲性能并且允许进行更进一步的循环优化。

# `-fforce-addr`

必须将地址复制到寄存器中才能对他们进行运算。由于所需地址通常在前面已经加载到寄存器中了，所以这个选项可以改进代码。

# `-floop-interchange`

交换循环变量。

例如：

	DO J = 1, M
	DO I = 1, N
	A(J, I) = A(J, I) * C
	ENDDO
	ENDDO

会改变为：

	DO I = 1, N
	DO J = 1, M
	A(J, I) = A(J, I) * C
	ENDDO
	ENDDO

改变后，如果 N 比缓冲区大的话，会更有效率。这是因为 Fortran 里数组是以列主元为排列方式的。当然这个选项并不仅仅用于 Fortran，gcc 家族的编译器都有效。

# `-fvisibility=hidden`

设置默认的 ELF 镜像中符号的可见性为隐藏。使用这个特性可以非常充分的提高连接和加载共享库的性能，生成更加优化的代码，提供近乎完美的 API 输出和防止符号碰撞。我们强烈建议你在编译任何共享库（Dll）的时候使用该选项。

-fvisibility-inlines-hidden

默认隐藏所有内联函数，从而减小导出符号表的大小，既能缩减文件的大小，还能提高运行性能，强烈建议你在编译任何共享库的时候使用该选项。

# `-minline-all-stringops`

默认时 GCC 只将确定目的地会被对齐在至少 4 字节边界的字符串操作内联进程序代码。该选项启用更多的内联并且增加二进制文件的体积，但是可以提升依赖于高速 memcpy , strlen , memset 操作的程序的性能。

# `-m64`

生成专门运行于 64 位环境的代码，不能运行于 32 位环境，仅用于 x86_64 [含 EMT64] 环境。

# `-fprefetch-loop-arrays`

生成数组预读取指令，对于使用巨大数组的程序可以加快代码执行速度，适合数据库相关的大型软件等。具体效果如何取决于代码。不能和 -Os 一起使用。

# `-pipe`

在编译过程的不同阶段之间使用管道而非临时文件进行通信，可以加快编译速度。建议使用。

# 推荐选项开关

综上，比较安全的开关为

	-pipe
	-O3 (-Os)
	-march=native
	-mfpmath=sse
	-msse2
	-ftracer
	-fivopts
	-ftree-loop-linear
	-fforce-addr

如果不需要多高的精度，比如 GUI 框架之类，加入：

-ffast-math

如果是编译的是共享库（ .dll , .a ）加入

	-fvisibility=hidden
	-fvisibility-inlines-hidden

注意某些比赛不能使用 -O1 , -O2 , -O3 , -Os .

# 底层优化（坑）

# I/O 优化

I/O 优化是卡常中最常用的技巧，当数据较大的时候，读入输出占用了很多时间。

# 读入优化

流输入方式很方便，不需要记忆占位符，但每次读入时，它都要检测是否和 stdin 的同步（是否被 freopen 改变 / 是否被 scanf 读取），因此它是可以和 scanf 混用的。但也导致了它每次都要从数据开始位置跳转到当前读入的位置，浪费了大量时间，可以用 std::ios::sync_with_stdio(false); 关闭两者的同步以加快速度，这样做之后会比 scanf 还快！但必须注意，调用后不能再用 freopen ，但是还可以用 fstream 。

当然，更好的方法是用 getchar 自己写读入函数。

	inline void read(int &sum) {
	char ch = getchar();
	int tf = 0;
	sum = 0;
	while ((ch < '0' \|\| ch > '9') && (ch != '-')) ch = getchar();
	tf = ((ch == '-') && (ch = getchar()));
	while (ch >= '0' && ch <= '9') sum = sum * 10 + (ch - 48), ch = getchar();
	(tf) && (sum = -sum);
	}

编者注：

补充一份我自己使用的快读：

	inline int read() {
	int x = 0, c = getchar(), f = 0;
	while (c < '0' \|\| c > '9') f \|= c == '-', c = getchar();
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f ? -x : x;
	}

优势：更短，且不会因为代码格式化而展开。

这样效率有了很大的提升，而且可以和 scanf 混用（字符串等），第 7 行和第 10 行的代码后面会说。

我们知道， getchar 是逐字符读取的，在 stdio.h 中，有一个 fread 函数，能整段读取，比 getchar 还快，并且支持 freopen （完美兼容）和 fopen （需要把下面的所有 stdin 改成你的文件指针）。

函数原型： size_t fread(void *buffer, size_t size, size_t count, FILE *stream);

作用：从 stream 中读取 count 个大小为 size 个字节的数据，放到数组 buffer 中，返回成功了多少个大小为 size 个字节的数据。

	inline char nc() {
	static char buf[1000000], p1 = buf, p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
	}
	//#define nc getchar
	inline void read(int &sum) {
	char ch = nc();
	int tf = 0;
	sum = 0;
	while ((ch < '0' \|\| ch > '9') && (ch != '-')) ch = nc();
	tf = ((ch == '-') && (ch = nc()));
	while (ch >= '0' && ch <= '9') sum = sum * 10 + (ch - 48), ch = nc();
	(tf) && (sum = -sum);
	}

但要注意，由于这种方法是整段读取的，这也造就了它两个巨大的缺陷：

不能用键盘输入。数据还没输入，程序怎么整段读取。如果你需要在电脑上用键盘输入调试，请把第 6 行的注释取消。
不能和 scanf ， getchar 等其他读入方法混合使用。因为 fread 是整段读取的，也就是说所有数据都被读取了，其他函数根本读取不到任何东西（只能从你的读取大小后面开始读），因此，所有类型的变量读入都必须自己写，上面的 read 函数只支持 int 类型。

下面是测试，摘自 LibreOJ，单位为毫秒（ $n=3 \times 10^6$ ）。

读入方法	编译器	$[0,2^1)$	$[0,2^3)$	$[0,2^{15})$	$[0,2^{31})$	$[0,2^{63})$
`fread`	G++ 5.4.0 ( `-O2` )	13	13	39	70	111
`getchar`	G++ 5.4.0 ( `-O2` )	58	73	137	243	423
`cin` （关闭同步）	G++ 5.4.0 ( `-O2` )	161	147	205	270	394
`scanf`	G++ 5.4.0 ( `-O2` )	182	175	256	368	574
`cin`	G++ 5.4.0 ( `-O2` )	442	429	706	1039	1683

没错，你没有看错， fread 以压倒性的优势碾压了其他所有方法，而关闭同步的 cin 比 scanf 快，并且读 long long 的时候比 getchar 还要快。

下面的内容某些 OI 比赛不支持。慎用！

其实还可以更快， Linux 下 sys/mman.h 中存在函数 mmap ， scanf 底层实现时调用的就是 mmap 函数，其作用是把文件映射进内存，这里仅仅给出代码，有兴趣的同学可以自行查阅有关资料。

	#include <sys/mman.h>
	namespace Inputs {
	char* s;
	int a[24];
	io() {
	s = (char*)mmap(NULL, 1 << 26, PROT_READ, MAP_PRIVATE, fileno(stdin), 0);
	}
	void scan(char* u) {
	while (*s < 48) ++s;
	while (s > 32) u++ = *s++;
	*u = 0;
	}
	int scan() {
	int Hibiki = 0, v = 1;
	while (s < 48) v = s++ ^ 45 ? 1 : -1;
	while (s > 32) Hibiki = Hibiki 10 + *s++ - 48;
	return Hibiki * v;
	}
	}

有人喜欢用 isdigit 宏，但这个宏在本机测试上的确更慢了，这个宏的效率还有待研究。

# 输出优化

输出优化并不是十分常用，因为很少有题目要求大量输出，这里仍然给出代码。（第 4 行以后再说）

	void write(int x) {
	if (x == 0) return (void)putchar('0');
	(x < 0) && (putchar('-'), x = -x);
	static int a[26];
	int tp = 0;
	while (x > 0) {
	a[++tp] = x % 10;
	x /= 10;
	}
	for (int i = tp; i > 0; i--) putchar(a[i] + '0');
	}

如果你按照上面的代码打，那只能说明你的想象力不够， fwrite 扑进 fread 的怀里失声痛哭。 fwrite 的优势被你完美地抛弃了，取而代之的是逐字符输出的 putchar 。

函数原形：

size_t fwrite(const void *buffer, size_t size, size_t count, FILE *stream);

作用：把 buffer 中的数据拆成大小为 size 个字节的数据，输出前 count 个到 stream 中，实际成功写入的大小为 size 的数据块数目。

	namespace Ostream {
	static const int BUF = 50000000;
	char buf[BUF], *h = buf;
	inline void put(char ch) {
	h == buf + BUF ? (fwrite(buf, 1, BUF, stdout), h = buf) : 0;
	*h++ = ch;
	}
	inline void putint(int num) {
	static char _buf[30];
	sprintf(_buf, "%d", num); //(*)
	for (char s = _buf; s; s++) put(*s);
	}
	inline void finish() { fwrite(buf, 1, h - buf, stdout); }
	};

有人也许会说，上面的代码的 (*) 处还可以优化，但这个优化的意义并不大，当然，也可以优化。

下面是测试：

( $n = 5 \times 10^6$ , rand)

Clock Rate: 3.70 GHz

RAM: 4 GB

方法	编译器	时间 (ms)
`printf`	G++ 5.4.0	21278
`sprintf` + `puts`	G++ 5.4.0	21426
纯 `sprintf` 不输出	G++ 5.4.0	540
`fprintf(stdin)`	G++ 5.4.0	26037
`putchar`	G++ 5.4.0	98556
`sprintf` + `fwrite`	G++ 5.4.0	607

由上表得， sprintf 的复杂度并不高， fwrite 也没有给 fread 丢脸。而 fprintf 的表现却让人大跌眼镜。 getchar 的结果很可能具有偶然性，反正上面的数据是在小编的机器上用同一组随机数测的。

# 位运算

在很多时候，我们会听到很多有关位运算的追捧，像 “位运算的常数很小，比加减法还要快”。这是真的吗？

# 左移和右移的天上地下

下面有两段代码：

	#include <cstdio>
	int x = 5;
	int main(void) {
	x <<= 1;
	printf("%d", x);
	return 0;
	}

	#include <cstdio>
	int x = 5;
	int main(void) {
	x *= 2;
	printf("%d", x);
	return 0;
	}

它们理论上是等价的，但 g++ 翻译成汇编后呢？

两段代码的汇编代码是一样的！下面是 x<<=1 和 x*=2 被翻译后的代码。

addl    %eax, %eax

它等价于 a=a+a 。是不是被打脸了，响不响，痛不痛，红不红，痒不痒…… 好吧，从上面的例子可以看出，某些时候自作聪明的优化并没有任何用。

那乘以 4 呢？翻译后的代码还是一样的：

sall    $2, %eax

上面的代码等价于 x<<=2 。现在死心了吧。

或许你还执着于 x*=10 。这次翻译后的汇编代码终于不一样了，下面是 x*=10 的汇编代码（ -O2 优化）：

leal    (%eax,%eax,4), %eax
addl    %eax, %eax

只有两条指令：

	x=x+x*4 // 别看是加法和乘法，却是一条指令完成
	x=x+x // 加法还不容易吗

那些喜欢用 x=(x<<3)+(x<<1) 的人请自重。

那是不是说位运算一无所用呢？并不是，在除法方面有不少用处。

右移的汇编代码：

  movl    _x, %eax
  sarl    %eax
  movl    %eax, _x
  movl    _x, %eax

除以 2 的代码：

  movl    _x, %eax
  movl    %eax, %edx  ;(del)
  shrl    $31, %edx   ;(del)
  addl    %edx, %eax  ;(del)
  sarl    %eax
  movl    %eax, _x
  movl    _x, %eax

整整多了三行。

但这种情况仅限于有符号的整数，因为有符号的整数的右移和除法不是同一个东西，编译器还需要修正一下。
如果用的是 unsigned 类型，那汇编代码又一样了。

# Mod 和 And 的战争

下面是 x%2 的代码（ -O2 ）：

  movl    _x, %eax
  movl    $LC0, (%esp)
  movl    %eax, %edx   ;(del)
  shrl    $31, %edx    ;(del)
  addl    %edx, %eax   ;(del)
  andl    $1, %eax
  subl    %edx, %eax   ;(del)
  movl    %eax, 4(%esp)
  movl    %eax, _x

那 x&1 呢？少了 4 条语句（ -O2 ）：

  movl    _x, %eax
  movl    $LC0, (%esp)
  andl    $1, %eax
  movl    %eax, 4(%esp)
  movl    %eax, _x

# Xor 和 temp 的故事

相信大家在学交换两个变量的值的时候一定会先学习所谓的 “三变量交换法”，然后就被异或取代了。

下面是异或（ a^=b^=a^=b ）的汇编：

  movl    _b, %edx
  movl    _a, %eax
  xorl    %edx, %eax
  xorl    %eax, %edx
  xorl    %edx, %eax
  movl    %eax, _a
  xorl    %eax, %eax
  movl    %edx, _b

有 movl 指令和 xorl 指令各 4 条。
那三变量交换法（ int t=a; a=b, b=t; ）呢？

  movl    _a, %eax
  movl    _b, %edx
  movl    %eax, _b
  xorl    %eax, %eax
  movl    %edx, _a

从此，有 temp 再没有异或。

# 神奇的 “位运算技巧”

网上有很多奇奇怪怪的方法，例如取绝对值 (n^(n>>31))-(n>>31) ，取两个数的最大值 b&((a-b)>>31)|a&(~(a-b)>>31) ，取两个数的最小值 a&((a-b)>>31)|b&(~(a-b)>>31) 。

喜欢用上面代码的人难道没有自己亲自数一数上面有多少条位运算的指令吗？

但凡事没有绝对，还是有一些优秀的例子的：

取二进制下最后一个 1 和后面的 0 ：

lowbit(x)=(x&(-x))

判断一个数是不是 2 的幂：

n>0?(n&(n-1))==0:false

# Xor 和网络流的故事

还记得网络流的反向弧？通常某些人喜欢在结构体中新建一个变量来表示这条边的反向弧编号。但这样不免有些浪费，因为在插入新边的时候，我们一般会把两条互为反向弧的边相邻插入，有一个有趣的性质可以完美地解决这个问题：

	(2x)^1=2x+1
	(2x+1)^1=2x

也就是说，我们可以用异或节省下一个空间。

那在汇编中呢？异或本来就是逻辑运算，一条指令 xorl $1, _x 搞定，但如果用另一个变量呢？编译器需要对变量进行初始化，还多了一条指令。

# 条件语句

相信条件语句会在程序中经常出现，而且也是不可避免的，谁知道，这么死板的事情还可以再优化。

# `if` 和 `?:` 的故事

编者注：原文内容存在错误，已删除。

if-else 与 ?: 运算符本质上相同，大多数情况下所产生的汇编代码完全相同。
对于下面的两段代码：
if (x == 1)
    printf("1");
else
    printf("2");
x == 1 ? printf ("1") : printf ("2");
网上有人说，三目运算符比 if 语句快，所以第二段代码就比第一段代码快。

实际上汇编代码是一模一样的，所以运行时间也是一样的。

摘自：浅谈底层常数优化及编译器优化 - zhaojinxi 的博客 - 洛谷博客
?: 运算符并不会消除分支预测。

分支预测的原理，是在 if 括号内部的判断语句未执行完成时，在另一线程中预测一条分支执行接下来的语句。当判断语句执行完毕时，若执行结果与预测相同，则继续执行该分支语句；若执行结果与预测不同，则重新执行另一分支语句。分支预测可以充分发挥 CPU 的多线程性能，避免多余的等待。

分支预测的效率取决于 CPU 的设计。在大部分情况下，分支预测能加快运算速度，除非分支预测的准确度极低。毕竟 CPU 的设计者也不是傻子。

分享一篇不错的关于分支预测的文章：为什么很多程序员不用 switch，而是大量的 if...else if ...？ - 是 Yes 呀的回答 - 知乎

下面的内容某些 OI 比赛不支持。慎用！

gcc 存在内置函数： __builtin_expect(!!(x), tf)

当 tf 为 true 时表示 x 非常可能为 true ，反之同理。

用法： if(__builtin_expect(!!(x), tf))

编者附：

而 GCC 提供了一个内建函数 __builtin_expect ，通过分支预测提高效率，将接下来运行的可能性较大的代码放在靠前的位置，减少指令跳转，这样保证了空间局部性，可以减少 cache miss。但经过测试后发现， __builtin_expect 仅在开启 -O2 优化下有效。

例如下面的代码：
#include <cstdio>
#include <cstdlib>
int main() {
       srand(2333);
       int cnt1 = 0, cnt2 = 0;
       for (int i = 0; i < 1000000000; ++i) {
           int t = rand();
           if (t < 10)
               ++cnt1;
           else
               ++cnt2;
       }
       printf("%d %d\n", cnt1, cnt2);
   }
#include <cstdio>
#include <cstdlib>
int main() {
    srand(2333);
    int cnt1 = 0, cnt2 = 0;
       for (int i = 0; i < 1000000000; ++i) {
           int t = rand();
           if (__builtin_expect(t < 10, false))
               ++cnt1;
           else
               ++cnt2;
       }
       printf("%d %d\n", cnt1, cnt2);
   }
使用 __builtin_expect (t < 10, false) 后，编译器把 else 后的语句放到了紧跟着前面的语句的位置，而当 t < 10 为 true 时才进行跳转。

摘自：浅谈底层常数优化及编译器优化 - zhaojinxi 的博客 - 洛谷博客

# `switch` 和 `if-else` 的故事

下面有两段代码，你觉得那段更快呢？

	if (x == 1)
	x++;
	else if (x == 2)
	x *= 2;
	else if (x == 3)
	x /= 3;
	else if (x == 4)
	x >>= 1;
	else if (x == 5)
	x = 1;

	switch (x) {
	case 1:
	x++;
	break;
	case 2:
	x *= 2;
	break;
	case 3:
	x /= 3;
	break;
	case 4:
	x >>= 1;
	break;
	case 5:
	x = 1;
	}

显然地，下面的代码更快，因为上面的代码需要逐条判断，而下面的代码直接跳转。

那是不是所有 switch 都比 if 快呢？凡事没有绝对，当 switch 遇到 default 的时候，整个程序的效率就会大打折扣，因为它又回到了 if 的无脑判断模式。再比如，当 if 用来判断区间的时候就比 switch 快， if 只需要做三次逻辑运算（两条判断，一条逻辑与），而 switch 呢？我就呵呵一笑。

# 短路的故事

此短路非彼短路，它指的是一种运算符的特性。

我们常用的逻辑运算符，例如 && 和 || 都是短路运算符。什么意思呢？比如在运算 A && B 时，如果发现 A 已经为 false ，就不会再计算 B。

现在你能解释第一章中留下的问题了吗？

(tf)&&(sum=-sum); 当 tf 为 true 的时候，会执行后面的 sum=-sum ，如果 tf 为 false ，则不会执行后面的 sum=-sum 。

等价于如下语句：

if (tf) sum = -sum;

tf = ((ch == '-') && (ch = getchar()));

当 ch='-' 时，会执行后面的 ch=getchar() ，因为 getchar 一般不会等于 0 （如果不放心可以写成 tf=((ch=='-')&&((ch=getchar()),true)) ），因此 tf 的结果等于 true 。

当 ch!='-' 时，不会执行后面的 ch=getchar() ， tf 的值为 false 。

等价于如下语句：

	if (ch == '-') {
	tf = true;
	ch = getchar();
	}

总结一下：

	if(A) B; ⇔ (A)&&(B)
	if(A) B; else C; ⇔ A&&(B,1)\|\|C

为什么？详情参见下一小节。

如果短路运算符只能改写 if 语句，那这里就不会浪费这么多篇幅来介绍这个东西。事实上，这个东西比我们想象得有用得多。看下面两段代码：

	double t = rand();
	if (t / RAND_MAX < 0.2 && t != 0) printf("%d", t);

	double t = rand();
	if (t != 0 && t / RAND_MAX < 0.2) printf("%d", t);

你认为哪一份代码会更快？

好像没什么区别对吧。但对于 CPU 来说很有区别。第一段代码中的 t / RAND_MAX < 0.2 为 true 的概率约为 $20\%$ ，但 t!=0 为 true 的概率约为 $\frac{1}{RAND\_MAX}$ ，明显小于 20%。
因此，如果把计算一个不含逻辑运算符布尔表达式的计算次数设为 $1$ 次，设计算了 $X$ 次，则对于第一段代码， $X$ 的数学期望为 $65$ ，但对于第二段代码， $X$ 的数学期望为 $\frac{2\times (RAND\_MAX-1)}{RAND\_MAX}$ ，远远大于第一段代码。

总结一下，

遇到 A&&B 时，优先把可能为 false 的表达式放在前面。
遇到 A||B 时，优先把可能为 true 的表达式放在前面。

# 布尔表达式和逗号运算符的故事

为什么要专门设置这么一小节呢？
因为很多人喜欢用 if(x==true) ，直接用 if(x) 就好了。还有 x==false 和 !x ，它们也是等价的。

现在，请另一位大佬隆重登场：逗号运算符。

若干条语句可以通过逗号运算符合并成一条语句。
例如 t=a;a=b;b=t; 可以写成 t=a,a=b,b=t; 有什么用吗？它的返回值。

int x=(1,5,4,2,6,3,9);

猜一猜，上面的语句执行完后 x 的值是多少？

答案是 9。没错，逗号运算符的返回值就是最后一个的值。

现在可以解释上一小节留下总结了吧。

A&&(B,1)||C ：当 A 为 true 时会执行 (B,1) ，返回值为 true ，因此 A&&(B,1) 的返回值为 true ，因此不会执行 C ，当 A 为 false 时，不会执行 (B,1) ，且 A&&(B,1) 的值为 false ，因此会执行 C 。

# Standard Template Library

如果能熟练使用 STL，则可以大大减小代码复杂度，提高对于部分人的可读性（前提是那个人也会 STL）。但在很多 OI 比赛中，STL 会成为性能瓶颈（不仅仅是常数瓶颈），而且要明白：对于 STL 来说， -O2 的开与否带来的不仅仅是几毫秒的差，而是一种蜕变！

# 容器

# 完全连续容器

在 STL 中，唯一的真正意义上的完全连续容器应该只有 vector 和 bitset 了，其中， vector 中的所有元素都是连续的，但它是怎么做到的？在某些编译器中，它实现内存分配的方法是当前的容量不足时，申请一块当前容量 2 倍的新内存空间，然后将所有的老元素全部拷贝到新内存中，添加大量元素的时候的花费的惊人的大。和 allocator 的时间复杂度一样。

函数原型： extern void *realloc(void *memory, unsigned int newsize);

作用：把 memory 开头的指针所占用的空间修改成 newsize 个字节大小。

内部是怎么实现的？在内存中寻找一片足够大的连续空间，然后把原来地方的数据拷到新空间中。

听着就觉慢，因此在 vector 需要存储大量数据的时候，尽量不要用 push_back ，直接用 resize(size_type size) 函数改变大小，或者先用 reserve(size_type size) 函数预留空间，然后再用 push_back 方法，这样能尽可能地降低其弊端。

但由于其是完全连续容器，因此在查找的时候效率和普通数组没有太大区别。

邻接表有两种实用的方法，一种是前向星（有人也叫向前星，这里以百度百科为准），另一种就是用 vector 。

尽管 vector 修改大小的时候会很浪费时间，但要知道， vector 可是一个完全连续容器，相比前向星好了不知道多少（从一个数组里跳来跳去）。

在某些需要频繁访问边（例如网络流和最短路），遇到很稠密的图的时候， vector 完全连续的作用就被发挥到了最大，而动态开辟空间的消耗也已被降到了最低最低，尤其是在开了 -O2 优化的时候。

下面分别是 vector 和前向星跑网络流（ISap）的用时。（ $m=50n$ ）

存图方法	编译器	$n=10^4$	$n=10^5$	$n=5 \times 10^5$
`vector`	G++ 5.4.0	501ms	1108ms	5103ms
`vector`	G++ 5.4.0 ( `-O2` )	365ms	794ms	3855ms
前向星	G++ 5.4.0	478ms	1025ms	5111ms
前向星	G++ 5.4.0 ( `-O2` )	477ms	1017ms	5109ms

十分明显地，开了 -O2 优化的 vector 跑得飞快，而随着数据大小的上升，vector 的速度也越来越快。

bitset 的大小是在编译时就被固定了，因此不会出现和 vector 一样浪费时间的情况。它的最大作用是节约空间。那里节约空间了？要知道，C++ 的任何类型都至少占用一个字节，包括 bool 。因此， bool 会浪费七个字节的空间。但其实 bitset 也是可以自己实现的。

编者注：原文内容存在争议，已删除。通常情况下， int 运算速度比 long long 快不少。

# 部分连续容器

如果你认为 queue （一种容器适配器）和 deque 应该在上一章出现，那你就错了。事实上，它们并不是完全连续容器。它们内部的实现有点诡谲。为什么这样说呢？因为它们在内存中是部分连续的，也就是说，当内存不够的时候，它们就会再申请一段，然后再连接过去，因此在内存中，它们是不完全连续的，是多个内存块组成的，每个块中存放的元素连续内存，而内存块又像链表一样连接起来。

因为有了这种方法，它们不需要每次申请空间时，都像 vector 一样复制原来的元素。而是可以在常数时间内完成这个操作。因为它们在内存中是不完全连续的，因此速度不会太低。也可以很好地避免循环队列大小估计错误的可能。

但要注意是否会出现对空队列取队首或出队的操作，而且由于每次都会申请一大段的连续空间，因此需要注意空间的开销。

当我做完测试后却大吃一惊。

实现方法	编译器	时间
arr: `queue`	G++ 5.4.0	25 ms
arr: `queue`	G++ 5.4.0 ( `-O2` )	15 ms
stl: `queue`	G++ 5.4.0	433 ms
stl: `queue`	G++ 5.4.0 ( `-O2` )	31ms
arr: `deque`	G++ 5.4.0	16 ms
arr: `deque`	G++ 5.4.0 ( `-O2` )	4 ms
stl: `deque`	G++ 5.4.0	850 ms
stl: `deque`	G++ 5.4.0 ( `-O2` )	58 ms

为什么会出现这种情况？

其实 queue 默认实现方法是封装 deque ，通过更改模板参数可以使用 vector 和 list 实现。而 deque 呢？由于其内存不完全连续，因此导致了过多的内存跳转，浪费了大量时间，由此可得，部分连续容器和完全连续容器的效率差极大。

因此，在能使用连续空间的情况下，尽可能地使用完全连续容器。

# 节点容器

节点容器就比较多了。常见的 map ， set 和 list 都属于它的范畴。

其中， list 有点像 deque ，和其原理差不多，只是内存块的大小恒为 1，插入和删除都可以在常数时间内完成。唯一的缺点是不支持二分查找和随机访问。而且由于 list 是不连续容器，因此它的查询会导致内存频繁地跳转，因此只有在经常需要增加或删除的时候才会考虑使用 list 。

set 和 map 属于关联容器，关联容器支持高效的关键字查找和访问，内部是以一种叫做红黑树的 BST 实现的，但它太复杂了，它的插入有 5 种情况，删除有 6 种情况，是 “当今信息界中平均速度最快的 BST”，比我们在 OI 比赛中有能力在时间内手动实现的 BST 快得多。

因此， set 和 map 的查询时间和红黑树的时间复杂度一致，基本上所有操作都是 $\log size$ 级别的，包括迭代器的 ++ 和 — 操作，它们在 BST 中相当于求前驱和后继。而且由于它们是节点容器，因此在内存中是断续的，反复地跳转可能导致更多的开销。

但当需要自己实现部分（不包括一些特别的功能，例如求排名）平衡树的功能时，用 set 和 map 一般会比手写更优。

如果遇到了不能用 set 和 map 的情况，并不推荐用 Splay，因为它的常数太大了，这里推荐一种极好的 BST: 替罪羊树 (Scapegoat Tree)，它的思想非常简单：当且仅当某棵子树的不平衡度超过 $\alpha$ 时，暴力重构整棵子树，从而避免了旋转的操作。

本文转载自：https://blog.csdn.net/qq_40155097/article/details/83083051

原作者：Victor Miller

CSP-S 2020 游记 & NOIP 2020 爆零记

2020-11-14T16:00:00.000Z

~~不会真有人现在才写游记吧（~~

# CSP-S1

~~没啥好说的，莫名其妙就 72.5 分了。~~

居然用高考答题卡考 CSP，~~不愧是 €€£~~。

阅读程序出现了史无前例的 99 行程序，~~就差破个百了~~。

C++：终于想起我是门面向对象语言了？

考后打了张 Excel 算了下分，居然发现最后 5 分钟蒙对了两道 4 分题，总计 8 分！~~（虽然说就算没蒙对也能过分数线）~~

# CSP-S2

考场：广东大学附属中学（大学城校区）

# 开局：出师不利

~~某位同学高兴地一路狂奔…… 然后扑街了。（开幕雷击）~~

我也没好哪去，跟着人群走，走到 4 楼才发现走错楼了……

开考前 15 分钟，才发现没打印疫情须知，还好监考老师有，~~差点当场退役~~。

匆匆忙忙填完须知，监考老师在名单上看了又看，我才意识到走到隔壁考场去了……

这次考场不能带水进去，可能是怕由于打翻水壶而引发的 “机房惨案”。

考试机器居然装的是 Windows 10（神州网信版）！AMD 6-Core CPU! 8 GiB Memory!

先习惯性在机子里到处翻翻，在 C 盘发现一个神秘文件夹，文件夹里有一压缩包，压缩包里又有一压缩包（迷惑），里面居然有 Sublime Text 3 的安装包！~~可把我激动坏了。~~

考试机默认装了 Dev C++ 5.9，然而在刚刚的压缩包里找找就会找到一个 Dev C++ 5.11 的安装包（迷惑 x2）。（即便如此也不能阻止我 NOIP 上由于 Dev C++ 过于智能而导致函数没写返回类型也不会报错的 CE 爆零惨案。）

以及，与以往不同的是，~~难得良心的~~ CCF 居然给了一个检查选手目录正确性的 EXE 程序，~~再也不用担心因建错目录而爆零了（事实证明，该爆的零总是逃不掉的）~~。

桌面名为的 NOI 文件夹里还真有 NOI Linux 的虚拟机，然而并没有时间玩。

居然没有扫雷，CSP 上玩扫雷的愿望破灭了（（（

# 开赛：逐渐暴躁

T1 儒略日转公制日。上来一道大模拟，跳了。

T3 看起来比较简单，打个大暴力。

回头想了想 T1，没啥思路。

（上厕所以获取灵感）

上完厕所回来还是没思路，开始打 T2。T2 二进制状态压缩，看起来似乎挺简单的，结果遇到玄学 bug，调半天调不出来，傻了。

然后回头搞 T1，打了个一直 NextDay 的暴力，最后一个小时分段打表，然而表的大小没打对，大样例也没过。

最后 15 分钟给 T2 和 T4 输出个样例和随机数。好像 4 个小时也没干啥就结束了。

# 赛后：直呼凉凉

考完试出来居然天已经黑了。

路上听到有人只做出 T1，T2 输出了个 0（

听到旁边座位的初中大佬居然做出 300 分！（我太蒻了）

由于 T2 玄学 bug 没调出来，考完直呼凉凉。

~~好像学了一个多月的提高组内容，除了快读和分段打表，其余正经的一个没用上（（（~~

（广州停车位是真的难找）

# 后续：我又活（炸）了

第二天洛谷出民间数据，靠着记忆把考场上 T1 的代码打完才想起有 "公开选手代码" 这回事（去年我好像都没见过 "选手代码" 这玩意）。

拿选手代码在洛谷的民间数据上一测：

T1	T2	T3	T4	Total
30 pts	85 pts (WTF?!)	10 pts	0 pts	125 pts

~~我可真是谢谢您老 Dev C++ 嘞。~~

T3 暴力以为用不着 long long （考前看别人博客说 int 比 long long 快不少），于是就没开 long long ，结果 $35 pts \to 10 pts$ ……

最终成绩：

T1	T2	T3	T4	Total
30 pts	95 pts（针不戳）	10 pts	0 pts	135 pts

GD 一等分数线 150 pts，我的一等啊…… 我的蓝勾……

总结：不开 long long 见祖宗。

# NOIP

# Before 赛前

开考前一天跟 HY 的大佬们打了一场~~被巨佬称为 “便秘比赛” 的~~模拟水题赛，极其欢乐。

根据约定，我们这些 ~~AKIOI 的~~高中学长们不能抢首 A，于是……

# 赛前

加一条命！

来得挺早，见到了 HY ~~比我小然而比我强~~的大佬们，还有以前的 OI 老师。

同一个考场，同一个考室，~~同样的倒霉运气~~。

有了上次的经验，一顿基本操作，解压，装 Sublime Text 3、Dev C++ 5.11，看题。

T1 图论， $m \leq 10$ ，好像暴力能过？吸取教训，开 long long ，大样例全文比对，手造极限数据（我太蒻了不会对拍），~~然而还是逃脱不了爆零的命运~~。

T2 字符串，考前一星期刚好看到 KMP（我太蒻了），想着估计不会考就没往下看……

T3 SPJ! NOIP 历史上第一次 Special Judge!（插播新闻：SPJ 惨遭 Hack）

T4 看起来很可做，上暴力。

最后 1h 纠结做 T2 还是 T3，决定打 T2 部分分，结果暴力没调出来……

最后 2 分钟开了 NOI Linux 虚拟机玩玩，结果不知道密码（不会有人现在还不知道 NOI Linux 的密码是 123456 吧），溜了。

# 赛后

针不戳！我觉得我 T1 能 AC！

啥？T1 入度为 0 的点不一定是接收口？

CCF 说没坑，那没事了。

啥？T1 要打高精？

哦，就 10 分，那没事了。

啥？我 T1 函数没写返回值？

哦，CE 了，那没事了。

结局：T1 惨遭爆零。

最终成绩：

T1	T2	T3	T4	Total
0 pts	0 pts	0 pts	35 pts	35 pts

总结：没事别用 inline ，多用用 NOI Linux。

2020 CSP-S 游记 & NOIP 2020 爆零记，完。

【转载】蒟蒻的宝书 - 新版骗分导论

2020-10-06T16:00:00.000Z

一年前打 CSP-J 时，学校的信息学老师给了我这篇《蒟蒻的宝书》。正是因为如此，最后我通过骗来的 15 分过了一等线。

由于原帖及目前网络上的转载贴排版普遍都很难看，因此在此转载并重新排版。

夹带私货：宝藏

2020-12-30 更新：所有数学公式已使用 $\LaTeX$ 重写，全文已根据排版标准进行优化。

新版骗分导论

THE NEW GUIDE OF CHEATING IN INFORMATICS OLYMPIAD

蒟蒻的宝书

全网排版最优的《骗分导论》

转载 & 排版 By Fidel

# 目录

# 第 1 章绪论

在 OIer 中，有一句话广为流传：

任何蒟蒻必须经过大量的刷题练习才能成为大牛乃至于神牛。

这就是著名的 lzn 定理。然而，我们这些蒟蒻们，没有经过那么多历练，却要和大牛们同场竞技，我们该怎么以弱胜强呢？

答案就是：

骗分

那么，骗分是什么呢？骗分就是用简单的程序（比标准算法简单很多，保证蒟蒻能轻松搞定的程序），尽可能多得骗取分数。

让我们走进这本《新版骗分导论》，来学习骗分的技巧，来挑战神牛吧！

# 第 2 章从无解出发

# 2.1 无解情况

在很多题目中都有这句话：“若无解，请输出 $-1$ .”

看到这句话时，骗分的蒟蒻们就欣喜若狂，因为 —— 数据中必定会有无解的情况！那么，只要打出下面这个程序：

printf("-1");

就能得到 10 分，甚至 20 分，30 分！

举个例子：

文化之旅（NOIP 2012 普及组第 4 题）

题目描述

有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。

现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使者游历的起点和终点（在起点和终点也会学习当地的文化），国家间的道路距离，试求从起点到终点最少需走多少路。

输入格式

第一行为五个整数 $N,K,M,S,T$ ，每两个整数之间用一个空格隔开，依次代表国家个数（国家编号为 $1$ 到 $N$ ），文化种数（文化编号为 $1$ 到 $K$ ），道路的条数，以及起点和终点的编号（保证 $S$ 不等于 $T$ ）；

第二行为 $N$ 个整数，每两个整数之间用一个空格隔开，其中第 $i$ 个数 $C_i$ ，表示国家 $i$ 的文化为 $C_i$ 。

接下来的 $K$ 行，每行 $K$ 个整数，每两个整数之间用一个空格隔开，记第 $i$ 行的第 $j$ 个数为 $a_{ij}$ ， $a_{ij}=1$ 表示文化 $i$ 排斥外来文化 $j$ （ $i$ 等于 $j$ 时表示排斥相同文化的外来人）， $a_{ij}= 0$ 表示不排斥（注意 $i$ 排斥 $j$ 并不保证 $j$ 一定也排斥 $i$ ）。

接下来的 $M$ 行，每行三个整数 $u,v,d$ ，每两个整数之间用一个空格隔开，表示国家 $u$ 与国家 $v$ 有一条距离为 $d$ 的可双向通行的道路（保证 $u$ 不等于 $v$ ，两个国家之间可能有多条道路）。

输出格式

一个整数，表示使者从起点国家到达终点国家最少需要走的距离数（如果无解则输出 $-1$ ）。

输入输出样例

输入 #1
2 2 1 1 2
1 2
0 1
1 0
1 2 10
输出 #1
-1
输入 #2
2 2 1 1 2
1 2
0 1
0 0
1 2 10
输出 #2
10
数据范围及提示

【输入输出样例 1 说明】

由于到国家 $2$ 必须要经过国家 $1$ ，而国家 $2$ 的文明却排斥国家 $1$ 的文明，所以不可能到达国家 $2$ 。

【输入输出样例 2 说明】

路线为 $1 \to 2$ 。

【数据范围】

对于 20% 的数据，有 $2≤N≤8$ ， $K≤5$ ；

对于 30% 的数据，有 $2≤N≤10$ ， $K≤5$ ；

对于 50% 的数据，有 $2≤N≤20$ ， $K≤8$ ；

对于 70% 的数据，有 $2≤N≤100$ ， $K≤10$ ；

对于 100% 的数据，有 $2≤N≤100$ ， $1≤K≤100$ ， $1≤M≤N^2$ ， $1≤k_i≤K$ ， $1≤u,v≤N$ ， $1≤d≤1000$ ， $S≠T$ ， $1≤S, T≤N$ 。

这道题看起来很复杂，但其中有振奋人心的一句话 “输出 $-1$ ”，我考试时就高兴坏了（当时我才初一，水平太烂），随手打了个 printf("-1"); ，得 10 分。

# 2.2 样例 —— 白送的分数

每道题目的后面，都有一组 “样例输入” 和 “样例输出”。它们的价值极大，不仅能初步帮你检验程序的对错 **（特别坑的样例除外）**，而且，如果你不会做这道题（这种情况蒟蒻们已经司空见惯了），你就可以直接输出样例！

编者注：现在 NOIP 的样例大部分都很坑。~~（用心造数据，用脚造样例）~~

例如美国的 USACO，它的题目有一个规则，就是第一组数据必须是样例。那么，只要你输出所有的样例，你就能得到 100 分（满分 1000）！这是相当可观的分数了。

现在，你已经掌握了最基础的骗分技巧。只要你会基本的输入输出语句，你就能实现这些骗分方法。那么，如果你有一定的基础，请看下一章 —— 我将教你怎样用简单方法骗取部分分数。

# 第 3 章 “艰苦朴素永不忘”

本章的标题来源于《学习雷锋好榜样》的一句歌词，但我不是想教导你们学习雷锋精神，而是学习骗分！

看到 “朴素” 两个字了吗？它们代表了一类算法，主要有模拟和 DFS 。下面我就来介绍它们在骗分中的应用。

# 3.1 模拟

所谓模拟，就是用计算机程序来模拟实际的事件。例如 NOIP 2012 的 “寻宝”，就是写一个程序来模拟小明上藏宝塔的动作。

较繁的模拟就不叫骗分了，我这里也不讨论这个问题。

模拟主要可以应用在骗高级数据结构题上的分，例如线段树。下面举一个例子来说明一下。

排队 (USACO 2007 January Silver)

题目描述

每天，农夫约翰的 $N$ （ $1≤N≤50000$ ）头奶牛总是按同一顺序排好队，有一天，约翰决定让一些牛玩一场飞盘游戏（Ultimate Frisbee），他决定在队列里选择一群位置连续的奶牛进行比赛，为了避免比赛结果过于悬殊，要求挑出的奶牛身高不要相差太大。

约翰准备了 $Q$ （ $1≤Q≤180000$ ）组奶牛选择，并告诉你所有奶牛的身高 $H_i$ （ $1≤ H_i ≤10^6$ ）。他想知道每组里最高的奶牛和最矮的奶牛身高差是多少。

编者注：修正了 $Q$ 的数据范围，原文为 $1≤Q≤200000$ 。

注意：在最大的数据上，输入输出将占据大部分时间。

输入格式

第一行，两个用空格隔开的整数 $N$ 和 $Q$ 。

第 $2$ 到第 $N+1$ 行，每行一个整数，第 $i+1$ 行表示第 i 头奶牛的身高 $H_i$

第 $N+2$ 到第 $N+Q+1$ 行，每行两个用空格隔开的整数 $A$ 和 $B$ ，表示选择从 $A$ 到 $B$ 的所有牛（ $1 ≤ A ≤ B ≤ N$ ）

输出格式

共 $Q$ 行，每行一个整数，代表每个询问的答案。

输入输出样例

输入 #1
6 3
1
7
3
4
2
5
1 5
4 6
2 2
输出 #1
6
3
0

对于这个例子，大牛们可以写个线段树，而我们蒟蒻，就模拟吧。

附模拟程序：

	for (int i = 1; i <= q; i++) {
	scanf("%d%d", &a, &b);
	int min = INT_MAX, max = INT_MIN;
	for (int i = a; i <= b; i++) {
	if (h[i] < min) min = h[i];
	if (h[i] > max) max = h[i];
	}
	printf("%d\n", max-min);
	}

程序简洁明了，并且能高效骗分。本程序得 50 分。

# 3.2 万能钥匙 ——DFS

DFS 是图论中的重要算法，但我们看来，图论神马的都是浮云，关键就是如何骗分。下面引出本书的第 2 条定理：

DFS 是万能的。

这对于你的骗分是至关重要的。比如说，一些动态规划题，可以 DFS；数学题，可以 DFS；剪枝的题，更能 DFS。下面以一道省选题为例，解释一下 DFS 骗分。

采药 (NOIP 2005 普及组第 3 题）

编者注：修正了题目来源，原文为 “NOIP2003”

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

输入第一行有两个整数 $T$ （ $1 \leq T \leq 1000$ ）和 $M$ （ $1 \leq M \leq 100$ ），用一个空格隔开， $T$ 代表总共能够用来采药的时间， $M$ 代表山洞里的草药的数目。接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$ ）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

输入输出样例

输入 #1
70 3
71 100
69 1
1 2
输出 #1
3
数据范围及提示

对于 $30\%$ 的数据， $M \leq 10$ ；
对于全部的数据， $M \leq 100$ 。

这题的方法很简单。我们瞄准 20% 的数据来做，可以用 DFS 枚举方案，然后模拟计算出最优解。附一个大致的代码：

	void DFS(int d,int c) {
	if (d == n) {if (c > ans) ans = c; return;}
	DFS(d + 1, c + w[i]);
	DFS(d + 1, c);
	}

# 第 4 章骗分的关键 —— 猜想

# 4.1 听天由命

如果你觉得你的人品很好，可以试试这一招 —— 输出随机数。

先看一下代码：

	#include<stdlib.h>
	#include<time.h>
	// 以上两个头文件必须加
	srand(time(NULL));
	// 输出随机数前执行此语句
	printf("%d",rand()%X);
	// 输出一个 0~X-1 的随机整数。

这种方法适用于输出一个整数（或判断是否）的题目中，答案的范围越小越好。让老天决定你的得分吧。

据说，在 NOIP 2013 中，有人最后一题不会，愤然打了个随机数，结果得了 70 分啊！！

# 4.2 猜测答案

有些时候，问题的答案可能很有特点：对于大多数情况，答案是一样的。这时，骗分就该出手了。你需要做的，就是发掘出这个答案，然后直接输出。

有时，你需要运用第 3 章中学到的知识，先写出朴素算法，然后造一些数据，可能就会发现规律。

例如，本班月赛中有一道题：

炸毁计划

问题描述

皇军侵占了通往招远的黄金要道。为了保护渤海通道的安全，使得黄金能够顺利地运送到敌后战略总指挥地延安，从而购买战需武器，所以我们要通过你的程序确定这条战略走廊是否安全。

已知我们有 $N$ 座小岛，只有使得每一个小岛都能与其他任意一个小岛联通才能保证走廊的安全。每个小岛之间只能通过若干双向联通的桥保持联系，已知有 $M$ 座桥， $(A_i,B_i)$ 表示第 $i$ 座桥连接了 $A_i$ 与 $B_i$ 这两座城市。

现在，敌人的炸药只能炸毁其中一座桥，请问在仅仅炸毁这一座桥的情况下，能否保证所有岛屿安全，都能联通起来。

现在给出 $Q$ 个询问 $C_i$ ，其中 $C_i$ 表示桥梁编号，桥梁的编号按照输入顺序编号。每个询问表示在仅仅炸毁第 $C_i$ 座桥的情况下能否保证所有岛屿安全。如果可以，在输出文件当中，对应输入顺序输出 yes ，否则输出 no （输出为半角英文单词，区分大小写，默认为小写，不含任何小写符号，每行输出一个空格，忽略文末空格）。

输入格式

第一行三个整数 $N,M,Q$ ，分别表示岛屿的个数，桥梁的个数和询问的个数。

第二行到第 $M+1$ 行每行两个整数。第 $i+1$ 行有两个整数 $A_i,B_i$ 表示这个桥梁的属性。

第 $M+2$ 行有 $Q$ 个整数 $C_i$ 表示查询。

输出格式

$Q$ 行，表示查询结果。

输入输出样例

输入 #1
2 1 1
1 2
1
输出 #1
no
数据范围

对于 80% 的数据， $N≤100$ 。
对于 100% 的数据， $N≤1000$ ， $N,Q≤M≤2000$ 。

你发现问题了吗？那么多座桥，炸一座就破坏岛屿的联系，可能性微乎其微（除非特别设计数据）。那么，我们的骗分策略就出来了：对于所有询问，输出 yes . 果然，此算法效果不错，得 80 分。

现在知道猜测答案的厉害了吧？

# 4.3 寻找规律

首先声明：本节讲的规律不是正当的算法规律，而是数据的特点。

某些题目会给你很多样例，你就可以观察他们的特点了。有时，数据中的某一个（或几个）数，能通过简单的关系直接算出答案。

只要你找到了规律，在很多情况下你都能得到可观的分数。

这样的题目大多出现在 NOI 或更高等级的比赛中，本人蒟蒻一个，就不举例了。传说某人去省选时专门琢磨数据的规律，结果有一题得了 30 分。

# 4.4 小数据杀手 —— 打表

我认识一个人，他在某老师家上 C 语言家教，老师每讲一题，他都喊一句：“打表行吗？”

他真的是打表的忠实粉丝。表虽然不能乱打，但还是很有用的。

先看一个例子：

栈（NOIP 2003 普及组第 3 题）

题目背景

栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。

栈有两种最重要的操作，即 pop（从栈顶弹出一个元素）和 push（将一个元素进栈）。

栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。

题目描述

宁宁考虑的是这样一个问题：一个操作数序列， $1, 2, \dots, n$ （图示为 1 到 3 的情况），栈 A 的深度大于 $n$ 。

现在可以进行两种操作，

将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的 push 操作）

将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的 pop 操作）

使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由 1 2 3 生成序列 2 3 1 的过程。

（原始状态如上图所示）

你的程序将对给定的 $n$ ，计算并输出由操作数序列 $1, 2, \dots, n$ 经过操作可能得到的输出序列的总数。

输入格式

输入文件只含一个整数 $n$ （ $1≤n≤18$ ）。

输出格式

输出文件只有一行，即可能输出序列的总数目。

输入输出样例

输入 #1
3
输出 #1
5

这题看似复杂，但数据范围太小， $n \leq 18$ 。所以，骗分程序就好写了：

	int a[18] = {1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700};

	scanf("%d", &n):
	printf("%d", ans[n-1]);

测试结果不言而喻，AC 了。

学完这一章，你已基本掌握了骗分技巧。下面的内容涉及一点算法知识，难度有所增加。蒟蒻中的蒟蒻可以止步于此了。

编者注：在某些 OI 中，提交的代码长度会有限制。当打的表过大时，可以试试分段打表和状压打表。

# 第 5 章做贪心的人

# 5.1 贪心的算法

给你一堆纸币，让你挑一张，相信你一定会挑面值最大的。其实，这就是贪心算法。

贪心算法是个复杂的问题，但你不用管那么多。我们只关心骗分。给你一个问题，让你从一些东西中选出一些，你就可以使用贪心的方法，尽量挑好的。

举个例子：这是我们的市队选拔的一道题。

有趣的问题

问题描述

2013 年的 NOIP 结束后， Smart 发现自己又被题目碾压了，心里非常地不爽，于是暗下决心疯狂地刷数学题目，做到天昏地暗、废寝忘食，准备在今年的中考中大展身手。

有一天，他在做题时发现了一个有趣的问题：

给定 $n$ 个二元组 $(a_i, b_i)$ ，记函数：

$y=100 \frac{\sigma(a_i)}{\sigma(b_i)}$

将函数 $y$ 的值四舍五入取整。

现将 $n$ 个二元组去掉其中的 $k$ 个计算一个新的 $y$ 值（也四舍五入取整），均能满足： $y \leq z$ ，求出最小的 $z$ 值。

Smart 想让你帮他一起找出最小的 $z$ 值。

输入格式

输入包含多组测试数据。

每组测试数据第一行两个整数： $n$ 和 $k$ ；

第二行为 $n$ 个数： $a_1, a_2, \dots, a_n$ ；

第三行为 $n$ 个数： $b_1, b_2, \dots, b_n$ 。

输入数据当 $n,k$ 均为 $0$ 时结束。

输出格式

对于每组测试数据输出一行，即找出的最小的 $z$ 值。

注意：为避免精度四舍五入出现误差，测试点保证每个函数值与最终结果的差值至少为 $0.001$ 。

输入输出样例

输入 #1
3 1
5 0 1
5 1 6
4 2
1 2 7 9
5 6 7 9
0 0
输出 #1
83
100
数据范围

对于 40% 的数据： $n≤20$ ；

对于 70% 的数据： $n≤1000$ ；

对于 100% 的数据： $n≤10000$ ， $a_i,b_i$ 都在 int 范围内。

这题让人望而生畏，但我们有贪心的手段。每个二元组的 $a$ 值是乘到答案中的，所以 a 越大越好，那么只要选择出最小的 $k$ 个去掉即可。代码就不写了，因为这个涉及到下一章的内容：排序。

此代码得 20 分。

# 5.2 贪心地得分

我们已经学了很多骗分方法，但他们中的大多效率并不高，一般能骗 10~20 分。这不能满足我们的贪心。

然而，我们可以合成骗分的程序。举个最简单的例子，有些含有无解情况的题目，它们同样有样例。我们可以写这个程序

	if (是样例) printf(样例);
	else printf("-1");

这样也许能变 10 分为 20 分，甚至更多。

当然，合并骗分方法时要注意，不要重复骗同一种情况，或漏考虑一些情况。

大量能骗分的问题都能用此法，大家可以试试用新方法骗 2.1 中的例子 “文化之旅”。

# 第 6 章 C++ 的福利

（请 P 党们跳过本章，这不是你们的福利）

在 C++ 中，有一个好东西，名唤 STL，被万千 OIer 们所崇拜，所喜爱。下面让我们走进 STL。

# 6.1 快速排序

快速排序是一个经典算法，也是 C++ 党的经典福利。他们有这样的代码：

	#include<algorithm> // 这是必须的
	std::sort(A,A+n); // 对一个下标从 0 开始存储，长度为 n 的数组升序排序

编者注：需要声明 std 命名空间。 std::sort(int , int ) 函数传入的第二个参数为待排序数组的最后一个元素的后一个元素的地址。

就这么简单，完成了 P 党一大堆代码干的事情。

# 6.2 “如意金箍棒”

C++ 里有一种东西，叫 vector 容器。它好比如意金箍棒，可以随着元素的数量而改变大小。它其实就是数组，却比数组强得多。

下面看看它的几种操作：

	#include<vector>
	using namespace std;

	vector<int> V; // 定义
	V.push_back(x); // 末尾增加一个元素 x
	V.pop_back(); // 末尾删除一个元素
	V.size(); // 返回容器中的元素个数

编者注：需要使用 vector 头文件和 std 命名空间，上述代码中添加了相应内容。

它同样可以使用下标访问。（从 0 开始）

编者注：添加了以下示例代码。

	V[0] = 1;
	printf("%d", V[0]);

# 第 7 章 “宁为玉碎，不为瓦全”

至此，我已介绍完了我所知的骗分方法。如果上面的方法都不奏效，我也无能为力。但是，我还有最后一招 ——

有句古话说：“宁为玉碎，不为瓦全”。我们蒟蒻也应有这样的精神。骗不到分，就报复一下，卡评测以泄愤吧！

卡评测主要有两种方法：一是死循环，故意超时；二是进入终端，卡住编译器。

先介绍下第一种。代码很简单，请看：

while(1);

就是这短短一句话，就能卡住评测机长达 10s，20s，甚至更多！对于测试点多、时限长的题目，这是个不错的方法。

第二种方法也很简单，但危害性较大，建议不要在重要比赛中使用，否则可能让你追悔莫及。它就是：

#include<con> //（windows 系统中使用）

或

#include</dev/console> //（Linux 系统中使用）

它非常强大，可以卡住评测系统，使其永远停止不了编译你的程序。唯一的解除方法是，工作人员强行关机，重启，重测。当然，我不保证他们不会气愤地把你的成绩变成 0 分。请慎用此方法。

# 第 8 章实战演练

下面我们来做一些习题，练习骗分技巧。

我们来一起分析一下 NOIP 2013 普及组的试题吧。

记数问题（NOIP 普及组 2013 第 1 题）

编者注：洛谷题目名称似乎错了。

题目描述

试计算在区间 $1$ 到 $n$ 的所有整数中。数字 $x(0 ≤ x ≤ 9)$ 共出现了多少次？例如，在 $1$ 到 $11$ 中，即在 $1,2,3,4,5,6,7,8,9,10,11$ 中。数字 $1$ 出现了 $4$ 次。

输入格式

输入共 $1$ 行，包含 $2$ 个整数 $n,x$ ，之间用一个空格隔开。

输出格式

输出共 $1$ 行，包含一个整数，表示 $x$ 出现的次数。

输入输出样例

输入 #1
11 1
输出 #1
4
数据范围

对于 100% 的数据， $1≤ n ≤ 1,000,000$ ， $0 ≤ x ≤ 9$ 。

表达式求值（NOIP 2013 普及组第 2 题）

题目描述

给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。

输入格式

输入仅有一行，为需要你计算的表达式，表达式中只包含数字、加法运算符 “ $+$ ” 和乘法运算符 “ $\times$ ” ，且没有括号，所有参与运算的数字均为 $0$ 到 $2^{31} - 1$ 之间的整数。

输入数据保证这一行只有 $0 \sim 9$ 、 $+$ 、 $×$ 这 $12$ 种字符。

输出格式

输出只有一行，包含一个整数，表示这个表达式的值。

注意：当答案长度多于 $4$ 位时，请只输出最后 4 位，前导 $0$ 不输出。

输入输出样例

输入 #1
1+1*3+4
输出 #1
8
输入 #2
1+1234567890*1
输出 #2
7891
输入 #3
1+1000000003*1
输出 #3
4
【输入输出样例说明】

样例 1 计算的结果为 $8$ ，直接输出 $8$ 。

样例 2 计算的结果为 $1234567891$ ，输出后 $4$ 位，即 $7891$ 。

样例 3 计算的结果为 $1000000004$ ，输出后 $4$ 位，即 $4$ 。

数据范围

对于 $30\%$ 的数据， $0≤ \text{表达式中加法运算符和乘法运算符的总数} ≤100$ ；

对于 $80\%$ 的数据， $0≤ \text{表达式中加法运算符和乘法运算符的总数} ≤1000$ ；

对于 $100\%$ 的数据， $0≤ \text{表达式中加法运算符和乘法运算符的总数} ≤100000$ 。

小朋友的数字（NOIP 2013 普及组第 3 题）

题目描述

有 $n$ 个小朋友排成一列。每个小朋友手上都有一个数字，这个数字可正可负。规定每个小朋友的特征值等于排在他前面（包括他本人）的小朋友中连续若干个（最少有一个）小朋友手上的数字之和的最大值。

作为这些小朋友的老师，你需要给每个小朋友一个分数，分数是这样规定的：第一个小朋友的分数是他的特征值，其它小朋友的分数为排在他前面的所有小朋友中（不包括他本人），小朋友分数加上其特征值的最大值。

请计算所有小朋友分数的最大值，输出时保持最大值的符号，将其绝对值对 $p$ 取模后输出。

输入格式

第一行包含两个正整数 $n,p$ ，之间用一个空格隔开。

第二行包含 $n$ 个数，每两个整数之间用一个空格隔开，表示每个小朋友手上的数字。

输出格式

输出只有一行，包含一个整数，表示最大分数对 $p$ 取模的结果。

输入输出样例

输入 #1
5 997
1 2 3 4 5
输出 #1
21
【输入输出样例 1 说明】

小朋友的特征值分别为 $1,3,6,10,15$ ，分数分别为 $1,2,5,11,21$ ，最大值 $21$ 对 $997$ 的模是 $21$ 。

输入 #2
5 7
-1 -1 -1 -1 -1
输出 #2
-1
【输入输出样例 2 说明】

小朋友的特征值分别为 $-1,-1,-1,-1,-1$ ，分数分别为 $-1,-2,-2,-2,-2$ ，最大值 $-1$ 对 7 的模为 $-1$ ，输出 $-1$ 。

数据范围

对于 $50\%$ 的数据， $1 ≤ n ≤ 1,000$ ， $1 ≤ p ≤ 1,000$ 所有数字的绝对值不超过 $1000$ ；
对于 $100\%$ 的数据， $1 ≤ n ≤ 1,000,000$ ， $1≤ p ≤ 10^9$ ，其他数字的绝对值均不超过 $10$ 。

车站分级（NOIP 2013 普及组第 4 题）

题目描述

一条单向的铁路线上，依次有编号为 $1, 2, \dots, n$ 的 $n$ 个火车站。每个火车站都有一个级别，最低为 1 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 $x$ ，则始发站、终点站之间所有级别大于等于火车站 $x$ 的都必须停靠。

（注意：起始站和终点站自然也算作事先已知需要停靠的站点）

例如，下表是 $5$ 趟车次的运行情况。其中，前 4 趟车次均满足要求，而第 $5$ 趟车次由于停靠了 3 号火车站（ $2$ 级）却未停靠途经的 $6$ 号火车站（亦为 $2$ 级）而不满足要求。

现有 $m$ 趟车次的运行情况（全部满足要求），试推算这 $n$ 个火车站至少分为几个不同的级别。

输入格式

第一行包含 $2$ 个正整数 $n, m$ ，用一个空格隔开。

第 $i + 1$ 行（ $1 ≤ i ≤ m$ ）中，首先是一个正整数 $s_i$ （ $2 ≤ s_i ≤ n$ ），表示第 $i$ 趟车次有 $s_i$ 个停靠站；接下来有 $s_i$ 个正整数，表示所有停靠站的编号，从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。

输出格式

输出只有一行，包含一个正整数，即 $n$ 个火车站最少划分的级别数。

输入输出样例

输入 #1
9 2 
4 1 3 5 6 
3 3 5 6
输出 #1
2
输入 #2
9 3 
4 1 3 5 6 
3 3 5 6 
3 1 5 9
输出 #2
3
数据范围

对于 $20\%$ 的数据， $1 ≤ n, m ≤ 10$ ；

对于 $50\%$ 的数据， $1 ≤ n, m ≤ 100$ ；

对于 $100\%$ 的数据， $1 ≤ n, m ≤ 1000$ 。

第 1 题，太弱了，不用骗，得 100 分。

第 2 题，数据很大，但是可以直接输入一个数，输出它 $\bmod 10000$ 的值。得 10 分。

第 3 题，是一道非常基础的 DP，但对于不知 DP 为何物的蒟蒻来说，就使用暴力算法（即 DFS）。得 20 分。

第 4 题，我们可以寻找一下数据的规律，你会发现，在所有样例中， $M$ 值即为答案。所以直接输出 $M$ ，得 10 分。

这样下来，一共得 140 分，比一等分数线还高 20 分！你的信心一定会得到鼓舞的。这就是骗分的神奇。

编者注：应该是弱省的分数线。

# 第 9 章结语

骗分是蒟蒻的有力武器，可以在比赛中骗得大量分数。相信大家在这本书中收获了很多，希望本书能帮助你多得一些分。

但是，最后我还是要说一句：

不骗分，是骗分的最高境界。

本文转载自：https://vijos.org/discuss/5343eb6c48c5fc86468b457d

为了更好的排版效果，部分题目参考了洛谷进行了修改。

以下为原作者信息：

作者：大神 cyd

QQ：724612372

考前推荐阅读：

OI 中简单的常数优化的介绍

复赛时要记住的 30 句话

怎么在 NOIP 用下划线开头的 STL

About Fidel's Lab

2020-04-04T16:00:00.000Z

此 About 页面及 Fidel's Lab 为目前的第三个版本。你可以在这里查看详细的更新日志。

~~现役 OIer~~ 已退役。

# RSS 订阅

RSS 是个好东西。它将每个人的不同系统、不同主题、不同排版的 Blog 集合成一种统一的信息格式，将浏览独立博客这种行为从「被动浏览」变为「伪主动推送」。

在我看来，RSS 不仅是一种技术上的革命，更是一种信息获取方式的革命。

您可以在这里获取 Fidel's Lab 的详细 RSS 订阅链接。

~~（虽然我知道这么写似乎不太优雅，但一下子想不到更好的措辞了 QwQ）~~

# 哪里可以找到我

GitHub：@Fidelxyz
洛谷 Luogu: @Fidel

# 一些技术性信息

Fidel's Lab 现采用的主题是 hexo-theme-shoka。

Docs: https://shoka.lostyu.me/computer-science/note/theme-shoka-doc/special/

Fidel's Lab 曾经采用的 Hexo 主题为基于 landspace 和 landscape-plus 的魔改版。

CSP-J 2019 游记 & 指引

2019-12-26T16:00:00.000Z

下面那篇 NOIP 比赛笔记其实是给我自己看的……

所以大家请看这篇 😃

彻底失去对 Luogu Blog 排版的信心。果然还是自己亲手搭的 Hexo 好用。

啧啧啧，我的 Hexo 排版真的好看。<_<

# 比赛前干啥

睡觉。

CSP-J 在下午，如果有时间，你还可以睡个中午觉。

~~不然你就只能在考场上睡了。~~

😃

临走前记得带上这些：

身份证
准考证
通讯工具
2 支或以上好写的笔（可以带几支不同颜色的）
纸巾
一个背包

水其实可以不用带。上车后会发一瓶，到了考场还有一瓶。当时我包里带了 3 瓶水回来，考场发的鼎湖山泉现在还放在我桌面上。

# 开考前干啥

进入考场之前，手机关机放背包里，不要带进去。

对了，你可以带吃的进去，神奇的 NOIP 允许你在考试时吃东西。

~~当然你也可以试试带榴莲或者榴莲糖、榴莲蛋糕之类的进去吃，规则上没说不给，不过不保证你能活着出来。😃~~

进入考场，先进入设置把屏幕分辨率从老人机模式调到原生分辨率，显示器亮度调到合适，鼠标键盘调到一个舒适的位置。检查机箱 USB 封条是否稳固。

桌面上有一个加密的压缩包，所有规则须知的文件，和一个编程程序文件夹。通读须知，C 盘下建好文件夹。设置编辑器环境。

# Dev C++

# 自动保存

「工具 -> 编辑器选项 - > 自动保存 -> 启动编辑器自动保存」打勾，文件名选择「附加格式化时间戳」

# 编译选项

「工具 -> 编译选项 -> 代码生成 / 优化 -> 连接器 -> 产生调试信息」 选择 YES

快捷键：启动调试 F5 下一步 F7

打开 -Wall

选择 C++ 编译器标准：ISO C++98

为了减少踢到电源线 / 考场停电 / 电脑死机时的损失，请打开自动保存。每做完一道题可以备份一份到 D/E/F 盘。

然后差不多开始做题了。

# 考试开始

输密码是一个会让人抓狂的环节，因为老师读给你的密码会是这样的：

=zhu1YI1JIAN1cha6（大小写拼音 + 数字）

实在难以想象一位有方言口音的老师读密码时的情景。

请先把密码打在记事本上，再复制密码解压。

解开压缩包之后，你就可以愉快地做题了。

一些小技巧和注意事项：

分屏大法，左边敲代码，右边看题目。
善用草稿纸。T3 T4 写代码前列需求点，画图。
记得加文件读写！
接上一条，测试时用文件测。

话说我当时的机子 Win 键貌似坏了…… Win + D 和 Win + Tab 用不了，难受。

比赛结束前 10 分钟就放弃治疗吧，别希望能绝杀。再三检查有没有去掉调试语句、是否能通过编译，文件输入输出是否正确，文件名和建立文件夹是否正确。

考场上如果没思路，建议多往厕所跑跑，厕所是一个很奇怪的地方，时常能在厕所获得灵感（雾）

# 大数据读写

电脑上装了 GVim，务必使用 GVim 打开大数据文件。（Notepad 打开会卡死）

使用 Vim 打开了文件，我们发现此时我们无法对文件进行操作

不要慌，Vim 默认开启时是 “命令” 模式，是需要输入指令来操作的

我们按下 i ，切换到插入模式，就可以愉快的写代码了

写完代码了，我们需要保存一下

那么问题来了，怎么保存呢

首先，我们按下 Esc 键 ~~（敲 ESC 三个字母的可以关掉 blog 直接退役了）~~，返回命令模式

然后，我们在命令模式下输入 :wq （均为小写英文字符），就可以保存文件并直接回到终端啦

语句解释： : 的作用是一次输入多条指令，上文中我们未使用 : 直接按 i 便是立刻执行命令，这里便会等待你一次输入全部命令回车后依次执行； w 是 Vim 的保存命令 ~~（不是 s 吗）~~ ； q 是退出指令

写不动了，下星期再接着写。

# 补充

# 2020-04-06

也没啥好写的了，差不多就这些。就这样吧。

祝大家

$RP++^{++^{++^{++^{++^{++^{++^{++^{++^{++^{++^{++^{++^{++^{++^{++^{++^{++^{++} } } } } } } } } } } } } } } } } }$

（从隔壁大佬那抄来的 RP+++++）

# 引用的文章

以梦为马，不负韶华 ——CSP2019 考前提醒
致 CSP 萌新 / 不会使用 NOI LINUX 的人群

NOIP 比赛笔记

2019-11-14T16:00:00.000Z

一点小笔记

祝大家 RP++

# 0x01 环境配置

# Dev C++

# 自动保存

「工具 -> 编辑器选项 - > 自动保存 -> 启动编辑器自动保存」打勾，文件名选择「附加格式化时间戳」

# 编译选项

「工具 -> 编译选项 -> 代码生成 / 优化 -> 连接器 -> 产生调试信息」 选择 YES

快捷键：启动调试 F5 下一步 F7
打开 -Wall
选择 C++ 编译器标准：ISO C++98

# Vim

:vsp ~/.vimrc

	set ts=4
	set sw=4
	set smarttab
	set number
	set expandtab
	color desert
	syntax on
	set cindent
	set guifont=Consolas:h16
	set backspace=2

	inoremap ( ()<ESC>i
	inoremap [ []<ESC>i
	inoremap { {}<ESC>i
	inoremap < <><ESC>i
	vmap <C-C> "+y
	vmap <C-V> "+p
	imap <C-V> <ESC>"+pa
	vmap <BACKSPACE> d
	imap <C-Z> <ESC>ua
	vmap <C-Z> uv
	imap <C-S> <ESC>:w<CR>a
	vmap <C-S> :w<CR>v
	imap <C-A> <ESC>ggVG
	vmap <C-A> ggVG

# 0x02 注意事项

由于 CSP 的评测是在 Linux 的环境下完成的，因此有一些注意事项需要注意：

尽量不要使用 gets() 语句读取一行，因为这些函数使用换行符来判断行结束，Windows 下换行是 \r\n ，而 Linux 下换行是 \n ，假设某题的数据是在 Windows 下生成的，那么这道题的换行符就是 \r\n ，最终比赛时的代码是在 Linux 下编译的，读取的换行符是 \n ，这样就会导致读入错误。

kkksc03 评论：其实不使用 gets() 的原因主要还是潜在的溢出风险。

评测环境为 Linux 64 位，因此请注意指针变量占用的空间是 8 字节，注意计算内存，避免 MLE。
在使用 long long 时请记得使用 %lld 而非 WIndows 下的 %I64d 。
忌使用 __ （双下划线）开头的函数。
int * int 乘法强转 long long ！
减少不必要的优化，以降低思维难度、减少代码量和出错为目标。
next , x0 , x1 , y0 , y1 , index 别作变量名！
注意 long long 级别的 INF 要开 0x3f3f3f3f3f3f3f3fll 。
long long 状压左移写 1ll 。
尽可能到 Linux 测样例！
比赛结束前 10 分钟就放弃治疗吧，别希望能绝杀。再三检查有没有去掉调试语句、是否能通过编译，文件输入输出是否正确，文件名和建立文件夹是否正确。
觉得该用 long long 就用！
注意检查函数是否写了返回值类型，尤其是 inline 后面！Windows 下不会报错，尽量到 Linux 下测一次！
别踢电源线！

# 0x03 小技巧 and Notes

# C++ 代码模板

	#include <cstdio>

	inline int read(){
	int x=0, f=1; char ch=getchar();
	while(ch<'0'\|\|ch>'9'){if(ch=='-') f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-48; ch=getchar();}
	return x*f;
	}

	int main(){
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);

	fclose(stdin);
	fclose(stdout);
	return 0;
	}

# 安全数组大小

记得开全局数组！!

	int a[5792][5792]; // 579257924/1024/1024≈128 MiB.
	int a[33554432]; // (≈310^7) 335544324/1024/1024= 128 MiB.

	int a[8192][8192]; // 819281924/1024/1024≈256 MiB.
	int a[67108864]; // (≈610^7) 671088644/1024/1024= 256 MiB.

	int a[11585][11585]; //11585115854/1024/1024≈512 MiB.
	int a[134217728]; // (≈10^8) 134217728*4/1024/1024= 512 MiB.

# 对拍

为了防止挂分，建议对拍，即用暴力和要提交的程序进行互相检测。

建议不会写数据生成器的同学恶补一下。

这里提供一种用 C++ 写的 Windows 对拍脚本，可以参考一下。

其中 data.exe 是数据生成器， std.exe 是暴力， test.exe 是要测的程序。

test.out 是要测的程序的输出文件， test.ans 是暴力的输出文件。

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

	int main(){
	for(int i = 1; ; i++) {
	Sleep(50);
	system("data.exe");
	system("std.exe");
	syetem("test.exe");
	printf("-----------Test Case %d----------\n",cas);
	if(system("fc test.out test.ans")) system("pause");
	}
	}

# 奇妙的语法

# `inline`

竞赛中尽量别用。

记得加函数返回值！

	inline void MyFunction() {
	// ...
	}

# 运算符重载

	struct MyStruct {
	int val;
	bool operator<(const MyStruct &u1) const {
	return val < u1.val;
	}
	}

# IO

# long long 读写

记得用 %lld ！

	long long a;
	scanf("%lld", &a); // 读写 long long 注意用 % lld
	printf("%lld", a);

# 整行读入

	#include <iostream>
	#include <string>

	std::string a;
	getline(cin, a);

# STL

# `#include<math>`

double pow(double x, double y); //x^y

请勿使用 cmath 库中的 abs 函数！

	//DO NOT USE THEM!!!
	int abs(int i);
	double fabs(double x);

C++ 有很多 ~~bug~~ 你想不到的事！

相信 OIers 经常盯着一个他认为没毛病的程序，找问题。一小时后，他把
#include<cmath>
abs(n);
改成
int myabs(int n){
 if(n>=0) return n;
 return -n;
}
后就 AC 了

来源：给所有准备竞赛的同学 - Nothing But Something - 洛谷博客

如果你非得要用 STL 的 abs ，请用 cstdlib 库中的。

# `#include<algorithm>`

sort 函数的第二个参数为待排序区间最后一个元素的后一个元素地址。

	#include <algorithm>

	int a[] = {/* ... */};

	std::sort(a, a + n); // 升序排序 a [0...n-1]
	std::sort(a + 1, a + n + 1); // 升序排序 a [1...n]

	bool cmp(int &u1, int &u2) { return u1 > u2; } // 重写比较函数

	std::sort(a, a + 1, cmp); // 降序排序 a [0...n-1]

# `#include<vector>`

当数组用

	#include <vector>

	std::vector<int> a;
	a.push_back(1);
	a.insert(a.begin() + 5, 1); // 插入
	a.reverse(a.begin(), a.end()); // 翻转
	a.size(); // 查询大小
	a.empty(); // 查询是否为空
	a.clear(); // 清空
	b.erase(b.begin(), b.begin() + 3); // 删除
	std::vector<int> b = a; // 复制，速度极快
	a.swap(b); // 交换

	for (vector<int>::iterator i = a.begin(); i != a.end(); i++) // 迭代器
	printf("%d ", *i);

# `#include<queue>`

	#include <queue>

	// Queue
	std::queue<int> q1; // 队列
	q1.push(1); // 压入
	q1.front(); // 查询队头元素
	q1.pop(); // 弹出
	q1.empty(); // 查询是否为空
	q1.size(); // 查询大小

	// Deque
	std::deque<int> q2; // 双端队列
	q2.push_back(1);
	q2.push_front(1);
	q2.pop_back(1);
	q2.pop_front(1);
	q2.back();
	q2.front();

	// Priority Queue
	std::priority_queue<int> q3; // 优先队列（自动排序的队列）
	// 默认升序排列，如果需要降序排列可重写小于号操作符 <

# `#include<utility>`

	#include<utility>

	std::pair<int, int> a = std::make_pair(1, 2);

# 0x7F 神奇的网站

数列推导式查询 OEIS

洛谷 luogu

# 引用 or 有帮助的文章

以梦为马，不负韶华 ——CSP2019 考前提醒
致 CSP 萌新 / 不会使用 NOI LINUX 的人群
Noi Linux 的使用
NOI Linux 使用心得
【模板】Noi-Linux 下的一些配置
C/C++ 字符串与数字相互转换
C++ sort 排序函数用法
C++ 中 vector 使用详细说明（转）

	#include <cstdio>
	#include <cstdlib>
	int main() {
	srand(2333);
	int cnt1 = 0, cnt2 = 0;
	for (int i = 0; i < 1000000000; ++i) {
	int t = rand();
	if (t < 10)
	++cnt1;
	else
	++cnt2;
	}
	printf("%d %d\n", cnt1, cnt2);
	}

Fidel's Lab

从 C++98 到 C++14 —— OIer 升级指南

# 启用 C++14

# 新特性

# auto

# decltype

# 范围 for 循环

# 模板相关

# 变量模板

# 可变模板形参

# Lambda 表达式

# 二进制字面量 & 数位分隔符

# 新 STL 库功能特性

# <unordered_set> & <unordered_map>

# <regex>

# 正则语法

# 匹配 ( std::regex_match )

# 搜索 ( std::regex_search )

# 分词 ( std::regex_token_iterator )

# 替换 ( std::regex_replace )

# <tuple>

「机房利器」、Coding on iPad? —— 记一次使用 Cloud Studio 云端开发的尝试

# 前置准备

# OI on Cloud Studio

# 创建工作空间

# 初步探索

# 命令面板 (Commands Panel)

# 命令行 / 终端 (Terminal)

# 设置 (Settings)

# C++ 相关组件安装及配置

# 编译器 (LLVM / Clang)

# 插件 (Extensions)

# C / C++

# Code Runner

# Compile and Run!

# Debug

# 用户代码片段

# 代码格式化 (clang-format)

# Hexo on Cloud Studio

# 创建工作空间

# 源代码迁移

# 运行服务器 & 网页预览

# VS Code 配置

# 额外组件安装及配置

# Markdown Preview Enhanced

# markdownlint

# Pangu-Markdown

# MarkDown Table Format

# Coding on iPad?

# 彩蛋

# References

【转载】还能这样玩——关于一些 OI 的黑 (sao) 科 (cao) 技 (zuo) 优化

# 免责声明

# GCC 系列

# O 系列

# -O1

# -O2

# -O3

# -Os

# 针对目标机器

# -march=cpu-type

# -mfpmath=unit

# 加载指定指令集

# 其他比较有效的选项

# -ftracer

# -ffast-math

# -fivopts

# -ftree-parallelize-loops=n

# -ftree-loop-linear

# -fforce-addr

# -floop-interchange

# -fvisibility=hidden

# -minline-all-stringops

# -m64

# -fprefetch-loop-arrays

# -pipe

# 推荐选项开关

# 底层优化（坑）

# I/O 优化

# 读入优化

# `auto`

# `decltype`

# 范围 `for` 循环

# `<unordered_set>` & `<unordered_map>`

# `<regex>`

# 匹配 ( `std::regex_match` )

# 搜索 ( `std::regex_search` )

# 分词 ( `std::regex_token_iterator` )

# 替换 ( `std::regex_replace` )

# `<tuple>`

# `-O1`

# `-O2`

# `-O3`

# `-Os`

# `-march=cpu-type`

# `-mfpmath=unit`

# `-ftracer`

# `-ffast-math`

# `-fivopts`

# `-ftree-parallelize-loops=n`

# `-ftree-loop-linear`

# `-fforce-addr`

# `-floop-interchange`

# `-fvisibility=hidden`

# `-minline-all-stringops`

# `-m64`

# `-fprefetch-loop-arrays`

# `-pipe`

# `if` 和 `?:` 的故事

# `switch` 和 `if-else` 的故事

# 第 1 章绪论

# 第 2 章从无解出发

# 第 4 章骗分的关键 —— 猜想

# 第 5 章做贪心的人

# 第 8 章实战演练

# 第 9 章结语