Misc

自动关联目录:Misc

不属于单一主题,但到处都在用的东西。

复杂度分析

三种记号

记号含义类比
OO(大 O)上界,不超过≤\le
Ω\Omega(大 Ω)下界,至少≥\ge
Θ\Theta(大 Θ)紧确界,同阶==

口语里说的"复杂度"通常指OO(最坏情况上界)。

常见量级排序

O(1)<O(log⁡n)<O(n)<O(nlog⁡n)<O(n2)<O(n3)<O(2n)<O(n!)O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)

直觉建立:n=106n = 10^6 时

复杂度操作次数时间(10810^8 次/秒)
O(log⁡n)O(\log n)20瞬间
O(n)O(n)10610^60.01 s
O(nlog⁡n)O(n \log n)2×1072 \times 10^70.2 s
O(n2)O(n^2)101210^{12}2.8 小时
O(2n)O(2^n)天文数字宇宙毁灭

判题通常给 1 秒,对应约10810^8 次简单操作。先估量级再动手。

均摊复杂度(Amortized)

单次操作可能很贵,但一系列操作平均下来很便宜。

例子:动态数组 push_back

容量 1 → 2 → 4 → 8 → ...(每次满了翻倍)
扩容时要拷贝全部元素,单次 O(n)
但 n 次 push_back 总代价是 1+2+4+...+n = O(n)
→ 均摊 O(1)

用摊还分析(聚合分析 / 记账法 / 势能法)证明。

其他例子:并查集的O(α(n))O(\alpha(n))、单调栈的O(n)O(n)、splay 树的O(log⁡n)O(\log n)。

位运算

基础操作

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; }   // 先除后乘,防溢出

扩展欧几里得:求ax+by=gcd⁡(a,b)ax + by = \gcd(a,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;
}

组合数(模质数):

(nk)=n!k!(n−k)!(modp)\binom{n}{k} = \frac{n!}{k!(n-k)!} \pmod p

// 预处理阶乘和逆元阶乘
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 **:分解超大整数(101810^{18})的随机算法,试除法做不到时才用。

离散化

值域很大但元素个数少时,压缩到[0,n)[0, n)。

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. 离线处理

把查询按某种顺序重排,用数据结构批量处理。

在线: 查询和修改交替,每次都要立即回答 → 需要动态数据结构
离线: 先把所有查询读进来,排序/分组后统一处理 → 可以用更简单的静态算法

典型:莫队算法(O((n+m)n)O((n+m)\sqrt{n}))、离线区间加(差分)。

4. 分块(平方分解)

把数组分成n\sqrt{n} 块,整块用懒标记、零散部分暴力。

修改/查询 [l, r]:
  - 零散的两端(< 2√n 个元素): 暴力 O(√n)
  - 中间的整块(< √n 个块):   O(√n)
总复杂度 O(√n)

价值:比线段树好写好调,复杂度O(n)O(\sqrt n) 够用时优先用它。

5. 随机化

  • 随机化快排的 pivot(避免最坏情况)
  • 随机化哈希种子(防卡)
  • 模拟退火、遗传算法(求近似解)

6. 打表

小规模答案先暴力算出来找规律,或直接在代码里存表(如质数表、组合数表)。

输入输出

快速读写

ios::sync_with_stdio(false);
cin.tie(nullptr);

这一行能让 cin/cout 接近 scanf/printf 的速度。默认 cin 与 stdio 同步,很慢。

更快(10610^6 级别数据):

// 快读
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 溢出:109×10910^9 \times 10^9 超 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、邻接表)
  • 递归爆栈:深度 >10510^5 要改迭代
  • memset 的值:memset(dp, 0x3f, ...) 得到的是0x3f3f3f3f≈1.06×1090x3f3f3f3f \approx 1.06 \times 10^9;0x7f 得到2.1×1092.1 \times 10^9。对 long long 不能用 0x3f,要用 0x3f3f3f3f3f3f3f3f 或直接赋值
  • 浮点比较:fabs(a - b) < 1e-9,不要 a == b
  • 输出格式:%.10lf、\n vs endl(endl 会强制 flush,很慢)