首页 > 其他 > 详细

HDU 5536/ 2015长春区域 J.Chip Factory Trie

时间:2015-11-19 14:58:17      阅读:334      评论:0      收藏:0      [点我收藏+]

Chip Factory

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 s技术分享i技术分享技术分享 .

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:
max技术分享i,j,k技术分享(s技术分享i技术分享+s技术分享j技术分享)s技术分享k技术分享技术分享

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 s技术分享1技术分享,s技术分享2技术分享,..,s技术分享n技术分享技术分享 , separated with single space, indicating serial number of each chip.

1T1000技术分享
3n1000技术分享
0s技术分享i技术分享10技术分享9技术分享技术分享
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
 
题意:给你n个数,为你不同的三个下标i,j,k,其中两个之和异或第三个的最大值是多少
题解:我们枚举其中两个得和,去不同下标最大,显然就裸字典树了。
技术分享
///meek

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;


typedef long long ll;
#define mem(a) memset(a,0,sizeof(a))
#define pb push_back
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<0||ch>9){
        if(ch==-)f=-1;ch=getchar();
    }
    while(ch>=0&&ch<=9){
        x=x*10+ch-0;ch=getchar();
    }return x*f;
}
//****************************************
const int N=8005;
#define mod 10000007

#define inf 10000007
#define maxn 10000

struct Trie{
    int ch[N*8][2],siz,sum[N],word[N*8];
    void init(){mem(ch),siz=1;mem(word);}
    void insertt(int x) {
         int u=0,k=1,W=x,each[33];mem(each);
         while(x) each[k++]=x%2,x/=2;
         for(int i=32;i>=1;i--) {
            int c=each[i];
            if(!ch[u][c]) {
                ch[u][c]=siz++;
                word[ch[u][c]]++;
            }
            else {
                word[ch[u][c]]++;
            }
            u=ch[u][c];
            if(i==1)sum[u]=W;
         }
    }
    int ask(int x) {
        int u=0,each[33],k=1,WW=x,g;mem(each);
        while(x) each[k++]=x%2,x/=2;
        for(int i=32;i>=1;i--) {
            int c=each[i];if(c==1)g=0;else g=1;
            if(ch[u][g]&&word[ch[u][g]]) {
                u=ch[u][g];
            }
            else u=ch[u][c];
            if(i==1) return WW^sum[u];
        }
    }
    void dele(int x) {
         int u=0,each[33],k=1,g;mem(each);
        while(x) each[k++]=x%2,x/=2;
        for(int i=32;i>=1;i--) {
            int c=each[i];
            u=ch[u][c];
            word[u]--;
        }
    }
}trie;

int main(){
    int n,a[N],T=read();
    while(T--) {
        scanf("%d",&n);trie.init();
        for(int i=1;i<=n;i++) {
            scanf("%d",&a[i]);
            trie.insertt(a[i]);
        }int ans=0;
        for(int i=1;i<=n;i++) {
            trie.dele(a[i]);
            for(int j=i+1;j<=n;j++) {
                trie.dele(a[j]);
                ans=max(ans,trie.ask(a[i]+a[j]));
                trie.insertt(a[j]);
            }
            trie.insertt(a[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}
代码

 

HDU 5536/ 2015长春区域 J.Chip Factory Trie

原文:http://www.cnblogs.com/zxhl/p/4977514.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!