返回「邏輯與算法」主頁

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

带权中位数

带权中位数:给定数组 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 时,横向不劣。

广义单调栈

广义单调栈 :对序列的每个元素 AiA_i,寻找最小的 jj,满足 j>ij > i 且 不 满足偏序关系 Ai⪯AjA_i \preceq A_j。比如我们熟知的:

  • ⪯\preceq 定义为 x≤yx \le y。找右侧第一个比自己小的数(最经典)。
  • ⪯\preceq 定义为 x∣yx \mid y。找右侧第一个不能被自己整除的数。
  • ⪯\preceq 定义为 X⊇YX \supseteq Y(利用位运算 (x & y) == y)。找右侧第一个不被自己包含的集合。
  • ⪯\preceq 定义为字符串 SxS_x 是 SyS_y 的前缀。找右侧第一个不以自己为前缀的字符串。
  • 任何满足传递性的……

逆序遍历序列,用栈存储下标。设当前遍历到 ii,栈顶元素 jj。如果 Ai⪯AjA_i \preceq A_j,就将 jj 弹出栈。弹栈停止后,栈顶下标 jj 就是 ii 的所求。然后将 ii 压入栈中。复杂度 O(N)O(N)。

问 1:为什么如果 Ai⪯AjA_i \preceq A_j,就将 jj 弹出栈,这样做不会影响未来的结果?

设 k<i<jk < i < j。若 Ak⪯AiA_k \preceq A_i,因为已知 Ai⪯AjA_i \preceq A_j,则 Ak⪯AjA_k \preceq A_j,那 jj 不可能是 kk 要找的答案;若 Ak⪯̸AiA_k \not \preceq A_i,那 ii 已经是 kk 要找的答案,也不是 jj。因此直接将 jj 弹出栈。

问 2:栈内的元素有单调性吗?

对于整数比大小来说,<< 是全序关系,不满足 << 即 ⩾\geqslant,天然是单调的。对于更一般的单调栈,并非如此。从栈顶到栈底,任意相邻的两个元素满足 A⪯̸BA \not\preceq B。但不是单调的链。

计算星期几

Kim Larsen Calculation Formula:年份 y⩾1970y \geqslant 1970、月份 mm 和日子 dd,计算星期。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int d[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool isLeap(int y) {
return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);
}

int daysInMonth(int y, int m) {
return d[m - 1] + (isLeap(y) && m == 2);
}

int getDay(int y, int m, int d) {
int ans = 0;
for (int i = 1970; i < y; i++) {
ans += 365 + isLeap(i);
}
for (int i = 1; i < m; i++) {
ans += daysInMonth(y, i);
}
ans += d;
return (ans + 2) % 7 + 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;
}

RSA算法

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

上升子序列

把序列划分为若干条不升链,最小化链的数量。

  1. 链的数量的最小值,等于最长上升子序列长度。

  2. 【DP 法】f(i)f(i):以 AiA_{i} 结尾的最长上升子序列长度。按原序列下标记录。DP 值相同的元素按原顺序就是一条不升链。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> dp(n, 1);
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]);
}
vector<vector<int>> chains(ans);
for (int i = 0; i < n; i++) {
chains[dp[i] - 1].push_back(arr[i]);
}
  1. 【二分法】f(k)f(k):已处理前缀中,长度为 k+1k + 1 的上升子序列结尾元素的最小值。按子序列长度记录。找到位置不要直接替换,而是存起来,最后每个位置的所有数就是一条链。
1
2
3
4
5
6
7
8
9
10
vector<int> f(n, inf);
vector<vector<int>> chains(n);
for (auto v : arr) {
auto it = rgs::lower_bound(f, v);
int pos = it - f.begin(); // pos + 1 == dp[i]
chains[pos].push_back(v);
*it = v;
}
int ans = rgs::lower_bound(f, inf) - f.begin();
chains.resize(ans);

例:每个机器人从时刻 00 开始,速度不超过 11。机器人仅当在时刻 TiT_i 位于坐标 XiX_i 时,才能收集苹果 ii。最小化机器人数量。(ABC457G)

如果 Ti<TjT_i < T_j,单个机器人能够同时收集苹果 ii 和苹果 jj   ⟺  ∣Xi−Xj∣⩽Tj−Ti  ⟺  {Xi+Ti⩽Xj+TjXi−Ti⩾Xj−Tj⇔(u,v)=(X−T,X+T){ui⩾ujvi⩽vj\iff \vert X_i-X_j \vert \leqslant T_j-T_i \iff \begin{cases} X_{i}+T_{i} \leqslant X_{j}+T_{j} \\ X_{i}-T_{i} \geqslant X_{j}-T_{j} \end{cases} \xLeftrightarrow{(u,v)=(X-T,X+T)} \begin{cases} u_{i} \geqslant u_{j} \\ v_{i} \leqslant v_{j} \end{cases}。同一个机器人收集的一组苹果在这个偏序关系中构成一条链。问题即求覆盖所有点的最少链数,这等于最大反链的大小。将所有点按 (u,−v)(u, -v) 升序排序,求 vv 的最长上升子序列。

势能与停时

给状态 SS 设定势能函数 Φ(S)\Phi(S),使得每操作一次,势能 Φ(S)\Phi(S) 期望减少 1,且终止态无法继续转移,那么从当前态到终止态的期望为 Φ(Sbegin)−Φ(Send)\Phi(S_{\text{begin}}) - \Phi(S_{\text{end}})。

例:NN 点森林,第 ii 棵树不超过 2 层,有 CiC_{i} 个叶子。每次操作随机有序选择两个不同的根 A,BA, B,连接 A→BA\to B 并断开 BB 和它的所有子节点。反复操作,直至剩一棵树。求停止时的期望步数。(CF1025G)

Φ(G)\Phi(G):森林 GG 的势能。每操作一次,势能减少 1。所求为 Φ(G0)−Φ(Gn)\Phi(G_{0}) - \Phi(G_{n})。

ϕ(x)\phi(x):有 xx 个叶子的树的势能。若森林 GG 的第 ii 棵树有 xix_{i} 个叶子,定义 Φ(G)=∑ϕ(xi)\Phi(G)=\sum \phi(x_{i})。

设 A,BA, B 的叶子数量分别为 x,yx,y,依题意有转移

[ϕ(x)+ϕ(y)]−1=12[ϕ(x+1)+yϕ(0)]+12[ϕ(y+1)+xϕ(0)][\phi(x) + \phi(y)] - 1= \frac{1}{2} [\phi(x+1)+y\phi(0)] + \frac{1}{2} [\phi(y+1)+x\phi(0)]

取 x=yx=y 有 ϕ(x)−1=12[ϕ(x+1)+xϕ(0)]\phi(x) - 1 = \dfrac{1}{2} [\phi(x+1)+x\phi(0)]。不妨设 ϕ(0)=0\phi(0)=0,则 ϕ(x)−1=12ϕ(x+1)\phi(x) - 1 = \dfrac{1}{2} \phi(x+1),解得 ϕ(x)=1−2x\phi(x)=1-2^{x}。因此答案为 ∑(1−2Ci)−(1−2n−1)\sum(1-2^{C_{i}})-(1-2^{n-1})。

这里也不能太过随意,需要满足:① DP 末态为一个确定的数;② 所有定义的值满足原有公式。

树点边容斥

树点边容斥:设树 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 次,最终只计数一次。

贪心再反悔

另见:延迟决策。好的不一定好,坏的是一定坏。

例 1:第一天早上没有钱。在第 ii 天白天,可以花费 CiC_i 元买一个菠萝派;第 ii 天晚上得到 XX 元。这 NN 天最多能吃几个菠萝派。(CF1974G)

白天先不考虑钱无脑买,如果钱变成负数,就从之前买过的挑一个最贵的不买。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
i64 sum = 0;
priority_queue<int> q;
for (int i = 0; i < N; i++) {
int C;
cin >> C;
q.push(C);
sum -= C;
if (sum < 0) {
sum += q.top();
h.pop();
}
sum += X;
}
cout << q.size() << "\n";

例 2:第 ii 天菠萝派的价格调整为 CiC_i。每天要么买一个菠萝派,要么卖一个,要么什么都不干。希望在第 NN 天结束时不持有菠萝派,并最大化盈利。(CF865D)

1
2
3
4
5
6
7
8
9
10
11
12
13
i64 ans = 0;
priority_queue<int, vector<int>, greater<>> q;
for (int i = 0; i < N; i++) {
int x;
cin >> x;
if (!q.empty() && q.top() < x) {
ans += x - q.top();
q.pop();
q.push(x);
}
q.push(x);
}
cout << ans << "\n";

异或线性基

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

折半与分治

Discrete Logarithm Problem (DLP): Given a prime pp, a base gg, and a target hh. Solve for the non-negative integer xx in gx≡h(modp)g^x \equiv h \pmod p.

BSGS (Baby-Step Giant-Step): Express xx as x=i⋅B−jx = i \cdot B - j, where 1≤i≤⌈p/B⌉1 \le i \le \lceil p/B \rceil and 0≤j<B0 \le j < B. Then (gB)i⋅h−1≡gj(modp)(g^B)^i \cdot h^{-1} \equiv g^j \pmod p.

  • Precomputation: Compute the baby-step values gj(modp)g^j \pmod p for all j∈[0,B−1]j \in [0, B - 1].
  • Query: For each hh, sequentially compute giant-step terms (gB)i⋅h−1(modp)(g^B)^i \cdot h^{-1} \pmod p for i∈[1,⌈p/B⌉]i \in [1, \lceil p/B \rceil], and look up ViV_i in the precomputed hash map.

Time and Space: O(B+mp/B)=O(mp)\mathcal{O}(B + m p / B)=\mathcal{O}(\sqrt{ m p}).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
constexpr int B = 5000000;
vector<Z> powg(B + 1);
vector<pair<Z, int>> mp;
powg[0] = 1;
for (int j = 0; j < B; j++) {
mp.push_back({powg[j], j});
powg[j + 1] = powg[j] * 3;
}
ranges::sort(mp);

auto log = [&](Z h) -> Z1 {
if (h == 1) return 0;
if (h == 0) return -1;
Z x = powg[B] / h;
for (int i = 1; ; i++) {
auto it = ranges::lower_bound(mp, pair(x, -1));
if (it != mp.end() && it->first == x) {
return Z1(i) * B - it->second;
}
x *= powg[B];
}
};

Example (ARC222E).

Description. Given a sequence CC of non-negative integers with ∣C∣=2M⩽220|C|=2^{M} \leqslant 2^{20} and N=∑Ci⩽2×105N=\sum C_{i} \leqslant 2 \times 10^{5}, compute for all ss:

Ans(s)=∑i⊕j=smin⁡(Ci,Cj)\text{Ans}(s) = \sum_{i\oplus j=s} \min(C_{i},C_{j})

Method 1. Enumerate all pairs (i,j)(i,j). Time: O((2M)2)O((2^M)^2).

Optimize 1: Enumerate only pairs (i,j)(i,j) with Ci,Cj>0C_{i}, C_{j}>0. Time: O(N2)O(N^2).

Method 2. Note that

min⁡(Ci,Cj)=∑x=1max⁡(C)[Ci⩾x]⋅[Cj⩾x]\min(C_{i},C_{j}) = \sum_{x=1}^{\max(C)} [C_{i} \geqslant x] \cdot [C_{j} \geqslant x]

Enumerate xx and compute the XOR convolution. Time: O(M2Mmax⁡(C))O(M 2^M \max(C)).

Method 1+2. Choose an appropriate threshold BB. Decompose

min⁡(Ci,Cj)=min⁡(Ci,Cj,B)+max⁡(0,min⁡(Ci,Cj)−B)\min(C_i, C_j) = \min(C_i, C_j, B) + \max(0, \min(C_i, C_j) - B)

Then

Ans(s)=∑x=1B∑i⊕j=s[Ci≥x]⋅[Cj≥x]+∑i⊕j=smin⁡(Ci,Cj)⩾B(min⁡(Ci,Cj)−B)\text{Ans}(s) = \sum_{x=1}^B \sum_{i \oplus j = s} [C_i \ge x] \cdot [C_j \ge x] + \sum_{\substack{i \oplus j = s \\ \min(C_{i},C_{j}) \geqslant B}} (\min(C_i, C_j) - B)

For x=1,2,…,Bx=1,2,\ldots,B, use the method 2, and enumerate all pairs (i,j)(i,j) such that min⁡(Ci,Cj)⩾B\min(C_{i},C_{j}) \geqslant B using method 1.

Time: O(BM2M+(NB)2)\mathcal{O}\bigg(B M 2^M + \Big(\dfrac{N}{B}\Big)^2 \bigg).

By taking B=N2M2M3B = \sqrt[3]{\dfrac{N^2}{M2^M} }, this becomes O((NM2M)23)\mathcal{O}\bigg(\big(NM2^M\big)^{\frac{2}{3}}\bigg).

正则括号串

正则括号串 (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 的做交换。不变量:叶子节点数;从根到第一个分叉节点之间的节点数。