8 条题解

  • 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;
    }
    

    信息

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