HDU6059（01字典树求异或最大值）

xiaoxiao2021-02-27 144

题意：求a中三个数ai,aj,ak,ai⊕aj<aj⊕ak（i<j<k） $题意：求a中三个数a_i,a_j,a_k,a_i\oplus a_j 这里要动态维护字典树，每当输入一个数，就更新一下字典树。最后减去i>j的情况（这里最难懂），搞了好久，算是会了，手撕代码时问题百出，还是没有学到骨子里，留下以后在复习。参看了两位大佬的博客： 大佬博客小老博客 #include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<iostream> #include<string> #include <set> using namespace std; #define ll long long #define mem(a) memset(a,0,sizeof(a)) const int eps=1e-8; const int maxn=5e7+5;//须填写 const int inf=0x3f3f3f3f; struct node { int nxt[2];//0/1树的连个节点 ll sum[2];//sum表示在这个数的前面有多少个数的前t-1位与这个数的前t-1位是不同的 int v;//v表示此处经过了多少次 void init() { sum[0]=sum[1]=0; nxt[0]=nxt[1]=-1; v=0; } }L[maxn]; int tot; ll ans,cnt[32][2]; void add(int a[],int len) { int now=0; int tmp;//当前为k的0/1值 for(int i=len-1;i>=0;i--) { tmp=a[i]; if(L[now].nxt[tmp]==-1)//如果没有访问过，向下走，然后初始化下边 { L[++tot].init();//初始化 L[now].nxt[tmp]=tot;//记录所有接的的序号 } if(L[now].nxt[tmp^1]!=-1)//如果和k本位不同的数则进行计算 { ans+=(L[L[now].nxt[tmp^1]].v*(L[L[now].nxt[tmp^1]].v-1))/2;//如果i，j本位都与k不同，则任意从中选两个,C(v,2)中选两个 ans+=(L[L[now].nxt[tmp^1]].v*(cnt[i][tmp^1]-L[L[now].nxt[tmp^1]].v)-L[now].sum[tmp^1]);//这里还不是很懂 //求的是如果本位i与j都与k不同的所有情况减去之间标记过j>i的情况，这里好绕 } L[now].sum[tmp]+=cnt[i][tmp]-L[L[now].nxt[tmp]].v;//把此处的k当做i处理，寻找不符合要求的j，并记录留用 cnt[i][tmp]++; now=L[now].nxt[tmp]; L[now].v++; } } int a[500010]; int b[40]; int main() { int kase; scanf("%d",&kase); while(kase--) { mem(a); mem(b); int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); mem(cnt); tot=ans=0; L[0].init();//此处一定要初始化这里 for(int i=1;i<=n;i++) { for(int j=0;j<30;j++)//将a中的每个数分解存入b { b[j]=a[i]>>j&1; } add(b,30); } cout<<ans<<endl; } return 0; } <script></div><div align="center"><script src="https://www.6miu.com/js/artile.js">$

转载请注明原文地址: https://www.6miu.com/read-16501.html

技术

最新回复(0)