D. XOR-gun

给出一个长度为 n 非递减的序列 a，可以执行操作

选择两个相邻的数字将他们删去，并在此位置添加他们的异或和。

问最少需要多少次操作使序列不是非递减的?2≤n≤10⁵,1≤ai≤10⁹

 

我们发现一旦出现n>60的，一定出现某三个数的最高位相同，那么使得前两个数xor 得到结果

否则，暴力枚举区间左端点，右端点，中间点。

区间异或使用区间异或出来的前缀和，因为a xor a = 0

#include<bits/stdc++.h>
#define ll long long 
#define inf 1e17
using namespace std;
const int N=1e5+5;
int a[N],sum[N],ans=n+1;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]^a[i];
    }
    if(n>60){
        printf("1
");
        return 0;
    }
    for(int i=1;i<=n;i++)
        for(int j=i+2;j<=n;j++)
            for(int k=i;k<j;k++)
                if(sum[k]^sum[i-1]>sum[j]^sum[k])    
                    ans=min(ans,j-i-1);
    printf("%d
",ans==n+1?-1:ans);
    return 0;
}