8 条题解

  • 11
    @ 2021-10-2 15:20:39

    标准的 01 Trie 。

    #include <bits/stdc++.h>
    
    using namespace std;
    
    int n, a[1000005], trie[10000005][2], p = 1, ans;
    
    void insert(int u, int x, int b) {
        if (!x) return;
        if (!trie[u][(x >> b) & 1]) trie[u][(x >> b) & 1] = ++p;
        insert(trie[u][(x >> b) & 1], x - (((x >> b) & 1) << b), b - 1);
    }
    
    int search(int u, int x) {
        int res = 0, t = u;
        for (int i = 30; i >= 0; i--) {
            if (!t) break;
            if (trie[t][!((x >> i) & 1)]) {
                res += 1 << i;
                t = trie[t][!((x >> i) & 1)];
            } else {
                t = trie[t][(x >> i) & 1];
            }
        }
        return res;
    }
    
    int main() {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", a + i);
            insert(1, a[i], 30);
        }
        for (int i = 0; i < n; i++) {
            ans = max(ans, search(1, a[i]));
        }
        printf("%d\n", ans);
        return 0;
    }
    

    Personal Homepage | Blog | OI Blog

  • 4
    @ 2022-9-6 14:48:36

    楼上使用的是递归版的01Trie插入。 我用的循环的方式:

    #include <bits/stdc++.h>
    #include <cstdlib>
    
    using namespace std;
    
    const int N=31000010;
    int son[N][2];
    int cnt[N];
    int idx;
    
    int read()
    {
        int x=0,f=1;
        char ch=getchar();
        while(ch<'0'||ch>'9')
        {
        	ch=getchar();
        	if(ch=='-')f=-1;
        }
        while('0'<=ch&&ch<='9')
        {
        	x=x*10+ch-'0';
        	ch=getchar();
        }
        return x*f;
    }
    
    void insert(int x)
    {
        int p=0;
        for(int i=31;i>=0;i--)
        {
            int u=x>>i&1;
            if(!son[p][u])son[p][u]=++idx;
            p=son[p][u];
        }
        cnt[p]++;
    }
    
    int n;
    int res=0x80808080;
    
    int findxor(int x)
    {
        int p=0,res=0;
        for(int i=31;i>=0;i--)
        {
            int u=x>>i&1;
            if(son[p][!u])p=son[p][!u],res+=1<<i;
            else p=son[p][u];
        }
        return res;
    }
    
    int a[N];
    
    int main()
    {
        n=read();
        for(int i=1;i<=n;i++)
        {
            a[i]=read();
            insert(a[i]);
        }
        for(int i=1;i<=n;i++)res=max(res,findxor(a[i]));
        printf("%d\n",res);
        return 0;
    }
    
  • 1
    @ 2024-11-25 21:17:52

    本蒟第二次发题解,多多包涵 AC Code:

    #include<bits/stdc++.h>
    #include<cstdlib>
    using namespace std;
    const int N=31000010;
    //son数组用于存储字典树的节点,cnt数组用于记录叶节点的个数
    int son[N][2];
    int cnt[N];
    //idx用于记录当前使用的节点编号
    int idx=0;
    /**
     *读取输入的整数,处理EOF情况
     *@return 读取的整数,如果遇到EOF则退出程序
     */
    int read(){
        int x=0,f=1;
        char ch=getchar();
        if(ch==EOF) exit(EXIT_FAILURE);
        while(ch<'0'||ch>'9'){
            if(ch=='-') f=-1;
            ch=getchar();
            if(ch==EOF) exit(EXIT_FAILURE);
        }
        while('0'<=ch&&ch<='9'){
            x=x*10+ch-'0';
            ch=getchar();
            if(ch==EOF) break;
        }
        return x*f;
    }
    /**
     *向字典树中插入一个数
     *@param x 要插入的数
     */
    void insert(int x){
        int p=0;
        for(int i=31;i>=0;i--){
            int u=(x>>i)&1;
            if(!son[p][u]) son[p][u]=++idx;
            p=son[p][u];
        }
        cnt[p]++;
    }
    /**
     *在字典树中查找与给定数最大异或的结果
     *@param x 给定的数
     *@return 与给定数最大异或的结果
     */
    int find(int x){
        int p=0,res=0;
        for(int i=31;i>=0;i--){
            int u=(x>>i)&1;
            if(son[p][!u]){
                p=son[p][!u];
                res+=1<<i;
            }
            else{
                p=son[p][u];
            }
        }
        return res;
    }
    //主函数
    int main(){
        int n=read();
        int a[N];
        for(int i=1;i<=n;i++){
            a[i]=read();
            insert(a[i]);
        }
        int res=0x80808080;
        for(int i=1;i<=n;i++){
            res=max(res,find(a[i]));
        }
        printf("%d\n",res);
        return 0;
    }
    

    原创不易,切勿抄袭

    • 0
      @ 2024-6-23 8:27:14
      #include <bits/stdc++.h>
      using namespace std;
      
      int n, a[1000005], t[10000005][2], p = 1, ans;
      
      void insert(int u, int x, int b) {
          if (!x) return;
          int j = (x >> b) & 1;
          if (!t[u][j]) t[u][j] = ++p;
          insert(t[u][j], x - (j << b), b - 1);
      }
      
      int search(int u, int x) {
          int res = 0;
          for (int i = 30; i >= 0; i--) {
              if (!u) break;
              int j = (x >> i) & 1;
              t[u][!j] ? res += 1 << i, u = t[u][!j] : u = t[u][j];
          }
          return res;
      }
      
      int main() {
          cin >> n;
          for (int i = 0; i < n; i++) scanf("%d", &a[i]), insert(1, a[i], 30);
          for (int i = 0; i < n; i++) ans = max(ans, search(1, a[i]));
          cout << ans;
          return 0;
      }
      
      • 0
        @ 2024-2-16 17:09:49

        我不理解为什么有人说一定要快读

        #include<vector>
        #include<cstdio>
        #include<limits>
        
        
        class Trie
        {
        	public:
        		typedef std::size_t NodeId;
        		static constexpr NodeId NIL=static_cast<NodeId>(-1);
        	private:
        		struct TrieNode
        		{
        			NodeId zero;
        			NodeId one;
        			inline constexpr TrieNode():zero(NIL),one(NIL){}
        		};
        		
        		std::vector<TrieNode> child;
        		
        	public:
        		inline Trie():child(1ull){}
        		
        		bool hasChild(NodeId parent,bool childValue){
        			if(childValue && child.at(parent).one==NIL) return false;
        			else if(!childValue && child.at(parent).zero==NIL) return false;
        			else return true;
        		}
        		
        		NodeId getChild(NodeId parent,bool childValue){
        			if(childValue) return child.at(parent).one;
        			else return child.at(parent).zero;
        		}
        		
        		void insertNode(NodeId parent,bool childValue){
        			if(childValue && child.at(parent).one==NIL){
        				child.at(parent).one=child.size();
        				child.emplace_back();
        			}else if(!childValue && child.at(parent).zero==NIL){
        				child.at(parent).zero=child.size();
        				child.emplace_back();
        			}
        		}
        		
        		static inline constexpr NodeId getRootId(){
        			return 0ull;
        		}
        		
        		void insertNumber(int x){
        			int u=this->getRootId();
        			for(int i=31;i>=0;i--){
        				bool bit=static_cast<bool>((x>>i)&1);
        				this->insertNode(u,bit);
        				u=this->getChild(u,bit);
        			}
        		}
        		
        		int findXor(int x){
        			int u=this->getRootId(),res=0;
        			for(int i=31;i>=0;i--){
        				if(u==NIL) u=0;
        				bool bit=static_cast<bool>((x>>i)&1);
        				if(this->hasChild(u,!bit)){
        					u=this->getChild(u,!bit);
        					res+=1<<i;
        				}else{
        					u=this->getChild(u,bit);
        				}
        			}
        			return res;
        		}
        };
        
        
        int main(){
        	int n,ans=std::numeric_limits<int>::min();
        	scanf("%d",&n);
        	int *a=new int[n];
        	Trie* tr=new Trie;
        	for(int i=0;i<n;i++){
        		scanf("%d",a+i);
        		tr->insertNumber(a[i]);
        	}
        	for(int i=0;i<n;i++){
        		ans=std::max(ans,tr->findXor(a[i]));
        	}
        	printf("%d",ans);
        	delete tr;
        	delete []a;
        	return 0;
        }
        
        • 0
          @ 2023-10-11 20:03:41
          #include <bits/stdc++.h>
          #include <cstdlib>
          
          using namespace std;
          
          const int N=31000010;
          int son[N][2];
          int cnt[N];
          int idx;
          
          int read()
          {
          int x=0,f=1;
          char ch=getchar();
          while(ch<'0'||ch>'9')
          {
          ch=getchar();
          if(ch=='-')f=-1;
          }
          while('0'<=ch&&ch<='9')
          {
          x=x*10+ch-'0';
          ch=getchar();
          }
          return x*f;
          }
          
          void insert(int x)
          {
          int p=0;
          for(int i=31;i>=0;i--)
          {
          int u=x>>i&1;
          if(!son[p][u])son[p][u]=++idx;
          p=son[p][u];
          }
          cnt[p]++;
          }
          
          int n;
          int res=0x80808080;
          
          int findxor(int x)
          {
          int p=0,res=0;
          for(int i=31;i>=0;i--)
          {
          int u=x>>i&1;
          if(son[p][!u])p=son[p][!u],res+=1<<i;
          else p=son[p][u];
          }
          return res;
          }
          
          int a[N];
          
          int main()
          {
          n=read();
          for(int i=1;i<=n;i++)
          {
          a[i]=read();
          insert(a[i]);
          }
          for(int i=1;i<=n;i++)res=max(res,findxor(a[i]));
          printf("%d\n",res);
          return 0;
          }
          

          基础的 $\tt 01Trie

          • 0
            @ 2023-7-7 16:32:00
            #include <iostream>
            
            using namespace std;
            int rec[10000005][2];
            
            int main() {
                ios::sync_with_stdio(false);
                cin.tie(nullptr);
                int amount, n;
                int cnt = 0;
                cin >> amount;
            
                int result = 0;
                for (int i = 0; i < amount; i++) {
                    cin >> n;
                    int insert_p = 0;
                    int search_p = 0;
                    int val = 0;
                    int bits = 30;
                    while (bits >= 0) {
                        int head = n >> bits & 1;
                        if (rec[insert_p][head] == 0) {
                            rec[insert_p][head] = ++cnt;
                        }
                        insert_p = rec[insert_p][head];
            
                        if (rec[search_p][1 - head] != 0) {
                            search_p = rec[search_p][1 - head];
                            val += 1 << bits;
                        } else {
                            search_p = rec[search_p][head];
                        }
                        bits--;
                    }
                    if (val > result) { result = val; }
                }
            
                cout << result;
                return 0;
            }
            

            insert 和 search 可以一个循环一起完成

            • -1
              @ 2024-8-20 11:18:12
              #include <bits/stdc++.h>
              using namespace std;
              
              int n, a[1000005], trie[10000005][2], p = 1, ans;
              
              void insert(int u, int x, int b) {
                  if (!x) return;
                  if (!trie[u][(x >> b) & 1]) trie[u][(x >> b) & 1] = ++p;
                  insert(trie[u][(x >> b) & 1], x - (((x >> b) & 1) << b), b - 1);
              }
              
              int search(int u, int x) {
                  int res = 0, t = u;
                  for (int i = 30; i >= 0; i--) {
                      if (!t) break;
                      if (trie[t][!((x >> i) & 1)]) {
                          res += 1 << i;
                          t = trie[t][!((x >> i) & 1)];
                      } else {
                          t = trie[t][(x >> i) & 1];
                      }
                  }
                  return res;
              }
              
              int main() {
                  scanf("%d", &n);
                  for (int i = 0; i < n; i++) {
                      scanf("%d", a + i);
                      insert(1, a[i], 30);
                  }
                  for (int i = 0; i < n; i++) {
                      ans = max(ans, search(1, a[i]));
                  }
                  printf("%d\n", ans);
                  return 0;
              }
              
              • 1

              信息

              ID
              94
              时间
              1000ms
              内存
              256MiB
              难度
              4
              标签
              递交数
              740
              已通过
              174
              上传者