异或区间和部分解暴力代码
2026-10-04 19:41:57
发布于：广东
5阅读
0回复
0点赞
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
const int M = 1e9 ;
int a[N],st[N];
int n,k,s,ans=1e18;
//检查当前的删除情况是否满足连续的区间异或和为0
int check(){
int sum=0;
int res=0;
for(int i=1;i<=n;i++){
if(st[i]==0){
sum^=a[i];
}
else{
res++;
if(sum!=0)return -1;
}
}
if(sum!=0)return -1;
return res;
}
void dfs(int step){
if(step==n+1){
if(check()!=-1)ans=min(ans,check());
return ;
}
//第step个数删除
st[step]=0;
dfs(step+1);
//第step个数不删除
st[step]=1;
dfs(step+1);
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dfs(1);
cout<<ans<<"\n";
}
signed main(){
freopen("Xorz.in", "r", stdin);
freopen("Xorz.out", "w", stdout);
int _=1;
// cin>>_;
while(_--){
solve();
}
}
这里空空如也
有帮助，赞一个