奇技淫巧

· · 算法·理论

导论

任何奇技淫巧以能在比赛时使用为标准。

任何颠覆了传统且对比赛有帮助的东西统称奇技淫巧。奇技淫巧抑或是能减少码量，抑或是能优化时空，抑或是能乱搞，抑或只是为了装逼。目前主要分为如下几个类别：

更广义的奇技淫巧包括但不限于：

这些限于篇幅，且不完全符合对奇技淫巧的定义，不做讲解。

语法类

参考这篇专栏以及网上各路博客。

请注意，任何自带的函数常数都不如手写的，特殊标明除外。

C++98

库函数

GNU 私货

不在 C++ 标准中，是 GNU 的私货，比赛时可以使用。

numeric 库

有人说它很好用，个人觉得一般。

functional 库

常用的：less<>/greater<>。简单排序再也不用写 cmp 了。

实际上还有类似的：

剩下的个人感觉不常用了，可以自己打开头文件看。

cmath 库

此外，cmath 库中定义了很多常量，使用方法：

  1. 代码开头在引用头文件前必须写一句 #define _USE_MATH_DEFINES，不写是用不了的，也可以写头文件里剩下的那几个；
  2. 然后就可以使用里面的各种常量了。下面直接放头文件，注意有第二个下划线的是除以的意思，如 M_PI_2 就是 \pi/2，M_1_PI 就是 1/\pi。比较常用的就是一个 \pi 和一个 \mathrm e。
#if !defined(__STRICT_ANSI__) || defined(_XOPEN_SOURCE) || defined(_GNU_SOURCE) || defined(_BSD_SOURCE) || defined(_USE_MATH_DEFINES)
#define M_E     2.7182818284590452354
#define M_LOG2E     1.4426950408889634074
#define M_LOG10E    0.43429448190325182765
#define M_LN2       0.69314718055994530942
#define M_LN10      2.30258509299404568402
#define M_PI        3.14159265358979323846
#define M_PI_2      1.57079632679489661923
#define M_PI_4      0.78539816339744830962
#define M_1_PI      0.31830988618379067154
#define M_2_PI      0.63661977236758134308
#define M_2_SQRTPI  1.12837916709551257390
#define M_SQRT2     1.41421356237309504880
#define M_SQRT1_2   0.70710678118654752440
#endif

__builtin 家族

全都是 GNU 私货，复杂度 \boldsymbol{O(\log\log n)} 且常数很小，一定比手写快。

如果 \boldsymbol x 的类型是 long long，请务必使用 __builtin_xxxll(x)。

C++11

从 C++98 到 C++11 是一次重大的飞跃，许许多多非常实用的函数与语法如雨后春笋般出现。

新语法

nullptr

以后所有的 NULL 都写成 nullptr。

因为 NULL 实际上被实现成了含糊不清的 #define NULL 0，nullptr 彻底做出了区分。

using 替代 typedef

// Before
typedef long long ll;
typedef pair<int, int> pii; // CE，模板不是类型

// Now
using pii = pair<int, int>; // 编译成功，与 typedef 有一样的效果

constexpr 关键字

与 const 的区别：const 意义为 “只读”，constexpr 意义为 “常量”。

被 constexpr 修饰的变量/函数在编译时就被计算，效率更高。所以请尽量使用 constexpr。剩余更高深的应用自行 BDFS。

auto 关键字

Lambda 表达式

基于范围的 for 循环

// Before
for (int i = 0; i < g[u].size(); ++i) ... // 好麻烦，常数大（不断调用 size 函数）
for (vector<int>::iterator it = g[u].begin(); it != g[u].end(); ++it) ... // 常数小，但更麻烦

// Now
for (auto v : g[u]) // 舒服

emplace

许多 STL 的容器中出现的新函数：

几乎所有的 “插入、添加” 型成员函数都有 emplace 的版本。emplace 通过调用构造函数来插入，相较于原来的拷贝方式效率更优。所以它的用法也有不一样：

vector<pair<int, int>> v; // 以前两个>中间要加个空格，现在也不需要了
// Before
v.push_back(make_pair(a, b));
v.push_back({a, b});
// Now
v.emplace_back(a, b);

只要有构造函数，类似的写法同样可应用于结构体。

advance 函数

语法：advance(it, num)，其中 \mathit{it} 是一个迭代器，\mathit{num} 是一个整数。

作用是将迭代器 \mathit{it} 前进 \mathit{num} 位。时间复杂度是线性的。

它有什么用，相信不需要我再多说。

shrink_to_fit

decltype 关键字

用于推导返回值类型并将其作为新变量的类型，如：

int a = 1953615, b = 198964;
decltype(a + b) c; // 此时 c 是 int 类型

除非你真的不知道应该给新变量什么类型，否则可能没用。

库函数

algorithm 库

numeric 库

iterator 库

functional 库

一句话作用：把一个函数当作一个变量存起来，可保存为单个变量或数组，可正常遍历。

个人认为功能不强，语法请自行 BDFS。

random 库

详见随机化部分。

cmath 库

剩下的还有 STL 中的 tuple、构造函数等，它们要么是作用不大，要么是早已融入我们的代码中，在此不提。

这里所说的 “构造函数” 指的是更高级的构造函数，普通的构造函数相信大家都会，更高级的咱也用不着。

C++14

字符串带转义字符

以前的字符串中出现转义字符都需要反斜杠 \ 来修饰。

现在：char * str = R"(abc\db'\t")";。这样声明的字符串 \mathit{str}=\texttt{abc\\db'\\t"}。

语法就是 R"(...)"，括号内随便写什么都不会被转义。

整型字面量分隔符

  1. 在整型前面输入 0b 代表是二进制，与八进制的 0、十六进制的 0x 类似。例：int a = 0b1101101001。
  2. 在整型中插入 ' 作为分隔符，作用是方便阅读而不影响编译。例：
int wdz = 0b1'000'001'000;
int xx = 0x2'0'9; // 都是可以正常编译的

比较鸡肋是吧，因为有用的前面或多或少都提了。

STL 类

STL 是 C++ 独有的最庞大的奇技淫巧。

STL

vector

设 v 是一个 vector。

容量相关（2024/10/6 upd.）

vector 真正占空间的是容量，请务必在毒瘤题中注意 vector 的容量问题，及时释放不必要的容量。

综上所述，在这道题中，我们需要把当前 vector 的容量清空，我们该怎么做呢？设当前 vector 为 x。

  1. vector<int>().swap(x)，意思是构造一个空 vector，将它和 x 交换。因为 swap() 可以同时交换大小和容量，且这个构造的 vector 会在使用后就被销毁，所以我们便达到了目的。
  2. x.clear(), x.shrink_to_fit() 意思是先清空大小，再将容量调整至和大小相同。这样我们也达到了目的。

错误示范：

  1. x.resize(0)：由于 resize() 只改大小不改容量，所以这样写和 x.clear() 没有区别。
  2. x.reserve(0)：由于 reserve() 只能增加容量，所以这样写等于没写。

deque / list

deque 也是支持常数级别随机访问的，但增删元素为线性。list 支持常数增删元素，但随机访问为线性。函数与 vector 差不多，但又有差异。

set / multiset / unordered_set / unordered_multiset

求交集/并集/差集/对称差集（2024/10/16 upd.）

用法：前四个参数都是两个集合首尾的迭代器，最后一个参数为 inserter(c,c.begin()) 的形式，其中 c 是输出结果的 set。

注意，这些函数只能用于 STL，且使用前提是 STL 容器有序，所以它可以用于有序的 vector，但不能用于 unordered_set。

map / unordered_map

struct cc {
    bool operator () (const int &a, const int &b) const {
        return a > b;
    }
};
set<int, cc> st;
map<int, int, cc> mp;

先要说一下 unordered 系列容器的被卡问题，因为它们底层都是基于哈希表实现的，而 STL 自带的哈希函数很史（优点是效率高），所以只需要频繁插入一个特定素数的倍数就能制造哈希冲突，把哈希表卡到 O(N)。这个素数在 GCC 6 以前的编译器上是 126271，在以后的编译器上是 107897。
想要解决这个问题就是自己写哈希函数。可以利用与时间有关的库函数生成当前时间，然后把该值加入到哈希函数中，可以 100% 防止被卡。

struct hh {
    int operator () (const int &x) const {
        // 你的哈希函数 
    }
};
unordered_set<int, hh> st;
unordered_map<int, int, hh> mp;

有某些更好的哈希函数，比如：

const auto RAND = chrono::high_resolution_clock::now().time_since_epoch().count();
struct hh {
    int operator () (const int &x) const {
        return x ^ RAND;
    }
};

这是防止某些处心积虑的人卡 unordered_map 的，如果是 long long 类型，就写成 return (x >> 32) ^ x ^ RAND;。但是，它无法使 pb_ds 中的哈希表走出困境。

更强的哈希函数（Codeforces 大佬推荐）：

const auto RAND = chrono::steady_clock::now().time_since_epoch().count();
struct hh {
    static int splitmix64(int x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    int operator () (const int &x) const {
        return splitmix64(x + RAND);
    }
};

实测 gp_hash_table 加这个哈希函数跑到飞起。

2024/11/28 upd.

写这句话的人完全是在胡扯。实际上在不卡哈希的情况下，手写哈希函数的效率会慢 1.2 倍左右。除非你是在 CF 这种毒瘤云集的地方做题，否则不建议手写哈希函数，甚至不建议用 pb_ds，一是没有必要，二是可能有副作用。STL 中的东西能应付八成以上的情况，且 pb_ds 从来都不是一道题的必须。如果你非用 pb_ds 不可，只能说明你在乱搞。（逃

如果给 pair 写哈希函数，只需给 first 和 second 都按你的哈希函数哈希一下，把后者的哈希值右移一位（看网上博客说的，不知道有什么意义），最后返回二者异或的值。

stack / queue / priority_queue

bitset

bitset 严格来说不属于 STL，但它是包含在 #include <bits/stdc++.h> 中的。

首先要注意的是，随机的、跳跃的访问会拖慢 bitset 的效率，使之不如 bool 数组。所以图论里常见的 \mathit{vis} 数组最好还是写成 bool 数组的形式。

其余情况下，bitset 理论能把复杂度优化到 O(\frac nw)，其中 w 是计算机位数，一般是 32 或 64。关于 bitset 的详细用法请自行 BDFS。

exSTL 之 pb_ds

大杀器。引用头文件如下：

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp> // 用哈希表
#include <ext/pb_ds/tree_policy.hpp> // 用平衡树
#include <ext/pb_ds/priority_queue.hpp> // 用堆
using namespace __gnu_pbds;

cc_hash_table / gp_hash_table

pb_ds 中的哈希表，实测后者比前者快。一般用于代码卡常，以笔者当前经验来看，拿 gp_hash_table 代替 unordered_map 准不会慢，前提是手写哈希函数。

语法与 unordered_map 无异。

裸的 pb_ds 哈希表也是能被卡的（频繁插入 2^{16} 的倍数），具体防卡方法上文有述。

tree

平衡树，pb_ds 最为强悍之处。这篇博客讲了其中一部分，下面再补充一些。

语法和 set 无异，可以实现 set / map 所有功能外加

可以看出，pb_ds 中的平衡树几乎可以解决所有按键值分裂的平衡树题目。

priority_queue

与 STL 中的 priority_queue 类似，但目前还没有发现它有什么更好的地方，先咕着。

pb_ds 里面有用的也就这么多了。

exSTL 之 rope

二杀器。不过目前还没有使用它的实例，先咕着。

随机化类

既是造数据的帮手，又是骗分的利器。

时间函数

一般用于初始化随机种子，也用于对拍求程序运行时间、卡时、手写哈希函数等。

clock 函数

用法：clock()，返回当前程序运行的毫秒数（Windows 下）。注意，不同系统得到的返回值单位不同，因此统一成秒的方法是：(double)clock() / CLOCKS_PER_SEC。大家都会用，不赘述了。

一般用于卡时、对拍。

time 函数

用法 time(0)，返回从 1970 年 1 月 1 日到现在的秒数，一般用于初始化随机种子。但因为是秒级别的，所以一秒内生成的随机数相同，会影响效率。

chrono 类

chrono 是 C++11 新增的一个时间类，功能强大，不过我目前只用它的两个函数：

网上很多文章都说后者是精度最高的时钟，但实际上精度都能到纳秒，根本不用追求二者的精度差异。何况这玩意还是看实现的，在我的电脑上，high_resolution_clock 直接被定义成了 system_clock 的别名。更多时候还是建议使用前者，因为前者产生 10^{14} 级别，而后者产生 10^{19} 级别，前者不太会产生溢出问题。具体还是看用途来决定使用哪个。

timeb 类

另一种初始化毫秒级别随机种子的方法，注意在 Linux 下不能使用。

struct _timeb T;
_ftime(&T);
mt19937 wdz(T.millitm);

随机化函数

大家都会使用 rand()，但是 Windows 下 rand() 的值域只有 32767。如果使用 rand() * rand() 的手法生成更大的随机数，这样生成的随机数极不均匀。且众所周知的种种原因，rand() 不再推荐使用。

mt19937

推荐使用的是 mt19937，它的优点无需更多赘述。直接定义 mt19937 能生成 unsigned int 范围内的随机数，定义 mt19937_64 能生成 unsigned long long 类型的随机数。例：

mt19937 wdz;
cout << wdz() << '\n';

然而，你会发现这样每次输出的随机数是相同的，因此需要初始化随机种子。初始化方法：mt19937 wdz(1953615)，这样就将 1953615 作为随机化种子。和上面的时间函数结合，就是毫秒级别的随机数种子。

uniform_int_distribution

众所周知，用 wdz() % 1000000000 这样的方法生成的随机数是不均匀的，会偏小。这个函数可以生成真正均匀的随机数。

用法：uniform_int_distribution<>(1, 1e9)(wdz)，可以生成均匀分布于 [1,10^9] 的随机整数。其中尖括号里不填表示 int 类型，需要 long long 就填成 long long 即可。中间的就填范围，后面的 wdz 是一个 mt19937。

经过实测，这个函数的常数比较大，如果用在代码里，请注意它的效率。

uniform_real_distribution

用法类似，给定的两个边界用于生成 [a,b) 的随机数，尖括号里填浮点数类型。一般用于模拟退火。

以 uniform 开头的其他函数可以生成非均匀分布的随机数，如正态分布等，用途不大。

随机化算法

用于求解最优解问题的大杀器，也是求解部分期望题的最有效骗分手段。针对很逊的出题人，这种方法可以骗取极高的分数。随机化算法的准确性依赖数据范围，针对规模小的数据准确率很高。如果是用于求解期望题，则需要最终输出的答案不超过两位小数，准确率就非常高了。

首先是最常见的随机化 + 卡时，这种无需多言，按照题意模拟，最后取最优解即可。

然后是高级一些的模拟退火，参见洛谷上的一篇专栏。

卡常类

收录一些也不知有没有用的卡常小寄巧。其中大多数应该都可以靠 O2 优化，按个人喜好。不按照效果排序。

位运算类

直接看这里。