HDU_5536_Chip Factory

2018-06-17 21:48:33来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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:
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.

1T1000
3n1000
0si109
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
2015ACM/ICPC亚洲区长春站-重现赛(感谢东北师大)
 
  • 题中存在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("%lld\n",ans);
93         }
94     }
95     return 0;
96 }

 

 

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:HDU_5533_Dancing Stars on Me

下一篇:(笔记):构造函数与析构函数