AcWing 143 最大异或对

2021-05-16 23:29

阅读：596

标签：math mask name int 字符串复杂 const 答案 char

在给定的\(N\)个整数\(A1，A2……AN\)中选出两个进行xor（异或）运算，得到的结果最大是多少？

输入格式
第一行输入一个整数N。

第二行输入N个整数\(A1～AN\)。

输出格式
输出一个整数表示答案。

数据范围

\(1≤N≤105,\)

\(0≤Ai

输入样例

3

1 2 3

输出样例

3

算是一个Trie树的模板题，归纳一下Trie树的相关知识。

Trie树用于实现字符串快速检索，是一种多叉树结构，其每个结点都有若干子结点。一般的操作有：

初始化

一个空Trie只包含一个根节点

int trie[SIZE][26], tot = 1;  //trie数组的第二维通常是已知的，这里只考虑小写字母，所以每个节点最多有26个子结点，tot是节点指针，对应于第一维

插入

void insert(char* str){
    int len = strlen(str), p = 1;
    for(int k = 0; k

检索

bool search(char* str){
    int len = strlen(str), p = 1;
    for(int k = 0; k

回到问题上，这里是统计异或对，那么每个结点的子结点就只有0和1两种情况，即每个结点最多有两个儿子。我们对每个输入的数字，都将它的二进制串存储在trie树上，同时再在trie树上检索这个数字，对某个数A，如果它的某一位二进制数是0，那么我们在检索时就看trie树上对应结点的子结点是否有1，即去搜索与当前数的bit位相反的结点，如果有就记录1，没有就沿着相同结点继续搜索，并记录0.

整个trie树的结点总数（空间复杂度）应该是儿子个数 X 字串最大长度

#include 

using namespace std;

const int maxn = 3000000;  //这里我之前取的是2> 1;
    }
}

int tofind(int x){
    int p = 0, res = 0, mask = 1 > 1;
    }
    return res;
}

int main(){
    int n; scanf("%d", &n);
    int ans = 0;
    for(int i = 0; i

AcWing 143 最大异或对

标签：math mask name int 字符串复杂 const 答案 char

原文地址：https://www.cnblogs.com/patrolli/p/11795783.html

上一篇：windows追看日志bat脚本

下一篇：Win10常用快捷键

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 143 最大异或对
文章链接：http://soscw.com/index.php/essay/86464.html

亲，登录后才可以留言！

AcWing 143 最大异或对

评论

热门文章

推荐文章

最新文章

置顶文章