Misc
自动关联目录:Misc
不属于单一主题,但到处都在用的东西。
复杂度分析
三种记号
| 记号 | 含义 | 类比 |
|---|---|---|
| (大 O) | 上界,不超过 | |
| (大 Ω) | 下界,至少 | |
| (大 Θ) | 紧确界,同阶 |
口语里说的"复杂度"通常指(最坏情况上界)。
常见量级排序
直觉建立: 时
| 复杂度 | 操作次数 | 时间( 次/秒) |
|---|---|---|
| 20 | 瞬间 | |
| 0.01 s | ||
| 0.2 s | ||
| 2.8 小时 | ||
| 天文数字 | 宇宙毁灭 |
判题通常给 1 秒,对应约 次简单操作。先估量级再动手。
均摊复杂度(Amortized)
单次操作可能很贵,但一系列操作平均下来很便宜。
例子:动态数组 push_back
容量 1 → 2 → 4 → 8 → ...(每次满了翻倍)
扩容时要拷贝全部元素,单次 O(n)
但 n 次 push_back 总代价是 1+2+4+...+n = O(n)
→ 均摊 O(1)用摊还分析(聚合分析 / 记账法 / 势能法)证明。
其他例子:并查集的、单调栈的、splay 树的。
位运算
基础操作
n & (1 << i) // 第 i 位是否为 1
n | (1 << i) // 第 i 位置 1
n & ~(1 << i) // 第 i 位清 0
n ^ (1 << i) // 第 i 位取反
n & (n - 1) // 清除最低位的 1
n & -n // 只保留最低位的 1(lowbit)
n >> i & 1 // 取第 i 位内置函数(GCC)
__builtin_popcount(n) // 1 的个数
__builtin_clz(n) // 前导 0 的个数(leading zeros)
__builtin_ctz(n) // 末尾 0 的个数(= 最低位 1 的位置)
__builtin_parity(n) // 1 的个数奇偶性
// 64 位版本加 ll 后缀
__builtin_popcountll(n)常用技巧
// 1. 判断 2 的幂
bool isPow2(int x) { return x > 0 && (x & (x - 1)) == 0; }
// 2. 枚举所有子集
for (int sub = mask; sub; sub = (sub - 1) & mask) { /* ... */ }
// 3. 求最低位的 1 的位置
int pos = __builtin_ctz(x);
// 4. 交换两个数(不用临时变量,但实际不快)
a ^= b; b ^= a; a ^= b;
// 5. 绝对值(无分支)
int abs(int x) { int m = x >> 31; return (x ^ m) - m; }
// 6. 取最大值(无分支,避免分支预测失败)
int max(int a, int b) { return b & ((a - b) >> 31) | a & ~(a - b) >> 31; }枚举子集的所有子集
// 总复杂度 O(3^n)
for (int mask = 0; mask < (1 << n); mask++)
for (int sub = mask; sub; sub = (sub - 1) & mask)
/* ... */;状态压缩
用整数的每一位表示一个布尔状态:
// n 个物品是否选过 → n 位整数
int state = 0;
state |= (1 << i); // 选了第 i 个
if (state & (1 << i)) // 第 i 个被选了吗数论基础
最大公约数
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
// C++17: std::gcd(a, b)
int lcm(int a, int b) { return a / gcd(a, b) * b; } // 先除后乘,防溢出扩展欧几里得:求 的一组解。
int exgcd(int a, int b, int& x, int& y) {
if (!b) { x = 1; y = 0; return a; }
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}用途:求模逆元、解线性同余方程。
快速幂与模逆元
long long qpow(long long a, long long n, long long mod) {
long long r = 1 % mod;
a %= mod;
while (n) {
if (n & 1) r = (__int128)r * a % mod;
a = (__int128)a * a % mod;
n >>= 1;
}
return r;
}
// 费马小定理求逆元(mod 必须是质数)
long long inv(long long a, long long p) { return qpow(a, p - 2, p); }
// 扩展欧几里得求逆元(mod 与 a 互质即可,不要求质数)
long long inv2(long long a, long long m) {
long long x, y;
exgcd(a, m, x, y);
return (x % m + m) % m;
}组合数(模质数):
// 预处理阶乘和逆元阶乘
vector<long long> fact(N + 1), invf(N + 1);
fact[0] = 1;
for (int i = 1; i <= N; i++) fact[i] = fact[i-1] * i % MOD;
invf[N] = qpow(fact[N], MOD - 2);
for (int i = N; i >= 1; i--) invf[i-1] = invf[i] * i % MOD;
long long C(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n] * invf[k] % MOD * invf[n-k] % MOD;
}质数筛
// 埃氏筛 O(n log log n)
vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++)
if (isPrime[i])
for (int j = i * i; j <= n; j += i)
isPrime[j] = false;
// 欧拉筛(线性筛)O(n)
vector<int> primes;
vector<bool> vis(n + 1, false);
for (int i = 2; i <= n; i++) {
if (!vis[i]) primes.push_back(i);
for (int p : primes) {
if (i * p > n) break;
vis[i * p] = true;
if (i % p == 0) break; // 关键:保证每个数只被最小质因子筛一次
}
}质因数分解
vector<pair<int,int>> factorize(int n) {
vector<pair<int,int>> res;
for (int i = 2; (long long)i * i <= n; i++) {
if (n % i == 0) {
int cnt = 0;
while (n % i == 0) { n /= i; cnt++; }
res.push_back({i, cnt});
}
}
if (n > 1) res.push_back({n, 1}); // 剩下的是大于 sqrt 的质因子
return res;
}** Pollard Rho **:分解超大整数()的随机算法,试除法做不到时才用。
离散化
值域很大但元素个数少时,压缩到。
vector<int> xs = a;
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
// 映射:
int id = lower_bound(xs.begin(), xs.end(), x) - xs.begin(); // 0-based用途:坐标压缩后能用数组/树状数组/线段树。
注意:如果要用"区间"语义(如扫描线),可能要离散化到"相邻两点之间的区间"而不仅是点。
常用技巧清单
1. 双指针
有序数组、滑动窗口、回文判定、链表判环(快慢指针)。
2. 二分答案
把"求最优"转成"判定可行性"。(见二分章节)
3. 离线处理
把查询按某种顺序重排,用数据结构批量处理。
在线: 查询和修改交替,每次都要立即回答 → 需要动态数据结构
离线: 先把所有查询读进来,排序/分组后统一处理 → 可以用更简单的静态算法典型:莫队算法()、离线区间加(差分)。
4. 分块(平方分解)
把数组分成 块,整块用懒标记、零散部分暴力。
修改/查询 [l, r]:
- 零散的两端(< 2√n 个元素): 暴力 O(√n)
- 中间的整块(< √n 个块): O(√n)
总复杂度 O(√n)价值:比线段树好写好调,复杂度 够用时优先用它。
5. 随机化
- 随机化快排的 pivot(避免最坏情况)
- 随机化哈希种子(防卡)
- 模拟退火、遗传算法(求近似解)
6. 打表
小规模答案先暴力算出来找规律,或直接在代码里存表(如质数表、组合数表)。
输入输出
快速读写
ios::sync_with_stdio(false);
cin.tie(nullptr);这一行能让 cin/cout 接近 scanf/printf 的速度。默认 cin 与 stdio 同步,很慢。
更快( 级别数据):
// 快读
inline int read() {
int x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}常见坑
int溢出: 超int。累加、乘法、阶乘一律先想是否要long long- 中间结果溢出:
(a * b) % mod里a * b可能已经溢出。用__int128或先取模 sqrt的精度:sqrt(1e18)可能有误差。用i * i <= n而不是i <= sqrt(n)(但i*i也要防溢出,用i <= n / i)- 取模时的负数:
(x % MOD + MOD) % MOD - 数组开太小:
N + 5起步,边界多留 - 多组数据没清空:全局变量(尤其
vis、dist、邻接表) - 递归爆栈:深度 > 要改迭代
memset的值:memset(dp, 0x3f, ...)得到的是;0x7f得到。对long long不能用0x3f,要用0x3f3f3f3f3f3f3f3f或直接赋值- 浮点比较:
fabs(a - b) < 1e-9,不要a == b - 输出格式:
%.10lf、\nvsendl(endl会强制 flush,很慢)
许可协议:CC BY
作者:Davids
本文链接:https://hustjjd.github.io/df95b584.html
更新于:2026年11月16日