题目链接
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\) 米的位置砍几刀，…… 肯定是在同一个位置。
因为我们的目的是破坏数列“非严格单调递增“的性质，所以我们只需要存在一对元素满足条件即可，很明显：
- 它们是相邻的
- 左边的那个数是一段连续的元素的异或和（对应以某个 \(a_i\) 结尾的连续若干个数）
- 右边的那个数也是一段连续的元素的异或和（对应以 \(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 函数总会返回 false。
所以可以对 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)\) 的，之所以能过的原因最主要我觉得还是因为：
- 当 \(n\) 比较大时，答案很小
- 题目的 \(n\) 可能给的比较小
- 或者别的原因（欢迎评论区补充）
可以发现，因为 \(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;
}
来优化我们的程序。
标签：gt,XOR,int,题解,gun,异或,连续,cases,ldots From： https://www.cnblogs.com/quanjun/p/16758224.html