CF1415D XOR-gun 题解

· · 题解

首先，如果只用一次操作就能把序列变成非不降序列，那么就输出 1。

我们发现，如果存在连续的三个数，它们在二进制下的最高位是同一位（例如 (100)_2,(110)_2,(111)_2），那么对后面的两个数进行一次操作，就能使序列非不降，因为它们的最高位会相互抵消掉（(110)_2\oplus(111)_2=(001)_2，(100)_2>(001)_2）。

所以，如果只用一次操作行不通的话，那么对于每个二进制位，以它为最高位的数最多只有 2 个。由于最多只有 30 个二进制位，所以此时 n\le 60，暴力即可。

（同样地，若 n>60，那么一定可以只用一次操作就使序列非不降。）

暴力时，先对序列做一遍前缀异或和。由于要操作的一定是相邻的两个区间内的所有数，所以我们枚举断点，答案取最小值即可。注意特判无解的情况。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,a[100005],x,y,ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",a+i);
    for(int i=1;i<=n-2;++i){
        x=a[i]^a[i+1];
        if(x<a[i-1] || x>a[i+2]){
            printf("1\n");
            return 0;
        }
    }
    for(int i=1;i<=n;++i)a[i]^=a[i-1];
    ans=n;
    for(int i=1;i<=n;++i){
        for(int j=i+1;j<=n;++j){
            for(int k=i;k<j;++k){
                x=a[k]^a[i-1];
                y=a[j]^a[k];
                if(x>y)ans=min(ans,j-i-1);
            }
        }
    }
    printf("%d\n",ans<n?ans:-1);
    return 0;
}