我在还有2天就参加机试的情况下，在1:4的神奇报录比之下，怀着忐忑不安的心情，以及近乎疲惫不堪的神经，但又充满着对网安的无限美好憧憬，将我这一个月来付出的一些努力进行汇总。（写完发现这是一个病句，但是这句话无足轻重，为了不重新组织这句话，我又写下了这句废话来搪塞。）
C 语言是每个理工科学生，或者说在当今中大交叉学科风气大盛行的时代下的每一个学生，如呼吸空气一般的简单技能，不必浪费笔墨（键盘）在这里赘述。
C++ 可视作是 C 语言的扩充，主要引入面向对象的特性。过多的理论并不能支撑在机试中取得良好表现，所以我只罗列重要的变化。
-
使用
iostream简易处理输入输出#include <iostream> using namespace std; cin >> a; cout << b;
在 C 语言中，有时为了安全处理 I/O，我们会手动解析用户输入，但这过于繁琐。使用
iostream的一些方法，可以根据对象的数据类型自动解析，非常省事。iostream同时实现了传统的cstdio的相关特性，因此可以放心弃用cstdio。 -
使用
algorithm高级方法 -
使用 C++ 样式的实现
我的原则是“优雅地实现”，因此在 C++ 环境里，应使用 C++ 样式的实现，即使兼容 C 语法样式。比如显式强制类型转换：
a = (int) b;
在 C++ 中应写作：
a = static_cast<int>(b);
有时看来
scanf会很方便（至少比手动解析强），但也仅限于 C 中，且它的不安全特性在任何一个 IDE 中都会被 Clang-Tidy 人人喊打。输入 % 和 & 也是一件令人痛苦地事情，所以又有什么理由不选择强大的 C++ Stream 语法呢？ -
使用 vector 来更加现代化地管理一组数据
如果不想被栈、堆内存管理折磨，请直接使用
vector，它是一个能让你在任何地方定义、以任何方法使用而无需过分担心内存管理的好东西。 -
无论什么时候都在变量声明后为它初始化一个合适的值
如果使用了变长数组等不支持初始化特性的变量，我的建议是：请立即转向 C++ 更现代化的实现方法，比如
new一个对象。 -
不要使用
switch这种低级易出错的用法，使用if-else代替 -
最好不要超过三层循环嵌套
数据量不大的情况下，三层嵌套是安全的，数据量较大的情况下，两层嵌套通常是安全的，数据量极大的情况下，请不要暴力枚举。
-
不要写未定义行为
不要写有歧义的代码，不要在同一行里写依赖于特定顺序才能正确执行的代码（如滥用运算符，括号不明确），不要写冗余代码，不要写不明意义的代码，不要想当然。想当然、不明意义的拍脑袋代码，在本地 debug 是无法被发现的，OJ 应用 O2 优化以后，会出现不明错误。
-
数组等作为循环条件时先检查边界
请勿越界访问，会报 RE。
-
使用现代化的
string类型存入字符串 -
无论什么时候都尽可能避免非现代化的实现
它们通常很麻烦，而且我们在考试时没有精力处理这些奇怪的错误。
-
使用迭代器
在
string、vector中最好使用迭代器，它们在大多数情况下更加灵活，且不容易引起错误，语义更清晰。区别是迭代器应当使用前导运算符，且需要在适时的情况下使用解引用、距离计算等语法。将迭代器赋值给变量，使用auto类型。 -
不要在 C 和 C++ 中互相转换 C++ 独有的数据类型
我也不知道这会不会出现一些问题。根据我秉持的“优雅实现”的理念，这一点也不够现代和优雅，在具有更新、更加安全、更加优雅、更加标准的实现方法下，我极度抗拒这些白痴用法，所以我完全忽略了所谓将
string转为字符数组等诸如此类抽象用法的知识。
以经验来看，需记住以下：
0 - 48，A - 65， a - 97
由于我的榆木脑袋瓜总是记不住运算符优先级的细节，故选择单开一节重申它。
| 优先级高 | 优先级低 | |||||||
|---|---|---|---|---|---|---|---|---|
| （、） | !、-（负号）、++、-- | *、/、% | +、- | <<、>>（左右位移） | <、>、>=、<= | ==、!= | && | || |
string 对象可以使用以下操作：
-
s.append(a)：将字符串a追加在原字符串的后面； -
s.substr(l, r)：返回从l起的r个字符； -
s.insert(l, a)：使索引为l的位置变为字符串a， 同时后移其他元素；（请勿在循环遍历枚举等操作中反复调用该方法，该方法时空复杂度较高，易导致 TLE，请考虑优化算法。） -
s.find(a, ptr)：从索引ptr的位置开始查找a第一次出现的位置，若找到，返回unsigned long long， 若未找到，返回std::string::npos。若要使用未找到情况下的值，请直接使用而不是应用强制转换，这在一些编译器中属于未定义行为。
从狭义来讲，在我看来，模拟不能称作一个算法。但在实际考试过程中，出现这类题基本就是一个炸弹。一个完全告诉你所有方法的题目，但题面足够的长，这一定会给你带来很大的震撼，甚至可以作为压轴题的存在。我总结了一些技巧：
-
输入：以恰当的形式组织需要输入到程序的内容，尤其要注意状态机思维，即利用变量对状态进行跟踪，需要搞清楚跟踪哪些内容才能维持程序在环境发生变化时改变行为，常见的状态有：
- 当前指针/位置/索引；
- 当前值/累计量
- 标记数组/条件数组
-
处理：这是难点。
-
先区分题面提到的多项规则，它们的优先级是什么；
-
在适当的时候拆分规则，否则，为每个规则准备一个变量，一行代码，甚至一个函数；
-
模拟题的禁忌在于在
main函数里深度耦合相关规则，考虑为它们单独使用函数； -
循环结构可用于以下情况：
- 顺序扫描
- 条件循环
- 回合制多轮模拟
-
主要流程的通用思维架构
初始化所有变量 while (没有结束) { // 1. 判断当前情况 if (情况A) { 执行操作A } else if (情况B) { 执行操作B } else { 执行默认操作 } // 2. 更新状态 更新变量 // 3. 判断是否结束 if (满足结束条件) break } 输出结果 -
只要没有出现复杂的遍历、枚举等导致时空复杂度爆炸的题目，尽管翻译题目就可以，不要尝试在考场上引入进阶算法等，把精力留到更需要的题目上；
-
除了需要预防越界访问导致 RE 的情况下，不要在判断语句中同时连接多个条件，这将降低可读性，且出错概率大幅提升。
-
直接上模板。根据我的观察，大部分题目可能会要求使用高精度实现加法和乘法，经过我的折腾和各路 AI 神仙的帮助，总结出这套易理解且好写的高精度。在题目未指明，且出现以下情况，无需多余思考，立即着手实现高精度：
- 斐波那契特性（具有斐波那契数列特征的数据）；
- 会对大量数据进行加和运算，尤其是连续乘法运算，且单个数据仅保证在 int 范围内；
- 将代码中的关键变量由 int 替换为 long long 后，OJ 的 WA 点报错信息发生改变；
- 涉及到 17 位及以上的数字。
C++ 实现高精度模板
#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef vector<int> bigint;
bigint read(string s) {
bigint a;
for (int i = s.size() - 1; i >= 0; i--) a.push_back(s[i] - '0');
return a;
}
void printf(bigint a) {
for (int i = a.size() - 1; i >= 0; i--) cout << a[i];
cout << endl;
}
bigint add(bigint a, bigint b) {
bigint c;
int carry = 0;
for (int i = 0; i < a.size() || i < b.size(); i++) {
int sum = carry;
if (i < a.size()) sum += a[i];
if (i < b.size()) sum += b[i]; // 一种更加优雅的逐位相加的实现方式，还能有效防止越界访问。
c.push_back(sum % 10);
carry = sum / 10;
}
if (carry) c.push_back(carry);
return c;
}
bigint mul(bigint a, bigint b) {
bigint c(a.size() + b.size(), 0); // 两个数相乘结果的位数一定不超过这两个数的位数的和。
for (int i = 0; i < a.size(); i++) for (int j = 0; j < b.size(); j++) c[i + j] += a[i] * b[j];
// 乘法不同于加法，需要全部乘完再逐个处理进位。（本质上还是在模拟人类竖式计算过程）
int carry = 0;
for (int i = 0; i < c.size(); i++) {
int sum = c[i] + carry;
c[i] = sum % 10, carry = sum / 10;
}
while (c.size() > 1 && c.back() == 0) c.pop_back(); // 去掉潜在的前导零。
return c;
}
// 调用示例
int main() {
string s1, s2;
cin >> s1 >> s2; // 先以字符串的形式读入
bigint a = read(s1);
bigint b = read(s2); // 调用存入函数
bigint c1 = add(a, b); // 调用加法
bigint c2 = mul(a, b); // 调用乘法
print(c1);
print(c2); // 调用打印
return 0;
}由于排序可以通过 algorithm 的 sort 实现，在这里阐述是极其不合时宜的。我在这里简要写一下手动实现快排的模板，重点放在 cmp 函数的编写上（因为我们有时需要自定义排序规则）。
快排的传统简易模板
void quick_sort(vector<int> a, int l, int r) { // 直接传入需要操作的容器
if (l >= r) return;
int i = l, j = r, pivot = a[(l + r) / 2];
while (i <= j) {
while (a[i] < pivot) i++; // 升序写法，写好的 cmp 函数也是放到这里进行判断
while (b[i] > pivot) j--;
if (i <= j) {
int tmp = a[i];
a[i] = a[j], a[j] = tmp, i++, j--;
}
}
quick_sort(a, l, j), quick_sort(a, i, r);
}我们将重心放在 cmp 函数上：
bool cmp(const T &a, const T &b) {
if (第一个关键字不相等) return 第一个关键字比较
if (第二个关键字不相等) return 第二个关键字比较
return 第三个关键字比较
}注意：T 是类型占位符，不要背模板背傻了；升序的比较是小于，降序的比较是大于；该 cmp 函数可以给 algorithm 的 sort 函数的第三参数使用。
lower_bound, upper_bound 记得待会写
这是最粗暴的解决方法，一些简易问题可使用该方法迅速枚举并得出期望的答案，但仅适用于以下情况：
- 数据量不大，且循环不超过三层；数据量较大，且循环不超过两层；
- 循环执行的是简易操作而非耗时操作。
如果必须使用循环枚举，考虑枚举一些简单的元素，而非直接对着答案疯狂枚举。
该情况过于简单，不多描述。
子集枚举仅在部分题目（如无明显贪心或动态规划策略）中可用，因为它的时间复杂度极高。
它的核心思路是将集合模拟成一个二进制数，用该位置上的 0 和 1 代表该位置选还是不选。我们上代码：
for (int mask = 0; mask < (1 << n); mask++) {
// 当前正在枚举子集 mask
cout << "{";
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
// 第 i 个元素已被选中
cout << a[i] << " ";
}
}
cout << "}";
}这里就是 algorithm 的主场了，我们引入函数 next_permutation(start, end)，这是 STL 的一个标准写法，它可以直接操作 [start, end) 区间内存产生下一个字典序列。使用时需注意以下事项：
- 数组传递指针（即直接把名字传给参数），
vector传递迭代器； - 该函数直接操作原内存区域，因此必须事先对其进行排序；
- 返回值类型是布尔值，当仍有可产生的新序列，返回
true，否则返回false； - 常和
do-while搭配； - 可选第三个参数，即放入
cmp函数。
注意：
do-while和while不能直接等价替换，do-while的逻辑正如字面，会先执行再判断，而while会先判断再执行。前者至少还能执行一次，后者可能完全不执行。
贪心，即“目光短浅”，始终保持当前决策在当前看来是最优的。在部分可用贪心解决的问题中，必须证明局部最优=整体最优。但通常正着证明很难，我们可以反过来考虑：是否有反例证明当目光短浅时，我们得不到最优答案？如果这个问题证明不出来，就知道贪心是可用的。贪心的使用还应满足当前的决策不会对未来决策产生影响，若先排序后决策，往往也是贪心的征兆。贪心使用起来应该具有线性函数那样顺畅的感觉，当尝试贪心时发现阻碍重重（比如怎样选择贪心？不断更换贪心方向？）这些征兆往往提示：在这里使用贪心是错误的。
贪心可能有这样几类（贪心的样式很多很多，极为玄学，我总结的是我遇到的典型的，不一定完全全面正确）
- 区间贪心：如最多选不重叠区间、最少覆盖区间，这种问题对右端点贪心；
- 排序贪心：如背包问题，往包里怎么装物品可使收益最大，这种问题对性价比进行贪心；
- 哈夫曼贪心：如怎样安排取水使得耗时最短，这种问题对最小的两个贪心（这里可能涉及到队列的知识点，但我并没有仔细研究。）
贪心最忌讳的就是陷入泥潭，导致意外调用大量耗时操作，比如反复移动指针，导致在某些情况下，指针没有按照预期移动；反复调用耗时操作，导致 TLE。写贪心时一定要细心仔细。
二分查找是小学生都能理解的东西，因为我小学翻字典就是这么翻的，所以我不想说了。
这里引入了两个比较重要的函数
lower_bound和upper_bound。前者返回第一个大于等于x的位置，后者返回第二个大于x的位置。用法示例如下：例如：
a = [0, 1, 2, 2, 2, 4, 5]
lower_bound(a, 2)指向第一个 2；upper_bound(a, 2)指向 4。常见用途有：
- 统计某个数出现的次数，如
count = upper_bound - lower_bound；- 判断是否存在；
- 寻找插入位置以保证容器内元素有序。
该函数返回类型为迭代器。
接下来是重头戏：二分查找
它的核心思想就是把求最值问题转化为判断某个答案 x 是否可行
识别该类型题目可依赖下述关键词：
- 最大值最小/最小值最大
- 尽量……同时满足……
- 在限制条件下求最优
该题目必须满足要求：具备单调性。单调性是指答案 x 在可能的范围内变化时，满足条件和不满足条件是具备单调性函数变化特征的。例如 x 越大越容易满足条件，而 x 越小越不能满足条件，这就说明答案具有单调性，可以考虑使用二分答案。
解题的关键步骤：
-
使用
l和r确定答案范围，越小越准确越好； -
写
check函数（后文写如何写到check函数，本质还是用贪心/模拟判断） -
二分答案，以下是控制流的二分标准模板
while (l < r) { mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid + 1; }
此模板是找最小可行解（
lower_bound型），如果找最大可行值，把l + r改成l + r + 1，if-else中l与r互换位置即可。奇技淫巧：当你发现循环卡死时，不妨把原来的
l + r改成l + r + 1。
check 函数的写法：
本质：在当前答案 x 下，检查构造出来的条件是否满足
常见套路：贪心、模拟、计数；
例如，以分割数组类型的题目作为例子：
bool check(int x) {
cnt = 1;
sum = 0;
for (int i = 0; i < n; i++) { // 强调一件事，考场千万不要过分紧张，导致这里变量不统一，或者分号变成逗号
if (sum + a[i] > x) cnt++, sum = a[i];
else sum += a[i];
}
return cnt <= k; // 看是否满足题目条件
}注意这里一定要弄清楚返回的布尔值代表什么，它影响着单调性判断。
搜索界两大恐怖巨头：DFS - 深度优先搜索；BFS - 广度优先搜索
DFS 常伴随着回溯法而出现，例如下列的伪代码：
function dfs(当前状态):
if (达到目标):
记录答案
return
for 每一种选择:
if (合法):
标记
dfs(新状态)
取消标记(回溯)
BFS 需要引入队列知识，所以不做展开。原因见最后一节。
吾听闻，原则上不考数据结构，好吧，我并没有准备。
如果没有原则了，我直接在考场上嚎啕大哭，我是窝囊派。