本文主要是介绍中国石油大学 Chip Factory(字典树处理异或最大值)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
9264: Chip Factory
时间限制: 5 Sec 内存限制: 128 MB
提交: 268 解决: 61
[提交] [状态] [讨论版] [命题人:admin]
题目描述
John is a manager of a CPU chip factory, the factory produces lots of chips everyday. To manage large amounts of products, every processor has a serial number. More specifically, the factory produces n chips today, the i-th chip
produced this day has a serial number si.
At the end of the day, he packages all the chips produced this day, and send it to wholesalers. More specially, he writes a checksum number on the package, this checksum is defined as below:
which i, j, k are three different integers between 1 and n. And 
is symbol of bitwise XOR.
Can you help John calculate the checksum number of today?
输入
The first line of input contains an integer T indicating the total number of test cases.
The first line of each test case is an integer n, indicating the number of chips produced today. The next line has n integers s1 , s2 ,..., sn , separated with single space, indicating serial number of each chip.
- 1≤T≤1000
- 3≤n≤1000
- 0≤s i≤109
- There are at most 10 testcases with n > 100
输出
For each test case, please output an integer indicating the checksum number in a line.
样例输入
2 3 1 2 3 3 100 200 300
样例输出
6 400
来源/分类
ICPC 2015 Changchun
题意:给出n个数,求其中不同的i,j,k使得(ai+aj)^ak的值最大,输出最大值.
题解:第一次见到这种处理方式是在CF中,当时还感觉是个很骚的操作,现在发现这居然是基本操作.....
可以将每个数字的二进制构造字典树,那么对于一个数查找最大值,它的每一位二进制就是一层,若它这一位是0,那么你就要在字典树的这一层查找1,若这一位是1,那么你就要查找0(查找到0这个数不会变化,查找到1则会变大或变小),因为i,j,k不能相同,所以每次查找枚举i,j就要在字典树中把这两个数字删去,然后再添加上。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;ll a[maxn];
int tire[maxn][2],tot,sz[maxn];void ins(ll x)
{int rt=1;sz[rt]++;for(ll i=30;i>=0;i--){int u=x&(1<<i)? 1:0;if(!tire[rt][u]) tire[rt][u]=++tot;rt=tire[rt][u];sz[rt]++;}
}void del(ll x)
{int rt=1;sz[rt]--;for(ll i=30;i>=0;i--){int u=x&(1<<i)? 1:0;rt=tire[rt][u];sz[rt]--;}
}ll find(ll x)
{int rt=1;for(ll i=30;i>=0;i--){int u=x&(1<<i)?1:0;if(u){if( tire[rt][0] && sz[ tire[rt][0] ] )rt=tire[rt][0];elsert=tire[rt][1],x^=(1<<i);}else{if( tire[rt][1] && sz[ tire[rt][1] ] )rt=tire[rt][1],x^=(1<<i);elsert=tire[rt][0];}}return x;
}int main()
{int T;scanf("%d",&T);while(T--){memset(tire,0,sizeof(tire));memset(sz,0,sizeof(sz));tot=1;int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);ins(a[i]);}ll ans=0;for(int i=1;i<=n;i++){del(a[i]);for(int j=i+1;j<=n;j++){del(a[j]);ans=max(ans,find(a[i]+a[j]));ins(a[j]);}ins(a[i]);}printf("%lld\n",ans);}return 0;
}
这篇关于中国石油大学 Chip Factory(字典树处理异或最大值)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
