7 条题解
-
11
标准的 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; }
-
4
楼上使用的是递归版的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; }-
SunnyYuan @ 2022-9-6 14:49:26
注意要加快读
-
-
0
#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
Melography
LV 3
@ 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
apple365_c LV 3 @ 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
#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
#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; }
baoshuo
LV 10
MOD
@ 2021-10-2 15:20:39
- 1
