CF 1457D XOR-gun

题目描述

http://codeforces.com/contest/1457/problem/D

简要题意：给定一个长度为 $n$ 的非降序列 $a_i$，每次操作可以选择两个相邻的数 $a_i$ 和 $a_{i+1}$ 然后将这两个数移除，放回 $a_i\oplus a_{i+1}$，求最少多少次操作可以使其不在是非降序列，注意 $n=1$ 时仍然认为是非降

$n\le 2\times 10^5,a_i\le 10^9$

Solution

注意到如果有连续三个数的最高位相同，则我们异或后面两个就能使得序列不合法

由于原题保证数列递增，所以相邻数的最高位至少相等

那么如果 $n>60$，答案一定为 $1$ 次

否则我们直接暴力即可

#include <iostream>
#include <cstdio>
#define maxn 100010
using namespace std;

int n, a[maxn], s[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    if (n <= 60) {
        int ans = n;
        for (int i = 1; i <= n; ++i) s[i] = s[i - 1] ^ a[i];
        for (int i = 1; i < n; ++i)
            for (int j = 1; j <= i; ++j)
                for (int k = i + 1; k <= n; ++k)
                    if ((s[i] ^ s[j - 1]) > (s[k] ^ s[i]))
                        ans = min(ans, k - j - 1);
        ans == n ? cout << "-1\n" : cout << ans << "\n";
    }
    else cout << "1\n";
    return 0;
}