返回「邏輯與算法」主頁
本页面收录难以归类的知识点。对于公式和定理,另见 邏輯與算法:柿子 。
带权中位数 带权中位数 :给定数组 W , X W, X W , X ,保证 W i ≥ 0 W_i \ge 0 W i ≥ 0 。求 argmin k ∑ i = 1 N W i ∣ k − X i ∣ \displaystyle \operatorname*{argmin}_{k} \sum_{i=1}^{N} W_i \lvert k - X_i \rvert k argmin i = 1 ∑ N W i ∣ k − X i ∣ 。
先考虑不带权的,那么带权就是 X i X_i X i 出现了 W i W_i W i 次。按 X i X_i X i 升序排序,顺序累加 W i W_{i} W i ,找到第一个使得 W i W_{i} W i 的前缀和 ≥ 1 2 ∑ i = 1 N W i \displaystyle \ge \dfrac{1}{2}\sum \limits_{i=1}^{N} W_i ≥ 2 1 i = 1 ∑ N W i 的位置 m m m ,则最优解为 k ∗ = X m k^* = X_m k ∗ = X m 。
例 1 :N N N 个人围成一圈,第 i i i 个人初始有 A i A_i A i 个物品。i i i 与 ( i + 1 ) m o d N (i+1) \bmod N ( i + 1 ) mod N 每传递 1 1 1 个物品的代价为 B i B_i B i 。欲通过若干次传递使每个人手中的物品数量相同,求最小总代价。
设 d i = A i − A ˉ d_i = A_i - \bar{A} d i = A i − A ˉ 。设 i i i 传递给 ( i + 1 ) m o d N (i+1) \bmod N ( i + 1 ) mod N 了 c i c_i c i 个(可能为负)。根据物品守恒,c i = c N + D i c_i = c_N + D_i c i = c N + D i 。则总传递代价 Ans ( c N ) = ∑ i = 1 N B i ∣ c i ∣ = ∑ i = 1 N B i ∣ c N + D i ∣ \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 Ans ( c N ) = i = 1 ∑ N B i ∣ c i ∣ = i = 1 ∑ N B i ∣ c N + D i ∣ 。欲构造 c N c_N c N 以最小化 Ans ( c N ) \text{Ans}(c_N) Ans ( c N ) ,这就是带权中位数问题。
例 2 :序列 A , B A, B A , B ,设有理数序列 c , d c, d c , d 满足 ( A i + c i ) ( B j + d j ) = ( A j + c j ) ( B i + d i ) (A_i+c_i)(B_j+d_j)=(A_j+c_j)(B_i+d_i) ( A i + c i ) ( B j + d j ) = ( A j + c j ) ( B i + d i ) ,最小化 ∑ ∣ c i ∣ + ∣ d i ∣ \sum |c_i|+|d_i| ∑ ∣ c i ∣ + ∣ d i ∣ 。(ABC479G )
要么 c i ≡ 0 c_{i} \equiv 0 c i ≡ 0 ,要么 d i ≡ 0 d_{i} \equiv 0 d i ≡ 0 。以 c i ≡ 0 c_{i} \equiv 0 c i ≡ 0 为例,设 B i + d i = k A i B_i+d_i = k A_{i} B i + d i = k A i ,需最小化 ∑ ∣ d i ∣ = ∑ ∣ k A i − B i ∣ = ∑ ∣ A i ∣ ∣ k − B i A i ∣ \sum |d_{i}| = \sum |k A_{i} - B_{i}| = \sum |A_{i}| \biggl|k - \dfrac{B_{i}}{A_{i}}\biggr| ∑ ∣ d i ∣ = ∑ ∣ k A i − B i ∣ = ∑ ∣ A i ∣ k − A i B i ,这就是带权中位数问题。注意特判非零的 A A A 为空。
将 ( A i , B i ) (A_{i}, B_{i}) ( A i , B i ) 看作二维坐标系的点,将每个点移动到同一条过原点的直线,代价是 ∣ c i ∣ + ∣ d i ∣ |c_i|+|d_i| ∣ c i ∣ + ∣ d i ∣ 。当 ∣ k ∣ ⩽ 1 |k| \leqslant 1 ∣ k ∣ ⩽ 1 时,点纵向移动不劣,∣ k ∣ > 1 |k| > 1 ∣ k ∣ > 1 时,横向不劣。
广义单调栈 广义单调栈 :对序列的每个元素 A i A_i A i ,寻找最小的 j j j ,满足 j > i j > i j > i 且 不 满足偏序关系 A i ⪯ A j A_i \preceq A_j A i ⪯ A j 。比如我们熟知的:
⪯ \preceq ⪯ 定义为 x ≤ y x \le y x ≤ y 。找右侧第一个比自己小的数(最经典)。⪯ \preceq ⪯ 定义为 x ∣ y x \mid y x ∣ y 。找右侧第一个不能被自己整除的数。⪯ \preceq ⪯ 定义为 X ⊇ Y X \supseteq Y X ⊇ Y (利用位运算 (x & y) == y)。找右侧第一个不被自己包含的集合。⪯ \preceq ⪯ 定义为字符串 S x S_x S x 是 S y S_y S y 的前缀。找右侧第一个不以自己为前缀的字符串。任何满足传递性的…… 逆序遍历序列,用栈存储下标。设当前遍历到 i i i ,栈顶元素 j j j 。如果 A i ⪯ A j A_i \preceq A_j A i ⪯ A j ,就将 j j j 弹出栈。弹栈停止后,栈顶下标 j j j 就是 i i i 的所求。然后将 i i i 压入栈中。复杂度 O ( N ) O(N) O ( N ) 。
问 1:为什么如果 A i ⪯ A j A_i \preceq A_j A i ⪯ A j ,就将 j j j 弹出栈,这样做不会影响未来的结果?
设 k < i < j k < i < j k < i < j 。若 A k ⪯ A i A_k \preceq A_i A k ⪯ A i ,因为已知 A i ⪯ A j A_i \preceq A_j A i ⪯ A j ,则 A k ⪯ A j A_k \preceq A_j A k ⪯ A j ,那 j j j 不可能是 k k k 要找的答案;若 A k ⪯̸ A i A_k \not \preceq A_i A k ⪯ A i ,那 i i i 已经是 k k k 要找的答案,也不是 j j j 。因此直接将 j j j 弹出栈。
问 2:栈内的元素有单调性吗?
对于整数比大小来说,< < < 是全序关系,不满足 < < < 即 ⩾ \geqslant ⩾ ,天然是单调的。对于更一般的单调栈,并非如此。从栈顶到栈底,任意相邻的两个元素满足 A ⪯̸ B A \not\preceq B A ⪯ B 。但不是单调的链。
计算星期几 Kim Larsen Calculation Formula:年份 y ⩾ 1970 y \geqslant 1970 y ⩾ 1970 、月份 m m m 和日子 d d d ,计算星期。
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 ):N N N 点 M M M 边有向图,边权 W i ∈ [ 1 , 9 ] W_i \in [1, 9] W i ∈ [ 1 , 9 ] 。求从 1 1 1 到每个点 v v v 的所有路径中,边权序列所表示的大整数最小的路径。
先最小化路径长度,路径长度相同时,大整数比较即字典序比较。实现时用 BFS 分层,同一层的节点一起转移,先 f ( v ) ← 10 f ( u ) + c f(v) \gets 10 f(u) + c f ( v ) ← 10 f ( u ) + c ,再收集所有 f ( v ) f(v) f ( v ) 并离散化。复杂度 O ( M log N ) \mathcal{O}(M \log N) 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 ):N N N 点 M M M 边有向图,边权 W i W_i W i 。求从 S S S 到 T T T 恰好经过 K K K 条边的所有路径中,边权序列字典序最小的路径,输出 hash 值 ∑ i = 1 K W e i X K − i \sum_{i=1}^K W_{e_i} X^{K-i} ∑ i = 1 K W e i X K − i 。
倍增预处理,设 f k , u , v f_{k, u, v} f k , u , v :从 u u u 到 v v v ,长度为 2 k 2^{k} 2 k ,字典序最小的路径序列。拼凑得到 K K K 。
考虑 merge。传统做法是 f a + b , u , v = min w ( f a , u , w + f b , w , v ) f_{a+b, u, v} = \min_{w} (f_{a, u, w} + f_{b, w, v}) f a + b , u , v = min w ( f a , u , w + f b , w , v ) ,但不可直接维护序列,因而分别维护字典序和 hash 值。为比较字典序,同一批转移时先 r a + b , u , v ← r a , u , w N 2 + r b , w , v r_{a + b, u, v} \gets r_{a, u, w} N^{2} + r_{b, w, v} r a + b , u , v ← r a , u , w N 2 + r b , w , v ,再离散化,其中 + ∞ +\infty + ∞ 表示不可达。对于 hash 值,h a + b , u , v = h a , u , w ∗ X b + h b , w ∗ , v h_{a + b, u, v} = h_{a, u, w^{*}} X^{b} + h_{b, w^{*}, v} h a + b , u , v = h a , u , w ∗ X b + h b , w ∗ , v 。复杂度 O ( N 3 log K ) \mathcal{O}(N^3 \log K) O ( N 3 log K ) 。
排序不等式 排序不等式 :只改变配对方式,
∑ A i B π ( i ) \sum A_{i} B_{\pi(i)} ∑ A i B π ( i ) :同序最大,逆序最小∑ ∣ A i − B π ( i ) ∣ \sum |A_{i} - B_{\pi(i)}| ∑ ∣ A i − B π ( i ) ∣ :同序最小,逆序最大∑ ( A i − B π ( i ) ) 2 \sum (A_{i} - B_{\pi(i)})^{2} ∑ ( A i − B π ( i ) ) 2 :同序最小,逆序最大例 :序列 A , B A, B A , B ,其中 ∣ A ∣ ⩽ ∣ B ∣ |A| \leqslant |B| ∣ A ∣ ⩽ ∣ B ∣ ,选取 B B B 的任一 ∣ A ∣ |A| ∣ A ∣ 元子列的任一排列 b b b ,最大化 ∑ ∣ A i − b i ∣ \sum |A_{i}-b_{i}| ∑ ∣ A i − b i ∣ 。(CF1921D )
不妨设 A A A 递增。由排序不等式,b b b 递减,将 B B B 倒序排序,再选取一个递减子列 b b b 。而且 b b b 是 B B B 的某前缀与某后缀拼接起来的。枚举分界点计算答案。O ( N log N ) \mathcal{O}(N\log N) O ( N log N ) 。
区间包含树 区间包含树 :给定若干区间 [ L i , R i ) [L_i,R_i) [ L i , R i ) ,要么互不相交(R i ≤ L j R_i \le L_j R i ≤ L j ),要么一个包含另一个(L i ≤ L j < R j ≤ R i L_i \le L_j < R_j \le R_i L i ≤ L j < R j ≤ R i ),不存在交叉重叠(L i < L j < R i < R j L_{i} < L_{j} < R_{i} < R_{j} L 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 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 p p p and q q q Modulus n = p × q n = p \times q n = p × q Public Exponent e e e : 1 < e < ϕ ( n ) 1 < e < \phi(n) 1 < e < ϕ ( n ) and e ⊥ ϕ ( n ) e \perp \phi(n) e ⊥ ϕ ( n ) Private Exponent d d d : d × e ≡ 1 ( m o d ϕ ( n ) ) d \times e \equiv 1 \pmod{\phi(n)} d × e ≡ 1 ( mod ϕ ( n )) Result
Public Key: ( e , n ) (e, n) ( e , n ) - distributed to everyone Private Key: ( d , n ) (d, n) ( d , n ) - kept secret Encryption (Confidentiality)
Suppose Alice wants to send an integer m m m (where 0 ≤ m < n 0 \le m < n 0 ≤ m < n ) to Bob Encryption : Alice computes c ≡ m e ( m o d n ) c \equiv m^e \pmod n c ≡ m e ( mod n ) using Bob ’s public key ( e , n ) (e, n) ( e , n ) Transmission : Bob receives the ciphertext c c c Decryption : Bob computes m ≡ c d ( m o d n ) m \equiv c^{d} \pmod n m ≡ c d ( mod n ) using his private key ( d , n ) (d, n) ( d , n ) Obviously, m ≡ c d ≡ m e d ≡ m k ϕ ( n ) + 1 ≡ m ( m o d n ) m \equiv c^{d} \equiv m^{e d} \equiv m^{k \phi(n) + 1} \equiv m \pmod n m ≡ c d ≡ m e d ≡ m k ϕ ( n ) + 1 ≡ m ( mod n ) for some integer k k k 上升子序列 把序列划分为若干条不升链,最小化链的数量。
链的数量的最小值,等于最长上升子序列长度。
【DP 法】f ( i ) f(i) f ( i ) :以 A i A_{i} A 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]); }
【二分法】f ( k ) f(k) f ( k ) :已处理前缀中,长度为 k + 1 k + 1 k + 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 (); chains[pos].push_back (v); *it = v; } int ans = rgs::lower_bound (f, inf) - f.begin ();chains.resize (ans);
例:每个机器人从时刻 0 0 0 开始,速度不超过 1 1 1 。机器人仅当在时刻 T i T_i T i 位于坐标 X i X_i X i 时,才能收集苹果 i i i 。最小化机器人数量。(ABC457G )
如果 T i < T j T_i < T_j T i < T j ,单个机器人能够同时收集苹果 i i i 和苹果 j j j ⟺ ∣ X i − X j ∣ ⩽ T j − T i ⟺ { X i + T i ⩽ X j + T j X i − T i ⩾ X j − T j ⇔ ( u , v ) = ( X − T , X + T ) { u i ⩾ u j v i ⩽ v j \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} ⟺ ∣ X i − X j ∣ ⩽ T j − T i ⟺ { X i + T i ⩽ X j + T j X i − T i ⩾ X j − T j ( u , v ) = ( X − T , X + T ) { u i ⩾ u j v i ⩽ v j 。同一个机器人收集的一组苹果在这个偏序关系中构成一条链。问题即求覆盖所有点的最少链数,这等于最大反链的大小。将所有点按 ( u , − v ) (u, -v) ( u , − v ) 升序排序,求 v v v 的最长上升子序列。
势能与停时 给状态 S S S 设定势能函数 Φ ( S ) \Phi(S) Φ ( S ) ,使得每操作一次,势能 Φ ( S ) \Phi(S) Φ ( S ) 期望减少 1,且终止态无法继续转移,那么从当前态到终止态的期望为 Φ ( S begin ) − Φ ( S end ) \Phi(S_{\text{begin}}) - \Phi(S_{\text{end}}) Φ ( S begin ) − Φ ( S end ) 。
例:N N N 点森林,第 i i i 棵树不超过 2 层,有 C i C_{i} C i 个叶子。每次操作随机有序选择两个不同的根 A , B A, B A , B ,连接 A → B A\to B A → B 并断开 B B B 和它的所有子节点。反复操作,直至剩一棵树。求停止时的期望步数。(CF1025G )
Φ ( G ) \Phi(G) Φ ( G ) :森林 G G G 的势能。每操作一次,势能减少 1。所求为 Φ ( G 0 ) − Φ ( G n ) \Phi(G_{0}) - \Phi(G_{n}) Φ ( G 0 ) − Φ ( G n ) 。
ϕ ( x ) \phi(x) ϕ ( x ) :有 x x x 个叶子的树的势能。若森林 G G G 的第 i i i 棵树有 x i x_{i} x i 个叶子,定义 Φ ( G ) = ∑ ϕ ( x i ) \Phi(G)=\sum \phi(x_{i}) Φ ( G ) = ∑ ϕ ( x i ) 。
设 A , B A, B A , B 的叶子数量分别为 x , y x,y x , y ,依题意有转移
[ ϕ ( x ) + ϕ ( y ) ] − 1 = 1 2 [ ϕ ( x + 1 ) + y ϕ ( 0 ) ] + 1 2 [ ϕ ( 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 ) + ϕ ( y )] − 1 = 2 1 [ ϕ ( x + 1 ) + y ϕ ( 0 )] + 2 1 [ ϕ ( y + 1 ) + x ϕ ( 0 )]
取 x = y x=y x = y 有 ϕ ( x ) − 1 = 1 2 [ ϕ ( x + 1 ) + x ϕ ( 0 ) ] \phi(x) - 1 = \dfrac{1}{2} [\phi(x+1)+x\phi(0)] ϕ ( x ) − 1 = 2 1 [ ϕ ( x + 1 ) + x ϕ ( 0 )] 。不妨设 ϕ ( 0 ) = 0 \phi(0)=0 ϕ ( 0 ) = 0 ,则 ϕ ( x ) − 1 = 1 2 ϕ ( x + 1 ) \phi(x) - 1 = \dfrac{1}{2} \phi(x+1) ϕ ( x ) − 1 = 2 1 ϕ ( x + 1 ) ,解得 ϕ ( x ) = 1 − 2 x \phi(x)=1-2^{x} ϕ ( x ) = 1 − 2 x 。因此答案为 ∑ ( 1 − 2 C i ) − ( 1 − 2 n − 1 ) \sum(1-2^{C_{i}})-(1-2^{n-1}) ∑ ( 1 − 2 C i ) − ( 1 − 2 n − 1 ) 。
这里也不能太过随意,需要满足:① DP 末态为一个确定的数;② 所有定义的值满足原有公式。
树点边容斥 树点边容斥 :设树 T = ( V , E ) T=(V,E) T = ( V , E ) ,设计数对象 S S S 对应一个非空顶点集合 A ( S ) ⊂ V A(S)\subset V A ( S ) ⊂ V ,且 T [ A ( S ) ] T[A(S)] T [ A ( S )] 连通,那么 ∣ S ∣ = ∑ v ∈ V # { S : v ∈ A ( S ) } − ∑ e = u v ∈ 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)\} ∣ S ∣ = ∑ v ∈ V # { S : v ∈ A ( S )} − ∑ e = uv ∈ E # { S : u , v ∈ A ( S )} 。也就是 # { \#\{ # { 对象 } = ∑ v # { \}=\sum_v\#\{ } = ∑ v # { 经过 v v v 的对象 } − ∑ e # { \}-\sum_e\#\{ } − ∑ e # { 经过 e e e 的对象 } \} } 。
引理:树有 ∣ V ∣ − ∣ E ∣ = 1 |V|-|E|=1 ∣ V ∣ − ∣ E ∣ = 1 。 理解:设 T [ A ( S ) ] = ( V ( S ) , E ( S ) ) 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 ( S ) ∣ − ∣ E ( S ) ∣ 。把两项分别写成指示函数,1 = ∑ v ∈ V [ v ∈ A ( S ) ] − ∑ e = u v ∈ E [ u , v ∈ A ( S ) ] 1=\sum_{v\in V}[v\in A(S)]-\sum_{e=uv\in E}[u,v\in A(S)] 1 = ∑ v ∈ V [ v ∈ A ( S )] − ∑ e = uv ∈ E [ u , v ∈ A ( S )] ,对所有对象 S ∈ S S\in\mathcal S S ∈ S 求和,∣ S ∣ = ∑ S ∈ S ∑ v ∈ V [ v ∈ A ( S ) ] − ∑ S ∈ S ∑ e = u v ∈ 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)] ∣ S ∣ = ∑ S ∈ S ∑ v ∈ V [ v ∈ A ( S )] − ∑ S ∈ S ∑ e = uv ∈ E [ u , v ∈ A ( S )] ,交换求和次序后即得结论。
推论 :设若干区间 I i = [ l i , r i ] I_i=[l_i,r_i] I i = [ l i , r i ] 满足 l i < l i + 1 l_i<l_{i+1} l i < l i + 1 ,r i < r i + 1 r_i<r_{i+1} r i < r i + 1 ,求区间 J = [ L , R ] J = [L, R] J = [ L , R ] 的数量,满足 J J J 至少包含一个 I i I_i I i 。设 S i S_i S i 表示区间 [ L , R ] [L, R] [ L , R ] 完整覆盖 I i I_i I i ,即 S i = { [ L , R ] : L ≤ l i , R ≥ r i } S_i=\{[L,R] : L\le l_i,\ R\ge r_i\} S i = {[ L , R ] : L ≤ l i , R ≥ r i } ,所求即
∣ ⋃ i S i ∣ = ∑ i ∣ S i ∣ − ∑ i ∣ S i ∩ S i + 1 ∣ \Bigg|\bigcup_{i} S_i\Bigg| = \sum_{i} |S_i| - \sum_{i}|S_i\cap S_{i+1}| i ⋃ S i = i ∑ ∣ S i ∣ − i ∑ ∣ S i ∩ S i + 1 ∣
理解:设区间 [ L , R ] [L,R] [ L , R ] 完整覆盖了 k k k 个 I i I_i I i ,那么第一项计数 k k k 次,第二项减去 k − 1 k-1 k − 1 次,最终只计数一次。
贪心再反悔 另见:延迟决策。好的不一定好,坏的是一定坏。
例 1:第一天早上没有钱。在第 i i i 天白天,可以花费 C i C_i C i 元买一个菠萝派;第 i i i 天晚上得到 X X X 元。这 N N N 天最多能吃几个菠萝派。(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:第 i i i 天菠萝派的价格调整为 C i C_i C i 。每天要么买一个菠萝派,要么卖一个,要么什么都不干。希望在第 N N N 天结束时不持有菠萝派,并最大化盈利。(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。答案为 2 N − rank 2^{N-\operatorname{rank}} 2 N − rank 。
折半与分治 Discrete Logarithm Problem (DLP) : Given a prime p p p , a base g g g , and a target h h h . Solve for the non-negative integer x x x in g x ≡ h ( m o d p ) g^x \equiv h \pmod p g x ≡ h ( mod p ) .
BSGS (Baby-Step Giant-Step) : Express x x x as x = i ⋅ B − j x = i \cdot B - j x = i ⋅ B − j , where 1 ≤ i ≤ ⌈ p / B ⌉ 1 \le i \le \lceil p/B \rceil 1 ≤ i ≤ ⌈ p / B ⌉ and 0 ≤ j < B 0 \le j < B 0 ≤ j < B . Then ( g B ) i ⋅ h − 1 ≡ g j ( m o d p ) (g^B)^i \cdot h^{-1} \equiv g^j \pmod p ( g B ) i ⋅ h − 1 ≡ g j ( mod p ) .
Precomputation : Compute the baby-step values g j ( m o d p ) g^j \pmod p g j ( mod p ) for all j ∈ [ 0 , B − 1 ] j \in [0, B - 1] j ∈ [ 0 , B − 1 ] .Query : For each h h h , sequentially compute giant-step terms ( g B ) i ⋅ h − 1 ( m o d p ) (g^B)^i \cdot h^{-1} \pmod p ( g B ) i ⋅ h − 1 ( mod p ) for i ∈ [ 1 , ⌈ p / B ⌉ ] i \in [1, \lceil p/B \rceil] i ∈ [ 1 , ⌈ p / B ⌉] , and look up V i V_i V i in the precomputed hash map.Time and Space: O ( B + m p / B ) = O ( m p ) \mathcal{O}(B + m p / B)=\mathcal{O}(\sqrt{ m p}) O ( B + m p / B ) = O ( 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 C C C of non-negative integers with ∣ C ∣ = 2 M ⩽ 2 20 |C|=2^{M} \leqslant 2^{20} ∣ C ∣ = 2 M ⩽ 2 20 and N = ∑ C i ⩽ 2 × 10 5 N=\sum C_{i} \leqslant 2 \times 10^{5} N = ∑ C i ⩽ 2 × 1 0 5 , compute for all s s s :
Ans ( s ) = ∑ i ⊕ j = s min ( C i , C j ) \text{Ans}(s) = \sum_{i\oplus j=s} \min(C_{i},C_{j}) Ans ( s ) = i ⊕ j = s ∑ min ( C i , C j )
Method 1 . Enumerate all pairs ( i , j ) (i,j) ( i , j ) . Time : O ( ( 2 M ) 2 ) O((2^M)^2) O (( 2 M ) 2 ) .
Optimize 1 : Enumerate only pairs ( i , j ) (i,j) ( i , j ) with C i , C j > 0 C_{i}, C_{j}>0 C i , C j > 0 . Time : O ( N 2 ) O(N^2) O ( N 2 ) .
Method 2 . Note that
min ( C i , C j ) = ∑ x = 1 max ( C ) [ C i ⩾ x ] ⋅ [ C j ⩾ x ] \min(C_{i},C_{j}) = \sum_{x=1}^{\max(C)} [C_{i} \geqslant x] \cdot [C_{j} \geqslant x] min ( C i , C j ) = x = 1 ∑ m a x ( C ) [ C i ⩾ x ] ⋅ [ C j ⩾ x ]
Enumerate x x x and compute the XOR convolution. Time : O ( M 2 M max ( C ) ) O(M 2^M \max(C)) O ( M 2 M max ( C )) .
Method 1+2 . Choose an appropriate threshold B B B . Decompose
min ( C i , C j ) = min ( C i , C j , B ) + max ( 0 , min ( C i , C j ) − B ) \min(C_i, C_j) = \min(C_i, C_j, B) + \max(0, \min(C_i, C_j) - B) min ( C i , C j ) = min ( C i , C j , B ) + max ( 0 , min ( C i , C j ) − B )
Then
Ans ( s ) = ∑ x = 1 B ∑ i ⊕ j = s [ C i ≥ x ] ⋅ [ C j ≥ x ] + ∑ i ⊕ j = s min ( C i , C j ) ⩾ B ( min ( C i , C j ) − 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) Ans ( s ) = x = 1 ∑ B i ⊕ j = s ∑ [ C i ≥ x ] ⋅ [ C j ≥ x ] + i ⊕ j = s m i n ( C i , C j ) ⩾ B ∑ ( min ( C i , C j ) − B )
For x = 1 , 2 , … , B x=1,2,\ldots,B x = 1 , 2 , … , B , use the method 2, and enumerate all pairs ( i , j ) (i,j) ( i , j ) such that min ( C i , C j ) ⩾ B \min(C_{i},C_{j}) \geqslant B min ( C i , C j ) ⩾ B using method 1.
Time: O ( B M 2 M + ( N B ) 2 ) \mathcal{O}\bigg(B M 2^M + \Big(\dfrac{N}{B}\Big)^2 \bigg) O ( BM 2 M + ( B N ) 2 ) .
By taking B = N 2 M 2 M 3 B = \sqrt[3]{\dfrac{N^2}{M2^M} } B = 3 M 2 M N 2 , this becomes O ( ( N M 2 M ) 2 3 ) \mathcal{O}\bigg(\big(NM2^M\big)^{\frac{2}{3}}\bigg) O ( ( NM 2 M ) 3 2 ) .
正则括号串 正则括号串 (Regular Bracket Sequence, RBS) :
生成方式:连接与加括号 前缀和保持非负 一一对应于有序树 T = ( T 1 T 2 … T k ) T = (T_{1}T_{2}\dots T_{k}) T = ( T 1 T 2 … T k ) 一一对应于有序二叉树 T = ( T L ) T R T = (T_{L})T_{R} T = ( 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 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 S S S 至多 K K K 个字符,最小化最长 RBS 子序列。(CF2233C ) 先做一遍括号匹配,最后希望剩下 )))((,右括号与左括号有个分界点。重点是绝对不存在一对匹配的括号,左括号在左半区,右在右半区,所以所有匹配的括号对要么全在左半,要么全在右半。左半的括号对删左,右半删右。如此最优。
例 2 :RBS S S S ,任意操作:选择两个不交的 RBS 子串,并交换位置。判断最终是否可以变换为 T T T 。(CF2210D ) 在树上做,操作等价于:选两个没有祖先关系的点 x , y x, y x , y ,将 x x x 的若干子节点的子树与 y y y 的做交换。不变量:叶子节点数;从根到第一个分叉节点之间的节点数。