8 条题解
-
0
我不理解为什么有人说一定要快读
#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
- 上传者