数据结构_Trie
用于高效存储字符串的数据结构-Trie(字典树)
代码模板
void insert(char s[]) { int p = 0; for(int i = 0; s[i]; i++){ int u = s[i] - ‘a‘; if(!sons[p][u]) sons[p][u] = ++idx; p = sons[p][u]; } ++cnt[p]; // 记录以该点结束的单词的个数 } int query(char s[]) { int p = 0; for(int i = 0; s[i]; i++) { int u = s[i] - ‘a‘; if(!sons[p][u]) return 0; p = sons[p][u]; } return cnt[p]; }
trie的拓展应用: 存储二进制信息
在给定的N个整数A1,A2……AN中选出两个进行xor(异或)运算,得出最大结果
异或运算:两者相同为0, 反之为1
暴力做法
void solve() { for(int i = 0; i < n; i++) for(int j = 0; j < i; j++) res = max(res, a[i] ^ a[j]); return res; }
trie树优化第二层循环
思路:
- 每次以该数的二进制形式插入Trie树, 每次查询可按照每位与之相反的方向走(如果有的话),最终走到叶子节点, 一定为与该数异或和最大的数
代码
const int N = 1e5 + 10, M = 31 * N; int n, x; int son[M][2], idx; void insert(int x) { int p = 0; for(int i = 30; i >= 0; i--) { int u = x >> i & 1; if(!son[p][u]) son[p][u] = ++ idx; p = son[p][u]; } } int query(int x) { int p = 0, res = 0; for(int i = 30; i >= 0; i--) { int u = x >> i & 1; if(son[p][!u]) { p = son[p][!u]; res = res * 2 + !u; } else { p = son[p][u]; res = res * 2 + u; } } return res; } int solve(int n) { int res = 0; for(int i = 0; i < n; i++) { int x; scanf("%d", &x); insert(x); res = max(res, query(x)); } return res; }
相关推荐
koushr 2020-11-12
zhangxiafll 2020-11-13
kikaylee 2020-10-31
范范 2020-10-28
MILemon 2020-10-22
hugebawu 2020-10-12
LauraRan 2020-09-28
shenwenjie 2020-09-24
omyrobin 2020-09-23
guangcheng 2020-09-22
qiangde 2020-09-13
hanyujianke 2020-08-18
晨曦之星 2020-08-14
xiesheng 2020-08-06
KAIrving 2020-08-02
xiesheng 2020-08-02
范范 2020-07-30
chenfei0 2020-07-30