返回「邏輯與算法」主頁

本页面收录难以归类的知识点。对于公式和定理，另见 邏輯與算法：柿子 。

带权中位数

带权中位数 ：给定数组 W,XW, X，保证 Wi≥0W_i \ge 0。求 argmin⁡k∑i=1NWi∣k−Xi∣\displaystyle \operatorname*{argmin}_{k} \sum_{i=1}^{N} W_i \lvert k - X_i \rvert。

先考虑不带权的，那么带权就是 XiX_i 出现了 WiW_i 次。按 XiX_i 升序排序，顺序累加 WiW_{i}，找到第一个使得 WiW_{i} 的前缀和 ≥12∑i=1NWi\displaystyle \ge \dfrac{1}{2}\sum \limits_{i=1}^{N} W_i 的位置 mm，则最优解为 k∗=Xmk^* = X_m。

例 1：NN 个人围成一圈，第 ii 个人初始有 AiA_i 个物品。ii 与 (i+1) mod N(i+1) \bmod N 每传递 11 个物品的代价为 BiB_i。欲通过若干次传递使每个人手中的物品数量相同，求最小总代价。
设 di=Ai−Aˉd_i = A_i - \bar{A}。设 ii 传递给 (i+1) mod N(i+1) \bmod N 了 cic_i 个（可能为负）。根据物品守恒，ci=cN+Dic_i = c_N + D_i。则总传递代价 Ans(cN)=∑i=1NBi∣ci∣=∑i=1NBi∣cN+Di∣\displaystyle \text{Ans}(c_N) = \sum_{i=1}^N B_i \lvert c_i\rvert = \sum_{i=1}^N B_i \lvert c_N + D_i\rvert。欲构造 cNc_N 以最小化 Ans(cN)\text{Ans}(c_N)，这就是带权中位数问题。

例 2：序列 A,BA, B，设有理数序列 c,dc, d 满足 (Ai+ci)(Bj+dj)=(Aj+cj)(Bi+di)(A_i+c_i)(B_j+d_j)=(A_j+c_j)(B_i+d_i)，最小化 ∑∣ci∣+∣di∣\sum |c_i|+|d_i|。(ABC479G)
要么 ci≡0c_{i} \equiv 0，要么 di≡0d_{i} \equiv 0。以 ci≡0c_{i} \equiv 0 为例，设 Bi+di=kAiB_i+d_i = k A_{i}，需最小化 ∑∣di∣=∑∣kAi−Bi∣=∑∣Ai∣∣k−BiAi∣\sum |d_{i}| = \sum |k A_{i} - B_{i}| = \sum |A_{i}| \biggl|k - \dfrac{B_{i}}{A_{i}}\biggr|，这就是带权中位数问题。注意特判非零的 AA 为空。
将 (Ai,Bi)(A_{i}, B_{i}) 看作二维坐标系的点，将每个点移动到同一条过原点的直线，代价是 ∣ci∣+∣di∣|c_i|+|d_i|。当 ∣k∣⩽1|k| \leqslant 1 时，点纵向移动不劣，∣k∣>1|k| > 1 时，横向不劣。

排名离散化

离散化 (Discretization)：把连续的大范围的东西转换成离散的小范围排名

1
2
3
4
auto g = a;
rgs::sort(g);
g.erase(rgs::unique(g).begin(), g.end());
for (auto& x : a) x = rgs::lower_bound(g, x) - g.begin();

例 1 (全平面的极角离散化)

例 2 (ABC481F)：NN 点 MM 边有向图，边权 Wi∈[1,9]W_i \in [1, 9]。求从 11 到每个点 vv 的所有路径中，边权序列所表示的大整数最小的路径。

先最小化路径长度，路径长度相同时，大整数比较即字典序比较。实现时用 BFS 分层，同一层的节点一起转移，先 f(v)←10f(u)+cf(v) \gets 10 f(u) + c，再收集所有 f(v)f(v) 并离散化。复杂度 O(Mlog⁡N)\mathcal{O}(M \log N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
dep[0] = 0;
layer[0].push_back(0);
for (int d = 0; d < N; d++) {  // 层 
	// 离散化 
	vector<int> g;
	for (auto y : layer[d]) g.push_back(dis[y]);
	ranges::sort(g);
	g.erase(ranges::unique(g).begin(), g.end());
	for (auto y : layer[d]) dis[y] = ranges::lower_bound(g, dis[y]) - g.begin();
	// 转移 
	for (auto x : layer[d]) {
		for (auto [y, c] : adj[x]) {
			if (dep[y] == -1) {
				dep[y] = dep[x] + 1;
				layer[dep[y]].push_back(y);
			}
			if (dep[y] != dep[x] + 1) {
				continue;
			}
			if (dis[y] > 10 * dis[x] + c) {
				dis[y] = 10 * dis[x] + c;
				ans[y] = 10 * ans[x] + c;
			}
		}
	}
}

例 3 (2024 TOPC L)：NN 点 MM 边有向图，边权 WiW_i。求从 SS 到 TT 恰好经过 KK 条边的所有路径中，边权序列字典序最小的路径，输出 hash 值 ∑i=1KWeiXK−i\sum_{i=1}^K W_{e_i} X^{K-i}。

倍增预处理，设 fk,u,vf_{k, u, v}：从 uu 到 vv，长度为 2k2^{k}，字典序最小的路径序列。拼凑得到 KK。

考虑 merge。传统做法是 fa+b,u,v=min⁡w(fa,u,w+fb,w,v)f_{a+b, u, v} = \min_{w} (f_{a, u, w} + f_{b, w, v})，但不可直接维护序列，因而分别维护字典序和 hash 值。为比较字典序，同一批转移时先 ra+b,u,v←ra,u,wN2+rb,w,vr_{a + b, u, v} \gets r_{a, u, w} N^{2} + r_{b, w, v}，再离散化，其中 +∞+\infty 表示不可达。对于 hash 值，ha+b,u,v=ha,u,w∗Xb+hb,w∗,vh_{a + b, u, v} = h_{a, u, w^{*}} X^{b} + h_{b, w^{*}, v}。复杂度 O(N3log⁡K)\mathcal{O}(N^3 \log K)。

排序不等式

排序不等式 ：只改变配对方式，

  • ∑AiBπ(i)\sum A_{i} B_{\pi(i)}：同序最大，逆序最小
  • ∑∣Ai−Bπ(i)∣\sum |A_{i} - B_{\pi(i)}|：同序最小，逆序最大
  • ∑(Ai−Bπ(i))2\sum (A_{i} - B_{\pi(i)})^{2}：同序最小，逆序最大

例 ：序列 A,BA, B，其中 ∣A∣⩽∣B∣|A| \leqslant |B|，选取 BB 的任一 ∣A∣|A| 元子列的任一排列 bb，最大化 ∑∣Ai−bi∣\sum |A_{i}-b_{i}|。(CF1921D)

不妨设 AA 递增。由排序不等式，bb 递减，将 BB 倒序排序，再选取一个递减子列 bb。而且 bb 是 BB 的某前缀与某后缀拼接起来的。枚举分界点计算答案。O(Nlog⁡N)\mathcal{O}(N\log N)。

区间包含树

区间包含树 ：给定若干区间 [Li,Ri)[L_i,R_i)，要么互不相交（Ri≤LjR_i \le L_j），要么一个包含另一个（Li≤Lj<Rj≤RiL_i \le L_j < R_j \le R_i），不存在交叉重叠（Li<Lj<Ri<RjL_{i} < L_{j} < R_{i} < R_{j}），构造区间包含树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 区间 -> 树 (0 是虚拟根)
vector<vector<int>> build(const vector<pair<int, int>>& seg) {
    const int N = int(seg.size());
    struct Seg {
        int l, r, id;
    };
    vector<Seg> A(N + 1);
    constexpr int inf = 0x3f3f3f3f;
    A[0] = {-inf, inf, 0}; // 虚拟根 
    for (int i = 0; i < N; i++) {
        auto [l, r] = seg[i];
        A[i + 1] = {l, r, i + 1};
    }
    ranges::sort(A, {}, [](const Seg& x) { return pair(x.l, -x.r); });
    vector<int> s;
    vector<vector<int>> adj(N + 1);
    for (int i = 0; i <= N; i++) {
        while (!s.empty() && A[s.back()].r <= A[i].l) {
            s.pop_back();
        }
        if (!s.empty()) {
            adj[A[s.back()].id].push_back(A[i].id);
        }    
        s.push_back(i);
    }
    return adj;
}

ＲＳＡ算法

Key Generation

  • Two distinct large prime numbers pp and qq
  • Modulus n=p×qn = p \times q
  • Public Exponent ee : 1<e<ϕ(n)1 < e < \phi(n) and e⊥ϕ(n)e \perp \phi(n)
  • Private Exponent dd : d×e≡1(modϕ(n))d \times e \equiv 1 \pmod{\phi(n)}

Result

  • Public Key: (e,n)(e, n) - distributed to everyone
  • Private Key: (d,n)(d, n) - kept secret

Encryption (Confidentiality)

  • Suppose Alice wants to send an integer mm (where 0≤m<n0 \le m < n) to Bob
  • Encryption: Alice computes c≡me(modn)c \equiv m^e \pmod n using Bob’s public key (e,n)(e, n)
  • Transmission: Bob receives the ciphertext cc
  • Decryption: Bob computes m≡cd(modn)m \equiv c^{d} \pmod n using his private key (d,n)(d, n)
  • Obviously, m≡cd≡med≡mkϕ(n)+1≡m(modn)m \equiv c^{d} \equiv m^{e d} \equiv m^{k \phi(n) + 1} \equiv m \pmod n for some integer kk

树点边容斥

树点边容斥 ：设树 T=(V,E)T=(V,E)，设计数对象 SS 对应一个非空顶点集合 A(S)⊂VA(S)\subset V，且 T[A(S)]T[A(S)] 连通，那么 ∣S∣=∑v∈V#{S:v∈A(S)}−∑e=uv∈E#{S:u,v∈A(S)}|\mathcal S|=\sum_{v\in V}\#\{S:v\in A(S)\}-\sum_{e=uv\in E}\#\{S:u,v\in A(S)\}。也就是 #{\#\{ 对象 }=∑v#{\}=\sum_v\#\{ 经过 vv 的对象 }−∑e#{\}-\sum_e\#\{ 经过 ee 的对象 }\}。

引理：树有 ∣V∣−∣E∣=1|V|-|E|=1。
理解：设 T[A(S)]=(V(S),E(S))T[A(S)]=(V(S), E(S))，这是一棵树，从而有 1=∣V(S)∣−∣E(S)∣1=|V(S)|-|E(S)|。把两项分别写成指示函数，1=∑v∈V[v∈A(S)]−∑e=uv∈E[u,v∈A(S)]1=\sum_{v\in V}[v\in A(S)]-\sum_{e=uv\in E}[u,v\in A(S)]，对所有对象 S∈SS\in\mathcal S 求和，∣S∣=∑S∈S∑v∈V[v∈A(S)]−∑S∈S∑e=uv∈E[u,v∈A(S)]|\mathcal S|=\sum_{S\in\mathcal S}\sum_{v\in V}[v\in A(S)]-\sum_{S\in\mathcal S}\sum_{e=uv\in E}[u,v\in A(S)]，交换求和次序后即得结论。

推论 ：设若干区间 Ii=[li,ri]I_i=[l_i,r_i] 满足 li<li+1l_i<l_{i+1}，ri<ri+1r_i<r_{i+1}，求区间 J=[L,R]J = [L, R] 的数量，满足 JJ 至少包含一个 IiI_i。设 SiS_i 表示区间 [L,R][L, R] 完整覆盖 IiI_i，即 Si={[L,R]:L≤li, R≥ri}S_i=\{[L,R] : L\le l_i,\ R\ge r_i\}，所求即

∣⋃iSi∣=∑i∣Si∣−∑i∣Si∩Si+1∣\Bigg|\bigcup_{i} S_i\Bigg| = \sum_{i} |S_i| - \sum_{i}|S_i\cap S_{i+1}|

理解：设区间 [L,R][L,R] 完整覆盖了 kk 个 IiI_i，那么第一项计数 kk 次，第二项减去 k−1k-1 次，最终只计数一次。

异或线性基

求子集的数量，满足异或和为 0。答案为 2N−rank⁡2^{N-\operatorname{rank}}。

正则括号串

正则括号串 (Regular Bracket Sequence, RBS)：

  • 生成方式：连接与加括号
  • 前缀和保持非负
  • 一一对应于有序树 T=(T1T2…Tk)T = (T_{1}T_{2}\dots T_{k})
  • 一一对应于有序二叉树 T=(TL)TRT = (T_{L})T_{R}
    ——CuteCube
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 括号串（森林）-> 有序树，0 为虚拟根 
vector<vector<int>> build(string S) {
    S = "(" + S + ")";
    vector<vector<int>> adj;
    stack<int> s;
    for (auto c : S) {
        if (c == '(') {
            int x = int(adj.size());
            if (!s.empty()) {
                adj[s.top()].push_back(x);
            }
            s.push(x);
            adj.emplace_back();
        } else {
            s.pop();
        }
    }
    return adj;
}
// 有序树 -> 原括号串，跳过虚拟根 
string restore(const vector<vector<int>>& adj) {
    string S;
    auto dfs = [&](this auto&& self, int x) -> void {
        S += '(';
        for (auto y : adj[x]) {
            self(y);
        }
        S += ')';
    };
    for (auto y : adj[0]) {
        dfs(y);
    }
    return S;
}

例 1：删除 BS SS 至多 KK 个字符，最小化最长 RBS 子序列。(CF2233C)
先做一遍括号匹配，最后希望剩下 )))((，右括号与左括号有个分界点。重点是绝对不存在一对匹配的括号，左括号在左半区，右在右半区，所以所有匹配的括号对要么全在左半，要么全在右半。左半的括号对删左，右半删右。如此最优。

例 2：RBS SS，任意操作：选择两个不交的 RBS 子串，并交换位置。判断最终是否可以变换为 TT。(CF2210D)
在树上做，操作等价于：选两个没有祖先关系的点 x,yx, y，将 xx 的若干子节点的子树与 yy 的做交换。不变量：叶子节点数；从根到第一个分叉节点之间的节点数。