Codeforces Round #687 (Div. 2, based on Technocup 2021 Elimination Round 2) D. XOR-gun (二进制,异或,前缀和)

• 题意:给你一组非递减的数,你可以对两个连续的数进行异或,使其合并为一个数,问最少操作多少次使得这组数不满足非递减.
• 题解:首先,给出的这组数是非递减的,我们考虑二进制,对于三个连续的非递减的最高位相同的数,我们可以将后面的两个异或,那么第一个数一定比合并的数大,所以当出现三个最高位相同的数时,操作数一定是\(1\),题目所给的\(a_i\)的最大值是\(1e9\),所以最多是\(2^{30}\),也就对应着\(30\)个最高位的情况,而当出现三个最高位相同的情况时操作数为\(1\),所以每个最高位的情况最多只能有\(2\)种,也就是\(n\)最多有\(59\)个(\(1\)的最高位对应的情况只有一种),所以当\(n\ge 60\)的时候我们直接输出\(1\)即可,否则可以用前缀和记录异或情况然后\(O(n^4)\)暴力枚举所有情况求最小值.
• 代码:

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
 
int n;
int a[N],pre[N];
 
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
 
	rep(i,1,n){
		cin>>a[i];
		pre[i]=a[i];
	}
 
	if(n>=60) {cout<<1<<‘\n‘;return 0;}
 
	rep(i,2,n) pre[i]=pre[i-1]^a[i];
 
	int ans=INF;
 
	rep(i,1,n){
		rep(j,i,n){
			rep(k,j+1,n){
				rep(p,k,n){
					if((pre[j]^pre[i-1])>(pre[p]^pre[k-1])){
						ans=min(ans,j-i+p-k);
					}
				}
			}
		}
	}
	if(ans==INF) ans=-1;	
	cout<<ans<<‘\n‘;
	
    return 0;
}

Codeforces Round #687 (Div. 2, based on Technocup 2021 Elimination Round 2) D. XOR-gun (二进制,异或,前缀和)

原文：https://www.cnblogs.com/lr599909928/p/14059174.html