玲珑oj 1028 贪心

http://www.ifrog.cc/acm/problem/1028

很有趣的一道题，求从n个数里挑出不同的两个，使得他俩'|','&','^'后的值尽量大，求这个最大的结果。

求最大的异或值想到了trie树的一个经典操作，对于按位与，要两个位置都是1才会出现1，我们肯定要贪心操作，优先使高位为1，

这也可以在trie上完成，如果这个位置1的个数>=2,至少有两个以这个前缀开头的数字，我们就认为这个位置可以为1，再往下走考虑下一位，

如果1的个数不满足得话，说明这一位肯定是0了，此时要进行一步合并操作，将0下面的部分合并到1上，因为此位不必要是1所以0/1都可以。

对于'|',有点复杂我感觉，我们考虑遍历每个数字，是1得位我们就不必管了，然后从最高位的0开始看看是否能变为1.

例如，对于1000(2),我们首先找有没有x100(2)，如果有再找x110(2),高位如果找不到了就找低位，最后得到的就是最大值，

我们预处理出每个数能拆出来的数，1001->1000,0001,1001。。。依次类推，用一个标记数组。

之后循环每一个数的时候，记录由高位到低位'0'出现的位置，之后贪心高位找到最大的，只要标记过这个数就表示可以进行或操作。

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 int num[35],a[100005];
  4 int ch[2100005][2],cnt[2100005],sz;
  5 void irt(int x)
  6 {
  7     int p=0;
  8     for(int i=20;i>=0;--i){
  9         int bit=(x&(1<<i))?1:0;
 10         if(ch[p][bit]==-1)
 11         {
 12             ch[sz][0]=ch[sz][1]=-1;
 13             cnt[sz]=0;
 14             ch[p][bit]=sz++;
 15         }//cout<<p<<endl;
 16         p=ch[p][bit];
 17         cnt[p]++;
 18     }
 19 }
 20 void uno(int &x,int y)
 21 {
 22     if(y==-1) return;
 23     if(x==-1) {ch[sz][0]=ch[sz][1]=-1;cnt[sz]=0;x=sz++;}
 24     cnt[x]+=cnt[y];
 25     uno(ch[x][0],ch[y][0]);
 26     uno(ch[x][1],ch[y][1]);
 27 }
 28 int solve1(int n)
 29 {
 30     int p=0,ret=0;
 31     for(int i=20;i>=0;--i){
 32         if(ch[p][1]!=-1&&cnt[ch[p][1]]>=2)
 33             ret|=(1<<i);
 34         else uno(ch[p][1],ch[p][0]);
 35     p=ch[p][1];
 36     }
 37     return ret;
 38 }
 39 
 40 int solve2(int x)
 41 {
 42     int ret=0,p=0;
 43     for(int i=20;i>=0;--i){
 44         int bit=(x&(1<<i))?1:0;
 45             if(ch[p][bit^1]!=-1) {p=ch[p][bit^1];ret|=(1<<i);}
 46             else p=ch[p][bit];
 47         if(p==-1) break;
 48     }
 49     return ret;
 50 }
 51 bool dp[(1<<22)];
 52 int solve3(int n)
 53 {
 54     int i,j,ret=0;
 55     memset(dp,0,sizeof(dp));
 56     for(i=1;i<=n;++i) dp[a[i]]=1;
 57     for(i=(1<<20);i>=0;--i)
 58     {
 59         for(j=20;j>=0;--j)
 60         {
 61             if(!(i&(1<<j))) dp[i]|=dp[i|(1<<j)];
 62         }
 63     }
 64     int t[100],p=0;
 65     for(i=1;i<=n;++i)
 66     {
 67         p=0;
 68         for(j=20;j>=0;--j)
 69             if(!(a[i]&(1<<j))) t[p++]=(1<<j);
 70         int x=0;
 71         for(j=0;j<p;++j)
 72         {
 73             if(dp[x|t[j]]) x|=t[j];
 74         }
 75         ret=max(ret,x|a[i]);
 76     }
 77     return ret;
 78 }
 79 int main()
 80 {
 81     int i,j,k,n,m,t,op;
 82 
 83    // freopen("in.txt","r",stdin);
 84      cin>>t;
 85     for(int cas=1;cas<=t;++cas)
 86     {
 87         sz=0;
 88         int xo=0;
 89         cin>>n>>op;
 90         memset(num,0,sizeof(num));
 91         ch[sz][0]=ch[sz++][1]=-1;cnt[0]=0;
 92         for(i=1;i<=n;++i)
 93         {
 94             scanf("%d",a+i);
 95             if(op==2) xo=max(xo,solve2(a[i]));
 96             irt(a[i]);
 97         }
 98         printf("Case #%d: ",cas);
 99         switch(op){
100         case 1:cout<<solve1(n)<<endl;break;
101         case 2:cout<<xo<<endl;break;
102         case 3:cout<<solve3(n)<<endl;break;
103         }
104     }
105     return 0;
106 }