2 条题解

  • 2
    @ 2022-8-28 11:37:23
    /*****************************************
    Note:
    ******************************************/
    #include <queue>
    #include <math.h>
    #include <stack>
    #include <stdio.h>
    #include <iostream>
    #include <vector>
    #include <iomanip>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    #define LL long long
    const int N = 1e6 + 10;
    const int INF = 0x3f3f3f3f;
    int tr[N*2][2] , a[N] , idx;
    void add(int x)
    {
    	int len = 0;
    	for(int i = 30 ; ~i ; i-- )
    	{
    		int k = (x & (1 << i)) ? 1 : 0;
    		if(!tr[len][k])
    			tr[len][k] = ++idx;
    		len = tr[len][k];
    	}
    }
    int find(int x)
    {
    	int len = 0 , ans = 0;
    	for(int i = 30 ; ~i ; i-- )
    	{
    		int k = (x & (1 << i)) ? 0 : 1;
    		if(tr[len][k])
    		{
    			ans += (1 << i);
    			len = tr[len][k];
    		}
    		else 
    			len = tr[len][k^1];
    	}
    	return ans;
    }
    int main()
    {
    	int n;
    	cin >> n;
    	for(int i = 1 ; i <= n ;i ++)
    	{
    		cin >> a[i];
    		add(a[i]);
    	}
    	int maxx = 0;
    	for(int i = 1 ; i <= n ; i++)
    		maxx = max(maxx , find(a[i]) );
    	cout << maxx << endl;
    	return 0;
    }
    
    • 1
      @ 2022-8-28 11:22:14
      /*****************************************
      Note:
      ******************************************/
      #include <queue>
      #include <set>
      #include <math.h>
      #include <stack>
      #include <stdio.h>
      #include <iostream>
      #include <vector>
      #include <iomanip>
      #include <string.h>
      #include <algorithm>
      #include <cstdio>
      #include <cstring>
      using namespace std;
      #define LL long long
      const int N = 1e6 + 10;
      const int INF = 0x3f3f3f3f;
      int a[N],n,maxn;
      struct node{
      	int son[3],f;
      	node(){
      		memset(son,0,sizeof(son));
      		f=-1;
      	}
      }trie[N*2];
      int idx=0;
      void add(int x)
      {
      	int num=0;
      	for(int i=30;i>=0;i--)
      	{
      		bool y=(x>>i)&1;
      		if(!trie[num].son[y])
      			trie[num].son[y]=++idx;
      		num=trie[num].son[y];
      	}
      }
      int find(int x)
      {
      	int num=0,sum=0;
      	for(int i=30;i>=0;i--)
      	{
      		bool y=(x>>i)&1;
      		if(trie[num].son[!y])
      		{
      			sum+=((y^1)<<i);
      			num=trie[num].son[y^1];
      		}
      		else
      		{
      			sum+=(y<<i);
      			num=trie[num].son[y];
      		}
      	}
      	return x^sum;
      }
      int main()
      {
      	scanf("%d",&n);
      	for(int i=1;i<=n;i++)
      	{
      		cin>>a[i];
      		add(a[i]);
      	}
      	for(int i=1;i<=n;i++)
      		maxn=max(maxn,find(a[i]));
      	cout<<maxn;
      	return 0;
      }
      
      • 1

      信息

      ID
      391
      时间
      1000ms
      内存
      512MiB
      难度
      6
      标签
      递交数
      59
      已通过
      18
      上传者