xor 2016 国庆集训day3

题目：给出 n 个数 a 1 ..a n ，求 a i xor a j , (i不等于j) 的最大值

          • 对于 30% 的数据，n ≤ 1000。

            • 对于另外 20% 的数据，数据保证最后的 ans 一定是 2^k − 1。 

            • 对于 70% 的数据，n ≤ 10 ^5 ，0 ≤ a i ≤ 10 ^7 。 

            • 对于 100% 的数据，n ≤ 10 ^5 ，0 ≤ a i ≤ 10 ^16 。

第一次打字典树。。。 

把每个数转化二进制建树，树的第i层就是二进制的第i位， 每个节点有两个孩子，分别表示该位上0与1是否存在。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
long long n,i,j,a[100005],ans,b[5600005][2],u,v,s,t;
int main()
{ scanf("%lld",&n);ans=0;for (i=1;i<=n;i++) { scanf("%lld",&a[i]);for (j=55;j>=0;j--)  //10^16大概55位{ v=(a[i]>>j)&1;if (b[u][v]==0) b[u][v]=++t;    //若当前位还不存在则新延伸一个节点，新节点编号为tu=b[u][v]; //并且走到新的节点}u=0;}for (i=1;i<=n;i++)  //每个数都找一遍{ s=0;u=0;for (j=55;j>=0;j--){ v=(a[i]>>j)&1;if (!b[u][v^1]) u=b[u][v];  //若与当前位相反的节点不存在，只能走走当前位else{ u=b[u][v^1];  //否则走到与当前位相反的节点s|=(1ll<<j);  //此时第j位上值为1 计入答案}}ans=std::max(ans,s);}printf("%lld",ans);
}

xor 2016 国庆集训day3

题目：给出 n 个数 a 1 ..a n ，求 a i xor a j , (i不等于j) 的最大值

          • 对于 30% 的数据，n ≤ 1000。

            • 对于另外 20% 的数据，数据保证最后的 ans 一定是 2^k − 1。 

            • 对于 70% 的数据，n ≤ 10 ^5 ，0 ≤ a i ≤ 10 ^7 。 

            • 对于 100% 的数据，n ≤ 10 ^5 ，0 ≤ a i ≤ 10 ^16 。

第一次打字典树。。。 

把每个数转化二进制建树，树的第i层就是二进制的第i位， 每个节点有两个孩子，分别表示该位上0与1是否存在。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
long long n,i,j,a[100005],ans,b[5600005][2],u,v,s,t;
int main()
{ scanf("%lld",&n);ans=0;for (i=1;i<=n;i++) { scanf("%lld",&a[i]);for (j=55;j>=0;j--)  //10^16大概55位{ v=(a[i]>>j)&1;if (b[u][v]==0) b[u][v]=++t;    //若当前位还不存在则新延伸一个节点，新节点编号为tu=b[u][v]; //并且走到新的节点}u=0;}for (i=1;i<=n;i++)  //每个数都找一遍{ s=0;u=0;for (j=55;j>=0;j--){ v=(a[i]>>j)&1;if (!b[u][v^1]) u=b[u][v];  //若与当前位相反的节点不存在，只能走走当前位else{ u=b[u][v^1];  //否则走到与当前位相反的节点s|=(1ll<<j);  //此时第j位上值为1 计入答案}}ans=std::max(ans,s);}printf("%lld",ans);
}