A - 基础算法 语言基础
语言基础
编译指令：
-std=c++11：c++11 标准。-O2：O2 优化。-Wl,--stack=1280000000：开栈。-Wall：显示所有警告。-Wextra：检测可疑代码并生成警告。-Wconversion：转型警告。
数值范围：
int范围：\(< 2^{31}\)。unsigned int范围：\(< 2^{32}\)。long long范围：\(< 2^{63}\)。unsigned long long范围：\(< 2^{64}\)。
自然溢出：
unsigned int自然溢出：对 \(2^{32}\) 取模。unsigned long long自然溢出：对 \(2^{64}\) 取模。
输出格式：
unsigned int输出格式：%u。unsigned long long输出格式：%llu。
C++ STL
lower_bound & upper_bound
lower_bound(s, t, val)：指向 \([s, t)\) 中第一个 \(\geq \mathrm{val}\) 的元素的迭代器，需要保证 \([s, t)\) 升序排序。upper_bound(s, t, val)：指向 \([s, t)\) 中第一个 \(> \mathrm{val}\) 的元素的迭代器，需要保证 \([s, t)\) 升序排序。
sort
升序排序（默认）：sort(s, t)。
降序排序：sort(s, t, greater<int>())。
vector
- vector 编号从 \(0\) 开始。
vector<int> num(n)：指定该容器大小为 \(n\)。vector<int> num(n, m)：指定该容器大小为 \(n\)，初始值均为 \(m\)。
区间计数： upper_bound(V.begin(), V.end(), r) - lower_bound(V.begin(), V.end(), l)。
priority_queue
大根堆（默认）：priority_queue<int> q。
小根堆：priority_queue< int, vector<int>, greater<int> > q。
multiset
升序排序（默认）：multiset<int> s。
降序排序：multiset< int, greater<int> > s。
s.erase(val)：将所有数值为 \(\mathrm{val}\) 的元素删除，返回被删除的元素个数。s.erase(pos)：将迭代器 \(\mathrm{pos}\) 指向的元素删除。- 在 multiset 中删除一个数值为 \(\mathrm{val}\) 的元素，应执行
s.erase(s.find(val))。 - 使用 multiset 维护多关键字的数据，在重载小于号时，应保证两个不同的元素能被有效区分。
bitset
- bitset 编号从 \(0\) 开始。
- bitset 可以进行各种二进制操作，如取反
~、与&、或|、异或^、左移<<、右移>>。 b.count()：返回 \(1\) 的个数。b.any()：查询 bitset 中是否存在 \(1\)。b.none()：查询 bitset 中是否全 \(0\)。b.set()：将所有位改为 \(0\)。b.reset()：将所有位改为 \(1\)。b._Find_first()：查询低位到高位第一个 \(1\) 的位置。b._Find_next()：查询当前位置之后下一个 \(1\) 的位置。
A - 基础算法 算法基础
I/O 优化
读入优化：
template <class &T>
inline void read(T &x) {
static char s;
static bool opt;
while (s = getchar(), (s < '0' || s > '9') && s != '-');
x = (opt = s == '-') ? 0 : s - '0';
while (s = getchar(), s >= '0' && s <= '9') x = x * 10 + s - '0';
if (opt) x = ~x + 1;
}
快速乘
\(\mathcal{O}(\log n)\) 快速乘：
特别要注意的是，模数大小的两倍不能超过 long long 上界。
typedef long long s64;
s64 qmul(s64 a, s64 b, s64 p) {
s64 ans = 0;
for (; b; b >>= 1) {
if (b & 1) ans = (ans + a) % p;
a = 2 * a % p;
}
return ans;
}
\(\mathcal{O}(1)\) 快速乘：
注意到：
\[a \times b \bmod p = a \times b - \left\lfloor \frac{a \times b}{p} \right\rfloor \times p \]利用 long double 来处理 \(\left\lfloor \frac{a \times b}{p} \right\rfloor\)。
虽然 \(a \times b\) 和 \(\left\lfloor \frac{a \times b}{p} \right\rfloor \times p\) 的数值可能很大，但是两者的差一定在 \([0, p)\) 之间，我们只关心它们的前 64 位即可，这正好可以用 long long 运算的自然溢出来处理。
typedef long long s64;
s64 qmul(s64 a, s64 b, s64 p) {
s64 c = (long double)a * b / p + 1e-8;
s64 ans = a * b - c * p;
if (ans < 0) ans += p;
if (ans >= p) ans -= p;
return ans;
}
快速幂
int qpow(int a, int b, int p) {
int ans = 1;
for (; b; b >>= 1) {
if (b & 1) ans = 1ll * ans * a % p;
a = 1ll * a * a % p;
}
return ans;
}
二分
>> 1向下取整，/2向零取整。- 在整数域上进行二分时：
- 若分成的区间为 \([l, \mathrm{mid}], [\mathrm{mid} + 1, r]\)，
mid = (l + r) >> 1。 - 若分成的区间为 \([l, \mathrm{mid} - 1], [\mathrm{mid}, r]\)，
mid = (l + r + 1) >> 1。
- 若分成的区间为 \([l, \mathrm{mid}], [\mathrm{mid} + 1, r]\)，
- 在实数域上进行二分时，
mid = (l + r) / 2。
二叉树
\(n_0\) 与 \(n_2\) 的关系：\(n_0 = n_2 + 1\)。
证明：
- 一方面
- 另一方面