trie树好题
主要是利用前缀异或
要注意的是首先要插入0
#include <bits/stdc++.h> typedef long long ll ; using namespace std; const int maxn = 1e5+7; struct node{ node*ch[2]; int v; node() {v = 0;ch[0] = ch[1] = NULL;} }; node*root,*rt; int k; ll ans; void insert(int n){ rt=root; for(int level=20;level>=0;level--){ int id=(n>>level)&1; if(rt->ch[id]==NULL) rt->ch[id]=new node(); rt=rt->ch[id]; rt->v++; } } void query(node*cur,int h,int n){ int ll = (k>>h)&1; int pp = (n>>h)&1; for(int i=0;i<=1;i++){ if (cur->ch[i] == NULL) continue; if((i^pp)<ll) ans+=cur->ch[i]->v; if((i^pp)==ll) query(cur->ch[i],h-1,n); } } int n; int val[maxn]; int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&val[i]); int v=0; ans=0; root=new node(); insert(0); for(int i=1;i<=n;i++){ v=v^val[i]; query(root,20,v); insert(v); } printf("%lld\n",ans); } return 0; }另一份代码 主要是修改了询问部分 然后时间少了三分之一。。。。
#include <bits/stdc++.h> typedef long long ll ; using namespace std; const int maxn = 1e5+7; struct node { node*ch[2]; int v; node() { v = 0; ch[0] = ch[1] = NULL; } }; node*root,*rt; int k; void insert(int n) { rt=root; for(int level=20;level>=0;level--){ int id=(n>>level)&1; if(rt->ch[id]==NULL) rt->ch[id]=new node(); rt=rt->ch[id]; rt->v++; } } int query(int n) { rt=root; int ans=0; for(int level=20;level>=0;level--){ if(rt==NULL)break; int x=(n>>level)&1; int y=(k>>level)&1; if(y){ if(rt->ch[x]!=NULL) ans+=rt->ch[x]->v; rt=rt->ch[1-x]; } else rt=rt->ch[x]; } return ans; } int n; int val[maxn]; int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&val[i]); int v=0; ll ans=0; root=new node(); insert(0); for(int i=1;i<=n;i++){ v=v^val[i]; ans+=(ll)query(v); insert(v); } printf("%lld\n",ans); } return 0; }