CF1415D XOR-gun 題解 二分答案/貪心

題目連結

​​https://codeforces.com/problemset/problem/1415/D​​

題目大意

給定一個長為 \(n\) 的不降序列，每次操作可以任選相鄰的兩個數，并将這兩個數替換為兩個數按位異或的結果，現在需要破壞序列的不降，求最少操作次數，無解輸出 \(-1\)。

方法一：二分答案

首先，要破壞數列的非嚴格單調遞增特性，肯定會選擇兩個連續的元素 \(a_i\) 和 \(a_{i+1}\)，然後：

• 選擇将 \(a_i\) 結尾的連續若幹個元素（\(\ldots, a_{i-2}, a_{i-1}, a_i\)）進行異或；
• 選擇将 \(a_{i+1}\) 開頭的連續若幹個元素（\(a_{i+1}, a_{i+2}, \ldots\)）進行異或

并令 前者（以 \(a_i\) 結尾的連續若幹個數的異或和）大于 後者（以 \(a_{i+1}\)

為什麼操作連續的若幹個數？

舉個形象一點的例子，這個就跟伐木一樣，比如說我要砍倒一棵樹，我肯定會選擇同一個高度砍，不會說先在距離地面 \(0.2\) 米的位置砍兩刀，然後再到距離地面 \(0.5\)

因為我們的目的是破壞數列“非嚴格單調遞增“的性質，是以我們隻需要存在一對元素滿足條件即可，很明顯：

1. 它們是相鄰的
2. 左邊的那個數是一段連續的元素的異或和（對應以某個 \(a_i\)
3. 右邊的那個數也是一段連續的元素的異或和（對應以 \(a_{i+1}\)

考慮可以操作 \(m\) 次時是否滿足條件（破壞數列的“非嚴格單調遞增“性質），因為要将一段連續的區間内的元素消到隻剩 \(2\) 個數（然後左邊那個數大于右邊那個數），操作一次會消去一個數，是以 \(m\) 次操作對應一個長度為 \(m+2\)

當 \(m\) 确定時，枚舉每個下标 \(i\)，對于下标 \(i\)，我們要确定的事情是：

是否存在一個以 \(a_i\) 結尾的連續子序列（假設這個連續子序列的異或和為 \(x\)）以及一個以 \(a_{i+1}\) 開頭的連續子序列（假設這個連續子序列的異或和為 \(y\)），滿足 \(x \gt y\) 且兩個連續子序列包含的元素個數不超過 \(m+2\)。

如果有的話就說明 \(\Rightarrow\) 消除不超過 \(m\)

注意：是 ”不超過 \(m\) 而不是 ”恰好 \(m\)。

這是為什麼呢？我們多定義兩個狀态 \(b_j\) 和 \(c_j\)，這兩個狀态在 \(j \le i\) 和 \(j \gt i\)

當 \(j \le i\)

\(b_j\) 表示的是 \(a_j \oplus a_{j+1} \oplus \ldots a_i\)（即以 \(a_j\) 開頭以 \(a_i\)

\[b_j = \begin{cases}

a_i & j = i \\

a_j \oplus b_{j+1} & j \lt i

\end{cases}

\]

\(c_j\) 表示的是 \(b_j, b_{j+1}, \ldots, b_i\)

\[c_j = \begin{cases}

b_i & j = i \\

\max\{ b_j, c_{j+1} \} & j \lt i

\end{cases}

\]

此時的狀态是從後往前推（\(i \rightarrow i-1 \rightarrow i-2 \rightarrow \ldots\)），可以發現 \(c_j\) 從後往前是非降的，因為 \(c_j\) 表示的并不是從 \(a_i\) 異或到 \(a_j\) 的結果（這是 \(b_j\) 表示的），而是從 \(a_i\) 異或到 \(a_j\)

也就是說，\(c_j\) 表示的含義是 \(a_i\) 往前合并 不超過 \(i - j\)

當 \(j \gt i\)

\(b_j\) 表示的是 \(a_{i+1} \oplus a_{i+2} \oplus \ldots a_j\)（即以 \(a_i\) 開頭以 \(a_j\)

\[b_j = \begin{cases}

a_{i+1} & j = i+1 \\

a_j \oplus b_{j-1} & j \gt i+1

\end{cases}

\]

\(c_j\) 表示的是 \(b_{i+1}, b_{i+2}, \ldots, b_j\)

\[c_j = \begin{cases}

b_{i+1} & j = i+1 \\

\min\{ b_j, c_{j-1} \} & j \gt i+1

\end{cases}

\]

（注意，差別于 \(j \le i\) 的情況，這裡 \(c_j\)

此時的狀态是從前往後推（\(i+1 \rightarrow i+2 \rightarrow i+3 \rightarrow \ldots\)），可以發現 \(c_j\) 從前往後是非增的，因為 \(c_j\) 表示的是從 \(a_{i+1}\) 異或到 \(a_j\)

也就是說，在 \(g \gt i\) 時，\(c_j\) 表示的含義是 \(a_{i+1}\) 往後合并 不超過 \(j - i - 1\)

那麼怎麼能確定不超過 \(m\)

枚舉合并的過程中最前面那個數的下标！

以 \(a_i\) 結尾合并 \(m\) 次能合并到 \(a_{i-m}\)，是以我們從 \(\max\{ i-m, 1\}\) 到 \(i\) 枚舉下标 \(j\)，對于的下标區間範圍是 \([j, j+m+1]\) —— 注意 \(j+m+1\) 可能大于 \(n\)，所可以開一個 \(k = j+m+1\)，對于的區間範圍是 \([j, k]\)，當 \(k \gt n\) 時就不用繼續操作了（因為 \(k \gt n\) 是左邊一段變小，而右邊一段固定，繼續 \(j++\) 隻會讓左邊一段異或和的最大值變小，而右邊一段異或和的最小值是不會發生任何變換，是以繼續 \(j++\)

• \(a_i\) 能夠合并到的最左邊的數是 \(a_j\)
• \(a_{i+1}\) 能夠合并到的最右邊的數是 \(a_k\)

那麼 \(a_i\) 往左合并的過程中的最大值就是 \(c_j\)，\(a_{i+1}\) 往右合并的過程中的最小值就是 \(c_k\)。隻要 \(c_j \gt c_k\)，就說明不超過 \(m\)

對應的我可以開一個 ​

​check(int m)​

​ 函數進行判斷。

但是這種方法隻能判斷在不超過 \(m\) 次合并時能夠滿足條件，不過可以發現，當 \(m\) 大于等于我們的最小操作次數時，check 函數總會傳回 true；當 \(m\)

是以可以對 check 函數二分答案。

示例程式：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, a[maxn], b[maxn], c[maxn];

bool check(int m) {
    for (int i = 1; i < n; i++) {
        b[i] = c[i] = a[i];
        for (int j = i-1; j >= max(1, i-m); j--) {
            b[j] = a[j] ^ b[j+1];
            c[j] = max(b[j], c[j+1]);
        }
        b[i+1] = c[i+1] = a[i+1];
        for (int j = i+2; j <= min(i+m+1, n); j++) {
            b[j] = a[j] ^ b[j-1];
            c[j] = min(b[j], c[j-1]);
        }
        for (int j = max(1, i-m); j <= i && j+m+1 <= n; j++)
            if (c[j] > c[j+m+1])
                return true;
    }
    return false;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int l = 0, r = n-2, res = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) res = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << res << endl;
    return 0;
}      

方法二：貪心思想+枚舉答案

上面二分答案的解法雖然能通過，但是分析一下，由于 ​

​check(m)​

​ 的時間複雜度是 \(O(n \cdot m)\) 的，\(m\) 接近 \(n\)，是以總的時間複雜度是 \(O(n^2 \log n)\)

1. 當 \(n\)
2. 題目的 \(n\)
3. 或者别的原因（歡迎評論區補充）

可以發現，因為 \(1 \le a_i \le 10^9\)，是以 \(a_i\) 的二進制表示最多 \(30\) 位，而數列是非嚴格單調遞增的，是以根據鴿籠/雀巢/抽屜原理，當 \(n \gt 60\) 時，必然存在連續的三個數 —— 假設這三個數是 \(a_i, a_{i+1}, a_{i+2}\) —— 的最高位的位數是相同的，此時将後兩個數（即 \(a_{i+1}\) 和 \(a_{i+2}\)）異或能夠消去最高位的 \(1\)，此時 \(a_i \gt a_{i+1} \oplus a_{i+2}\)（注意：本題中 \(a_i \ge 1\)，若 \(a_i\) 可以取 \(0\) 那還需要考慮排除 \(0\) 的影響），即：當 \(n \gt 60\) 時，答案為 \(1\)。

而當 \(n \le 60\)

也就是說，在題目裡面可以加一行

if (n > 60) {
    cout << 1 << endl;
    return 0;
}