ACM: Find MaxXorSum 解题报告-字典树

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Find MaxXorSum

Time Limit:2000MS     Memory Limit:65535KB     64bit IO Format:

Description

Given n non-negative integers, you need to find two integers a and b that a xor b is maximum. xor is exclusive-or.

Input

Input starts with an integer T(T <= ) denoting the number of tests.

For each test case, the first line contains an integer n(n <= ), the next line contains a1, a2, a3, ......, an( <= ai <= );

Output

For each test case, print you answer.

Sample Input

  5

Sample Output

11

这个题目其实思路很简单，就我知道的写法有Trie树指针和静态数组两种写法，一开始写的指针用了pow函数TLE了2次，然后换位运算又TLE两次醉了。。
后面换成静态数组数组开大了RE了一次。。。哭。。。
这是AC代码：

 #include"iostream"

 #include"algorithm"

 #include"cstdio"

 #include"cmath"

 #include"cstring"

 #define MX 1400000

 #define INF 0x3f3f3f3f

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 using namespace std;

 int tree[MX][],xx;

 void BuildTrie(long long a) {

     int i=;

     int p=;

     while(<=i) {

         bool num=a&(<<i);

         if(!tree[p][num]) {        //如果节点为空

             tree[p][num]=++xx;//标记并创建新的子节点

         }

         p=tree[p][num];

         //    cout<<"YES"<<i<<"   B is:"<<num<<"\n"; //建立的Trie树的样子

         i--;

     }

 }

 long long Query(long long  a) {

     int i=,p=;

     long long ans=;

     while(<=i) {

         bool num=!(a&(<<i));  //取反查找

         if(tree[p][num]) p=tree[p][num],ans+=<<i;//如果和原来的那一为相反的存在的话，返回值就加上，并且在这个支路走

         else p = tree[p][!num];  //按照相同的顺序找

     //    cout<<"YES"<<i<<"   B is:"<<num<<"     ans is:"<<ans<<endl;   //查询时候的Trie树的样子

         i--;

     }

     return ans;

 }

 int main() {

     int T,n;

     long long a[],ans;

     scanf("%d",&T);

     while(T--) {

         ans=;

         memset(tree,,sizeof(tree));

         xx=;

         scanf("%d",&n);

         for(int i=; i<=n; i++) {

             scanf("%I64d",&a[i]);

             BuildTrie(a[i]);

         }

         //cout<<"YES1\n";

         for(int i=; i<=n; i++) {

             ans=max(ans,Query(a[i]));

         }

         //    cout<<"YES2\n";

         printf("%I64d\n",ans);

     }

     return ;

 }

这是指针的写法，感觉复杂度和上面的没啥区别，为啥就ＴＬＥ了呢？　希望有人知道给我指点下。

 #include"iostream"

 #include"algorithm"

 #include"cstdio"

 #include"cmath"

 #include"cstring"

 #define MX 110000

 #define INF 0x3f3f3f3f

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 using namespace std;

 struct Trie {

     Trie *next[];

 } root;

 void BuildTrie(int a) {

     Trie *p=&root,*q;

     int i=;

     while(i>=) {

     bool num=a&(<<i);

         if(p->next[num]==NULL) {

             q=(Trie *)malloc(sizeof(root));//申请一块新内存; //动态分配内存

             q->next[]=NULL;

             q->next[]=NULL;    //清空申请内存的所有子节点

             p->next[num]=q;        //往子节点下去继续记录字典树

             p=p->next[num];

         } else {

             p=p->next[num];

         }

     //    cout<<"YES"<<i<<"   B is:"<<num<<"\n"; //建立的Trie树的样子

         i--;

     }

 }

 long long Query(int a) {

     Trie *p=&root;

     long long ans=;

     int i=;

     while(<=i) {

         bool num=a&(<<i);

         if(p->next[!num]!=NULL) p=p->next[!num],ans+=<<(i);//如果和原来的那一为相反的存在的话，返回值就加上，并且在这个支路走

         else if(p->next[num]!=NULL) p=p->next[num];  //按照相同的顺序找

     //    cout<<"YES"<<i<<"   B is:"<<num<<"\n"<<"ans is:"<<ans<<endl;   //查询时候的Trie树的样子

         i--;

     }

     return ans;

 }

 int main() {

     int T,n,a[MX];

     long long ans;

     scanf("%d",&T);

     while(T--) {

         ans=;

         root.next[]=NULL;

         root.next[]=NULL;

         scanf("%d",&n);

         for(int i=; i<n; i++) {

             scanf("%d",&a[i]);

             BuildTrie(a[i]);

         }

         //cout<<"YES1\n";

         for(int i=; i<n; i++) {

             ans=max(ans,Query(a[i]));

         }

     //    cout<<"YES2\n";

         printf("%I64d\n",ans);

     }

     return ;

 }