这道题真的把我秀到了，我首先猜了一波结论，打了一个可持久化 ( ext{Trie}) 加二分的两只 (log_2) 的做法，发现不能 (PP) ，然后就一直改到比赛结束还没改过。
然后比完赛的时候改出来了，发现 (WA) (on) (51) ，心想好像比赛时改没改出来好像没什么区别啊。
然后就看了一波别人的题解，发现是一道结论题。。。
我是 (sb) 。
题解
你发现如果任意相邻的三个数中存在最高位相同，那么必然可以通过合并后两个来达到目的，也就证明了如果长度大于 (60) ，答案就必定为 (1) ，小于 (60) 的直接暴搜就可以了。
代码如下
可持久化 Trie
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N],b[N];
struct Trie
{
int now,rt[N];
struct Node{int data,son[2];}tr[N<<5];
Trie(){now=0,memset(tr,0,sizeof(tr));}
void add(int u,int v,int x)
{
for(int i=30;i>=0;--i)
{
tr[v]=tr[u],tr[v].data++;
int tmp=(bool)(x&(1<<i));
tr[v].son[tmp]=++now;
u=tr[u].son[tmp],v=tr[v].son[tmp];
}
tr[v]=tr[u],tr[v].data++;
}
int query1(int u,int v,int x)
{
int res=0;
for(int i=30;i>=0;--i)
{
int tmp=(bool)(x&(1<<i));
int data=tr[tr[v].son[tmp^1]].data-tr[tr[u].son[tmp^1]].data;
if(data) u=tr[u].son[tmp^1],v=tr[v].son[tmp^1],res+=(1<<i);
else u=tr[u].son[tmp],v=tr[v].son[tmp];
}
return res;
}
int query2(int u,int v,int x)
{
int res=0;
for(int i=30;i>=0;--i)
{
int tmp=(bool)(x&(1<<i));
int data=tr[tr[v].son[tmp]].data-tr[tr[u].son[tmp]].data;
if(data) u=tr[u].son[tmp],v=tr[v].son[tmp];
else u=tr[u].son[tmp^1],v=tr[v].son[tmp^1],res+=(1<<i);
}
return res;
}
}t;
int main()
{
cin>>n;
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) b[i]=b[i-1]^a[i];
// for(int i=1;i<=n;++i) printf("%d ",b[i]);
// printf("
");
t.rt[0]=++t.now;
for(int i=1;i<=n;++i)
{
t.rt[i]=++t.now;
t.add(t.rt[i-1],t.rt[i],b[i]);
}
int res=1e9+7;
for(int i=1;i<n;++i)
{
int l=1,r=i-1,tmp=-1;
while(l<=r)
{
int mid=(l+r)>>1;
int data=t.query1(t.rt[mid-1],t.rt[i-1],b[i]);
// printf("-------
");
// printf("%d %d
",mid,data);
if(data>a[i+1]) l=mid+1,tmp=mid;
else r=mid-1;
}
if(b[i]>a[i+1]&&tmp==-1) tmp=0;
// printf("---%d %d
",i,tmp);
if(tmp>=0) res=min(res,i-tmp-1);
}
for(int i=2;i<=n;++i)
{
int l=i+1,r=n,tmp=-1;
while(l<=r)
{
int mid=(l+r)>>1;
int data=t.query2(t.rt[i],t.rt[mid],b[i-1]);
// printf("---%d %d
",mid,data);
if(data<a[i-1]) r=mid-1,tmp=mid;
else l=mid+1;
}
if((b[n]^b[i-1])<a[i-1]&&tmp==-1) tmp=n;
// printf("%d
",tmp);
if(tmp>=0) res=min(res,tmp-i);
}
if(res>=1e9+7) printf("-1
");
else printf("%d
",res);
return 0;
}
正解
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N],b[N],res=1e9+7;
int main()
{
cin>>n;
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) b[i]=b[i-1]^a[i];
for(int i=1;i<n;++i)
{
for(int j=0;j<=32&&i-j>=1;++j)
{
for(int k=0;k<=32&&i+1+k<=n;++k)
if((b[i]^b[i-j-1])>(b[i]^b[i+1+k]))
res=min(res,j+k);
}
}
if(res>=1e9+7) printf("-1
");
else printf("%d
",res);
}