思维题

这题有个小陷阱，比赛时掉进去了。过了pretest但是没能Accept
首先，最小的次数肯定就是1
既然是异或，那么我们很容易就会按照位进行思考。
我们想想，如果最高位为i的数字，总数超过3个。那么我们是不是一定能在1此操作中干掉这个数组。能的，对后两个进行异或，然后与前面的一个比较，一定小于前面的一个。

这是关键，因为通过这个方法，我们排除了大量的数据。
也就是说，经过这一步的筛选，最终剩下来的最多也只有64个数。
这就允许我们使用一些相对暴力的算法去解决了。
下面有一个结论：
如果我们操作了k此，那么这k次一定都是合并一个连续的区间。
为什么这样说呢？
假设k == 4 数组：
[a1,a2,a3,a4,a5,a6,a7]
如果我们将其分开a2,a3合并得num1 a6,a7合并得num2
num1 > num2 发现递减！！！
但是哈，注意了如果只有num1>num2的话
那么num1<=a4<=a5
则a5>num2
既然如此，我们只要枚举开始的索引，和异或的数量。然后向两边比较就可以了。

我很兴奋，我觉得自己找到了真相！！
但是我被fst了！！！！！！悲剧！悲剧！

我们上面的那个结论其实并不正确。
观看证明。如果合并的不是a2,a3 和 a6,a7而是a2,a3和a4,a5呢
情况大不相同。在种种情况下，因为没有中间元素所以他们是可行的。是有可能性成功的！

我们需要在枚举一层。。。。。。

惨痛的教训。

冷静的分析，清晰的头脑，加上大局观。这题我觉得很好。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int max_n = 1e5+100;
int a[max_n];
int b[max_n];
int c[max_n];
vector<int> cct[100];
int n;
int yh(int l,int r){
    return c[l]^c[r+1];
}
int get(int num){
    int ans = 0;
    while (num){
        ++ans;
        num>>=1;
    }return ans;
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;++i)scanf("%d",&a[i]);
    if (n==2){
        printf("-1\n");
        return 0;
    }
    for (int i=n;i>=1;--i)c[i] = c[i+1]^a[i];
    for (int i=1;i<n;++i){
        int tmp = a[i]^a[i+1];
        if (i!=1&&tmp<a[i-1]){
            printf("1\n");
            return 0;
        }
        if (i+2<=n&&tmp>a[i+2]){
            printf("1\n");
            return 0;
        }
    }
    for (int i=1;i<=n;++i){
        b[i]=get(a[i]);
        cct[b[i]].push_back(i);
    }
    for (int i=1;i<=32;++i){
        if (cct[i].size()>=3){
            printf("1\n");
            return 0;
        }
    }
    int res = 1e5+100;
    bool f = true;
    for (int i=1;i<n;++i){
        if (!f)break;
        for (int j=1;j<=n;++j){
            int l = j;int r = j+i;
            if (r>n)break;
            int tmp = yh(l,r);
            if (l!=1&&tmp<a[l-1]){
                res = i;
                f = false;
                break;
            }
            if (r!=n&&tmp>a[r+1]){
                res = i;
                f = false;
                break;
            }
            if (r==n)continue;
            for (int k = l+1;k+1<=r;++k){
                if (yh(l,k)>yh(k+1,r+1)){
                    res = i;
                    f=false;
                    break;
                }
            }
            if (!f)break;
        }
    }
    if (res==1e5+100)printf("-1\n");
    else printf("%d\n",res);
}