Bit-by-bit greedy¶
試填法¶
可以透過整數的連續性將試填法分成兩種做法:
- 假設 i-th 為 1/0 則，能否有符合限制的前綴。
for(int i = hi; i >= 0; --i) {
mask |= 1 << i;
int nxt = ans | (1 << i);
for(auto ...) {//traverse element to meet the requirments
res [op=] (x & mask);
if(check ...) {
ans = nxt
...
}
...
}
}
-
題目要求找出最大 \(x \oplus y\)，透過維護前綴 mask 以及在 i-th 位元試填 nxt，使用 hash table 找出是否有 \(nxt \oplus x_{pre_i}\)，若有表示 i-th 可以填 1。
-
2935. Maximum Strong Pair XOR II
題目要求找出符合限制的 \(x \oplus y\)，透過維護前綴 mask 以及在 i-th 位元試填 nxt，使用 hash table 找到能否有符合題目要求的 \(nxt \oplus x_{pre_i}\)，若有表示 i-th 可以填 1。
-
這題乍看之下要使用下面的方法做逐位排除確定，但是從 [7,3,15,14,2,8] 這個例子會發現這樣沒辦法得到解答，可以發現若是題目把可以操作的元素限制在一個集合當中，並且要透過維護一些性質並計算出答案，就要使用類似上面的模板的思考方向。
這題是要求限制 k 次 AND 操作後集合中的元素進行 OR 所得最小，透過維護前綴 mask 確定那些位元會是 0 得到當前操作 \(\le k\) 次的解。
-
貢獻法 + 試填法。構造出 target 需要多少貢獻，選最小貢獻的 m 做 AND。
-
基本上就是先填看看 0 ，然後看能夠選的選的元素中是否有符合當前bit為0的元素。
怎樣能夠選? 已經選了前綴 mask ，我們剩下能選的部分是"前綴 + \(2^i - 1\) 的子集。
-
Codeforces:
-
直覺的貪心會掉進陷阱，必須逐位元維護那些數是沿著 limit n，那些數是小於 n。
-
核心想法:
若是題目把可以操作的元素限制在一個有限集合(大小大概是 \(10^5\) )當中。透過維護前綴 mask 每次都只取 x 前綴，在遍歷過程中維護題目要求，重點在於遍歷的過程中要滿足限制。
有些題目可以使用 0-1 Trie 完成。
-
k-th lexicographical binary string
-
對於每一位，假設這一位是 0/1，計算後面還能構成多少合法字串，如果 \(\ge k\)，就選 0，否則選 1 並扣掉數量。
-
或者假設這一位是 1，計算左邊和右邊可以產生多少貢獻 x x x 1 o o .. ，如果 \(\le k\) 那就把這位設為 1 並扣掉貢獻。
-
核心想法: 利用整數的連續性，不斷縮小規模從而確定答案。
-
-
計算 i-th 設 1 會產生出的貢獻，若是小於 k ，減去貢獻並縮小規模，貢獻的公式 \(cnt = pre_i \times 2^i + \lfloor \frac{i}{x} \rfloor \times 2^{i - 1}\)，直觀理解為右邊有 \(2^i\) 的方案數可以使左邊 \(pre_i\) 產生貢獻。對於右邊的情況則可以用組合數學的方式思考，在 [0, i - 1] 位元上共有 \(\lfloor \frac{i}{x} \rfloor\) 個是可以產生貢獻的位元，對於每個位元其可以產生的貢獻為 \(2^{i - 1}\)，\(2^{i - 1}\) 代表著除了自己之外的方案數，兩個相乘 \(\lfloor \frac{i}{x} \rfloor \times 2^{i - 1}\) 表示在 x 位置上可以產生的貢獻。
-
這題跟上面那題的思路是一樣的，只有在細節上不一樣，因為題目限制只有 2 的冪次相乘，所以可以將相乘的計算改為冪次和的計算，避免數值溢出。另外對於右邊的冪次和 \(\sum_{0}^{x = i - 1} x * 2^{i - 1}\)，所以可以利用等差級數和公式得到 \(\frac{i(i - 1)}{2} \times 2^{i - 1}\)。
-
由高位至低位透過假設 i-th bit 填 0 的方案數決定這個位元是否填 1
-
這題要計算的是 $\(\sum_{j, k}(j \text{ OR } k) = \sum_{j, k} \sum_m(j \text{ OR } k) \text{ AND } 2^m = \sum_m \sum_{j, k} (j \text{ AND } 2^m) \text{ OR } (k \text{ AND } 2^m)\)$
由於 \(j \text{ AND } 2^m\) 只會是 \(2^m\) 或是 0，所以可以轉化為 \(n^2 - cnt^2(j \text{ AND } 2^m = 0)\)，用全部可能 \(n^2\) 減去兩側皆為 0 的情況:
\[\sum_{j, k} \sum_m(j \text{ AND } 2^m) \text{ OR } (k \text{ AND } 2^m) = \sum_{j, k} \sum_m 2^m(n^2 - Card^2\{j | j \text{AND} 2^m = 0\})\]設函數 \(Z(n, m) = Card\{j | 0 \le j < n, j \text{AND} 2^m = 0\}\) 為 \([0, n - 1]\) 的數中第 m 位為 0 的個數。
\[\sum_{j, k} \sum_m(j \text{ AND } 2^m) \text{ OR } (k \text{ AND } 2^m) = \sum_m 2^m(n^2 - Z^2(n, m))\]可以發現 0, 1 在 [0, n - 1] 中是週期性出現的，所以 Z(n, m) 可以利用這個性質很容易的求出，我們可以利用二分的方式得到 \(O(\log^2{n})\) 的方法。
可以發現我們要計算的整數範圍是 [0, n - 1]，由整數的連續性可以知道可以透過逐位確定不斷縮小問題規模。
增量計算¶
要使用逐位確定的話必須求出在第 i 位產生的貢獻，假設 \(n = a \cdot 2^b\)， \(n\) 是二進制右邊皆為 0 的形式。
有 \(G(n) = \sum_{0\le j, k < n}(j \text { OR } k) = \sum_m 2^m(n^2 - Z^2(n, m))\)
我們想要計算的是對於 \(2^{b-1}\) 產生的增量，也就是 \(G(n + 2^{b-1}) - G(n)\)，當我們由高至低確定第 b - 1 位是否會超過限制 s ，若是不超過則 \(n = n + 2^{b-1}\) 不斷逼近 s。
由上面的 \(G(n)\) 可以知道，\(G(n + 2^{b-1}) = \sum_{m}2^m((n+2^{b-1})^2 - Z^2(n+2^{b-1},m))\)，此時需要關注的點是 \(Z(n+2^{b-1},m)\)，要考慮的是 \(Z(n+2^{b-1},m)\) 與 \(Z(n+2,m)\) 的關係變化。
我們要考慮的是四種情況:
1) \(0 \le m < b - 1\)
由二進制的週期性可以知道 \(Z(n + 2^{b-1}, m) = \frac{n + 2^{b-1}}{2}\)
此時產生的增量為
\[ \begin{aligned} G(n + 2^{b-1}) - G(n) &= \sum_m 2^m((n+2^{b-1})^2 - Z^2(n+2^{b-1}, m)) - \sum_m 2^m(n^2 - Z^2(n, m)) \\ &= \sum_m 2^m((n+2^{b-1})^2 - Z^2(n+2^{b-1}, m) - n^2 + Z^2(n,m)) \\ &= \sum_m 2^m((n+2^{b-1})^2 - (\frac{n + 2^{b-1}}{2})^2 - n^2 + (\frac{n}{2})^2) \\ &= \frac{3}{4} \sum_m 2^m((n+2^{b-1})^2 - n^2) \\ &= \frac{3}{4} \cdot (2^{b-1} - 1) \cdot ((n+2^{b-1})^2 - n^2) \\ &= \frac{3}{4} \cdot (2^{b-1} - 1) \cdot 2^{b-1}(2 \cdot n + 2^{b-1}) \\ \end{aligned} \]可以利用等比級數和公式將式子化簡 \(\sum_{m = 0}^{b - 2} 2^m = (2^{b-1} - 1)\)
2) \(m = b - 1\)
在 \([n, n + 2^b-1)\) 上第 b - 1 位都是 0，這是 \(Z(n + 2^{b-1}, b - 1)\) 產生的增量，也就是 \(Z(n + 2^{b-1}, b - 1) = \frac{n}{2} + 2^{b-1}\)
因此增量為:
\[ \begin{aligned} G(n + 2^{b-1}) - G(n) &= \sum_m 2^m((n+2^{b-1})^2 - Z^2(n+2^{b-1}, b-1)) - \sum_m 2^m(n^2 - Z^2(n, b-1)) \\ &= \sum_m 2^m((n+2^{b-1})^2 - (\frac{n}{2} + 2^{b-1})^2) - \sum_m 2^m(n^2 - (\frac{n}{2})^2) \\ &= \sum_m 2^m((n+2^{b-1})^2 - (\frac{n}{2} + 2^{b-1})^2 - n^2 + (\frac{n}{2})^2) \\ &= \sum_m 2^m(2 \cdot n \cdot 2^{b-1} - n \cdot 2^{b-1}) \\ &= \sum_m 2^m(n \cdot 2^{b-1}) \\ &= 2^{b-1}\cdot n \cdot 2^{b-1} \\ \end{aligned} \]3) \(m \ge b, (n \text{ AND } 2^m) = 0\)
在比 b - 1 更高位時為 0 的情況，也就是在 \([n, n + 2^{b-1})\) 中為 0 的情況。對於每一位有 \(Z(n + 2^{b-1}, m) = Z(n, m) + 2^{b-1}\)，代表在 \(Z(n, m)\) 上再增加 \(2^{b-1}\)
有增量:
\[ \begin{aligned} G(n + 2^{b-1}) - G(n) &= \sum_m 2^m((n+2^{b-1})^2 - (Z(n, m) + 2^{b-1})^2) - \sum_m 2^m(n^2 - Z^2(n, m)) \\ &= \sum_m 2^m(n+2^{b-1})^2 - (Z(n, m) + 2^{b-1})^2 - n^2 + Z^2(n, m) \\ &= \sum_m 2^m(2 \cdot n \cdot 2^{b-1} + 2 \cdot Z(n, m) \cdot 2^{b-1}) \\ &= \sum_m 2^m \cdot 2^{b-1}(2n + 2Z(n, m)) \\ &= 2^{b-1} \sum_m 2^m (2n + 2Z(n, m)) \\ \end{aligned} \]設 \(ZC(n, b) = \sum_{m \ge b, n \text{ AND } 2^m = 0} 2^m (2n + 2Z(n, m))\)
最後得到:
\[G(n + 2^{b-1}) - G(n) = ZC(n, b)2^{b-1}\]4) \(m \ge b, (n \text{ AND } 2^m) = 2^m\)
在比 b - 1 更高位時為 1 的情況，也就是在 \([n, n + 2^{b-1})\) 中為 1 的情況。對於每一位有 \(Z(n + 2^{b-1}, m) = Z(n, m)\)。這個意義是對於 \(n \text{ AND } 2^m = 2^m\) 的情況 \(Z(n + 2^{b-1}, m)\) 不會有變化(\(Z\) 的定義是 0 的個數)。
此時的增量
\[ \begin{aligned} G(n + 2^{b-1}) - G(n) &= \sum_m 2^m((n+2^{b-1})^2 - Z^2(n, m)) - \sum_m 2^m(n^2 - Z^2(n, m)) \\ &= \sum_m 2^m((n+2^{b-1})^2 - n^2)\\ &= \sum_m 2^m(2 \cdot n \cdot 2^{b-1} + 2^{b-1} \cdot 2^{b-1}) \\ &= \sum_m 2^m \cdot 2^{b-1}(2 n + 2^{b-1} ) \end{aligned} \]由於我們考慮的是 \((n \text{ AND } 2^m) = 2^m\)，且此時的 n 為 \(n = a \cdot 2^b\) 的形式，所以可以得到在 \(m \ge b, (n \text{ AND } 2^m) = 2^m\) 的情況下 \(\sum_m 2^m = n\)。
因此增量為:
\[G(n + 2^{b-1}) - G(n) = n \cdot 2^{b-1}(2 n + 2^{b-1} )\]最後全部求和可以得到對於 \(n + 2^{b-1}\) 產生的增量:
\[ \begin{aligned} G(n + 2^{b-1}) - G(n) &= ZC(n, b)2^{b-1} + n \cdot 2^{b-1}(2 n + 2^{b-1} ) + 2^{b-1}\cdot n \cdot 2^{b-1} \\ &+ \frac{3}{4} \cdot (2^{b-1} - 1) \cdot 2^{b-1}(2 \cdot n + 2^{b-1}) \end{aligned} \]用 \(S = 2^{b-1}\) 簡化為:
\[ \begin{aligned} G(n + 2^{b-1}) - G(n) &= ZC(n, b)\cdot S + n \cdot S(2 n + S) + S\cdot n \cdot S \\ &+ \frac{3}{4} \cdot (S - 1) \cdot S(2 \cdot n + S) \end{aligned} \]接著要考慮的是如何維護 \(ZC(n, b)\)，因為對於 b - 1 位，有兩種可能 0 or 1，所以對於更新 \(ZC(n, b)\) 必須考慮兩種情況:
-
b - 1 位為 0 時，此時 n 不變，需要計算的是 \(ZC(n, b - 1)\)，由定義可以得到 \(ZC(n, b-1) = ZC(n, b) + 2^{b-1} (2n + 2Z(n, b-1))\)，而 \(Z(n, b-1)\) 時 b - 1 位的變化為週期性的，所以 \(Z(n, b-1) = \frac{n}{2}\)
得到 \(ZC(n, b-1) = Z(n, b) + 2^{b-1} \cdot n\)
-
b - 1 位為 1 時，n 變成 \(n + 2^{b-1}\)，需計算 \(ZC(n + 2^{b-1}, b-1)\)，可以知道對於 \(Z(n + 2^{b-1}, m)\) 此時會在 \(Z(n, m)\) 上產生 \(2^{b-1}\) 的增量
\[Z(n + 2^{b-1}, m) = Z(n, m) + 2^{b-1}\]兩邊同時取負號加上 \(n + 2^{b-1}\) 後乘 2 可以得到
\[2(n + 2^{b-1}) - Z(n + 2^{b-1}, m) = 2n + 2Z(n, m)\]也就是
\[ZC(n + 2^{b-1}, b - 1) = ZC(n, b)\]
結合上面兩種情況可以維護 \(ZC\)。
-
Logtrick¶
- 單調性
對於位元運算的時候，不妨將每個元素的位元運算看成對不同集合做運算，也就是:
由集合的角度出發，當遍歷陣列時，一旦固定右端點，不斷的往左進行 OR 運算，集合中的元素只會單調的增加，由陣列的元素值域 \([1, x]\) 可以知道集合的大小最大只會有 \(\lfloor \log{x}\rfloor\)。
若是做 AND 運算則集合的大小會單調遞減。
利用上面這個性質，我們可以將每次變化的位置記錄下來計算答案所需的部分。
由下面的圖片可以發現若是可以記錄下集合大小變化的位置，那就可以快速處理這些區間的資訊。
AND 運算會使集合大小單調遞減。
-
可以透過維護一個集合 set 由左往右遍歷陣列，為了維護陣列單調性，每次元素都要與陣列中的元素進行 OR/AND。
-
模板題:
-
Leetcode #3878. 统计好子数组
這題需要統計子陣列的個數，合法的子陣列為子陣列元素作或運算後得到的值 \(v_{or}\) 出現在子陣列中。
透過上圖可以觀察到，設右端點在 \(i\)，左端點在 \([l,r]\) 中的子陣列的 OR 都是 \(v_{or}\)。設 \(j=pre[v_{or}]\)。當 \(j \ge l\) 時，左端點為 \(l,l+1,...,min(r,j)\)，右端點為 \(i\) 的子陣列都包含 \(v_{or}\)，這一共有
\[min(r,j)−l+1\]- 原地去重要看一下。
class Solution {
public:
long long countGoodSubarrays(vector<int>& nums) {
vector<pair<int, int>> or_left; // (子数组或值，最小左端点)
unordered_map<int, int> last;
long long ans = 0;
for (int i = 0; i < nums.size(); i++) {
int x = nums[i];
last[x] = i;
// 计算以 i 为右端点的子数组或值
for (auto& [or_val, _] : or_left) {
or_val |= x; // **根据题目修改**
}
// x 单独一个数作为子数组
or_left.emplace_back(x, i);
// 原地去重（相同或值只保留最左边的）
// 原理见力扣 26. 删除有序数组中的重复项
int m = 1;
for (int j = 1; j < or_left.size(); j++) {
if (or_left[j].first != or_left[j - 1].first) {
or_left[m++] = or_left[j];
}
}
or_left.resize(m);
for (int k = 0; k < m; k++) {
auto [or_val, left] = or_left[k];
int right = k + 1 < m ? or_left[k + 1].second - 1 : i;
// 对于左端点在 [left, right]，右端点为 i 的子数组，OR 值都是 or_val
auto it = last.find(or_val);
if (it != last.end() && it->second >= left) {
ans += min(right, it->second) - left + 1;
}
}
}
return ans;
}
};
Other¶
-
Codeforces:
-
Max Sum OR (Easy Version)/(Hard Version)
觀察到對於 \([2^h, r]\) 的位元表示跟 \([l, 2^h - 1]\) 是互補的，因此可以用這個方式進行配對。
-
need to practice:
leetcode 3106. 满足距离约束且字典序最小的字符串 leetcode 3720. 大于目标字符串的最小字典序排列 leetcode 3734. 大于目标字符串的最小字典序回文排列 leetcode 3470. 全排列 IV leetcode 3022. 给定操作次数内使剩余元素的或值最小 leetcode 3518. 最小回文排列 II