题目链接
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