首页 > > 程序设计 > C/C++ >

HDU_5536_Chip Factory

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

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

max i, j, k (s i + s j) \oplus s k

Input

The first line of input contains an integer

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 }