CF1415D XOR-gun 题解
题目链接：CF1415D XOR-gun
题意：
给定一个长为 \(n\) 的不降序列，每次操作可以任选相邻的两个数，并将这两个数替换为两个数按位异或的结果，现在需要破坏序列的不降，求最少操作次数，无解输出 \(-1\) 。
输入格式：
The first line contains a single integer \(n\) ( \(2 \le n \le 10^5\) ) — the initial length of the array.
The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) ( \(1 \le a_i \le 10^9\) ) — the elements of the array. It is guaranteed that \(a_i \le a_{i + 1}\) for all \(1 \le i < n\) .
输出格式：
Print a single integer — the minimum number of steps needed. If there is no solution, print \(-1\) 。
也是一道结论题。
注意到如果存在连续的三个数满足他们在二进制下的最高位是同一位
那么对后面两个数进行一次操作，就能使序列被破坏。举个例子，\((100)_2,(110)_2,(111)_2\) 。
当然，如果一次不行的话，那么对于每个二进制位，以它为最高位的数最多有两个。
又因为最多有 \(\log V = 30\) 个二进制位，则 \(n\le 60\) ，直接暴力即可。
时间复杂度 \(\mathcal{O}(\max\{n,~\log^3
V\})\) （属于是强行写的）
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
int a[N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int n; cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n - 2; i++)
{
int x = a[i] ^ a[i + 1];
if(x < a[i - 1] || x > a[i + 2]) { return cout << "1\n", 0; }
}
for(int i = 1; i <= n; i++) a[i] ^= a[i - 1];
int res = n;
for(int i = 1; i <= n; i++)
for(int j = i + 1; j <= n; j++)
for(int k = i; k < j; k++) {
if((a[k] ^ a[i - 1]) > (a[j] ^ a[k])) down(res, j - i - 1);
}
cout << (res < n ? res : -1) << '\n';
return 0;
}参考文献：
