网站建设支出及维护费应怎样做账,山西并州建设有限公司,seo网络营销,做网站需要美工吗知识概览
Trie#xff1a;高效地存储和查找字符串集合的数据结构数字、汉字可以用二进制位来存 例题展示
题目链接
Trie字符串统计#xff1a;
https://www.acwing.com/problem/content/837/
代码
#include cstdioconst int N 100010;int son[N][26], cnt[N],…知识概览
Trie高效地存储和查找字符串集合的数据结构数字、汉字可以用二进制位来存 例题展示
题目链接
Trie字符串统计
https://www.acwing.com/problem/content/837/
代码
#include cstdioconst int N 100010;int son[N][26], cnt[N], idx; // 下标是0的点既是根节点又是空节点
char str[N];void insert(char str[])
{int p 0;for (int i 0; str[i]; i){int u str[i] - a;if (!son[p][u]) son[p][u] idx;p son[p][u];}cnt[p];
}int query(char str[])
{int p 0;for (int i 0; str[i]; i){int u str[i] - a;if (!son[p][u]) return 0;p son[p][u];}return cnt[p];
}int main()
{int n;scanf(%d, n);while (n--){char op[2];scanf(%s%s, op, str);if (op[0] I) insert(str);else printf(%d\n, query(str));}return 0;
} 题目链接
最大异或对
https://www.acwing.com/problem/content/145/
题解
对于每个数先插入然后再找和这个数异或最大的数找的方法是找已存储在字典树的数从高位到低位尽量找和当前数该位不同的数。最终得到的数即为所求。
代码
#include cstdio
#include algorithmusing namespace std;const int N 100010, M 31 * N;int n;
int son[M][2], idx, x;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 main()
{scanf(%d, n);int res 0;for (int i 0; i n; i){scanf(%d, x);insert(x);int t query(x);res max(res, x ^ t);}printf(%d\n, res);return 0;
}
