Chip Factory
Time Limit: 18000/9000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 3702 Accepted Submission(s): 1622
Problem Description
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?
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:
maxi,j,k(si+sj)⊕sk
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?
Input
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≤si≤109
There are at most 10 testcases with n>100
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≤si≤109
There are at most 10 testcases with n>100
Output
For each test case, please output an integer indicating the checksum number in a line.
Sample Input
2
3
1 2 3
3
100 200 300
Sample Output
6
400
Source
- 题中存在XOR运算，往二进制运算考虑
- 好吧，这题时间宽泛，n3复杂度8000ms可以过
- 考虑对于一个正整数的二进制形式的01字串A
- 如果用01字串B和A做XOR运算，考虑最优情况，应该是对应位置Ai!=Bi
- 那么如果我们n2枚举Si+Sj，接下来如果有一个可以反映剩下数的每个位置01状态的数据结构，我们就可以贪心地在每一步挑选最优策略
- 原始的十进制整数下的整数状态是不可能的，但是我们可以以二进制的形式对原始整数做tire就可以达到对剩余整数的一个数据压缩的效果
- 方法出来了，就是做二进制字典树，然后n2枚举和，贪心搜索tire
- 这里对于tire的建立最好是从高位开始建，原因嘛，恩本鶸从低位建树WA了，改成高位建树就AC了
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 #include <climits> 7 #include <cmath> 8 #include <vector> 9 #include <queue> 10 #include <stack> 11 #include <set> 12 #include <map> 13 using namespace std; 14 typedef long long LL ; 15 typedef unsigned long long ULL ; 16 const int maxn = 1e6 + 10 ; 17 const int inf = 0x3f3f3f3f ; 18 const int npos = -1 ; 19 const int mod = 1e9 + 7 ; 20 const int mxx = 100 + 5 ; 21 const double eps = 1e-6 ; 22 const double PI = acos(-1.0) ; 23 24 struct node{ 25 int cnt; 26 int go[2]; 27 LL val; 28 }; 29 node state[maxn<<2]; 30 int tot, root; 31 void add(LL w){ 32 int cur=root; 33 state[cur].cnt++; 34 for(int i=31;i>=0;i--){ 35 int k=(1<<i)&w?1:0; 36 if(!state[cur].go[k]){ 37 tot++; 38 state[cur].go[k]=tot; 39 memset(&state[tot],0,sizeof(state[tot])); 40 } 41 cur=state[cur].go[k]; 42 state[cur].cnt++; 43 } 44 state[cur].val=w; 45 } 46 void del(LL w){ 47 int cur=root; 48 state[cur].cnt--; 49 for(int i=31;i>=0;i--){ 50 int k=(1<<i)&w?1:0; 51 cur=state[cur].go[k]; 52 state[cur].cnt--; 53 } 54 } 55 LL search(LL w){ 56 int cur=root; 57 for(int i=31;i>=0;i--){ 58 int k=(1<<i)&w?1:0; 59 if(state[state[cur].go[k^1]].cnt){ 60 cur=state[cur].go[k^1]; 61 }else{ 62 cur=state[cur].go[k]; 63 } 64 } 65 return w^state[cur].val; 66 } 67 int T, n; 68 LL a[maxn], ans; 69 int main(){ 70 // freopen("in.txt","r",stdin); 71 // freopen("out.txt","w",stdout); 72 while(~scanf("%d",&T)){ 73 while(T--){ 74 root=1; 75 tot=1; 76 ans=-1LL; 77 memset(&state[0],0,sizeof(state[0])); 78 memset(&state[root],0,sizeof(state[root])); 79 scanf("%d",&n); 80 for(int i=1;i<=n;i++){ 81 scanf("%lld",&a[i]); 82 add(a[i]); 83 } 84 for(int i=1;i<=n;i++) 85 for(int j=i+1;j<=n;j++){ 86 del(a[i]); 87 del(a[j]); 88 ans=max(ans,search(a[i]+a[j])); 89 add(a[i]); 90 add(a[j]); 91 } 92 printf("%lldn",ans); 93 } 94 } 95 return 0; 96 }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
