11367: 【原1367】最大异或

题目描述

author: Kainan Wang 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1367

Input Sample

``````2 1
1
2
2
``````

Output Sample

``````3
``````

ligongzzz's solution

``````#include "iostream"
#include "cstdio"
#include "algorithm"
using namespace std;

//二叉树
class special_tree {
public:
class node {
public:
//左孩子代表0
node* lchild = nullptr;
//右孩子代表1
node* rchild = nullptr;
};
node* root = nullptr;
special_tree() {
root = new node;
}
};

int cur_ans = 0;

void dfs(special_tree::node* p1, special_tree::node* p2,int ans) {
if (p1->lchild == nullptr && p1->rchild == nullptr) {
if (ans > cur_ans)
cur_ans = ans;
return;
}
ans = ans << 1;
if (p1->lchild && p2->rchild && p1->rchild && p2->lchild) {
dfs(p1->lchild, p2->rchild, 1 + ans);
dfs(p1->rchild, p2->lchild, 1 + ans);
}
else if (p1->lchild && p2->rchild) {
dfs(p1->lchild, p2->rchild, 1 + ans);
}
else if (p1->rchild && p2->lchild) {
dfs(p1->rchild, p2->lchild,1 + ans);
}
else if (p1->lchild && p2->lchild) {
dfs(p1->lchild, p2->lchild, ans);
}
else if (p1->rchild && p2->rchild) {
dfs(p1->rchild, p2->rchild, ans);
}
}

int main() {
int N, M;
scanf("%d %d", &N, &M);

special_tree tree_a, tree_b;

for (; N > 0; --N) {
int temp;
scanf("%d", &temp);
//化为2进制
bool ans[32] = { 0 };
for (int i = 31; i >= 0; temp = temp >> 1, --i)
ans[i] = temp % 2;
//写入二叉树
auto p = tree_a.root;
for (int i = 0; i < 32; ++i) {
if (ans[i]) {
if (p->rchild == nullptr)
p->rchild = new special_tree::node;
p = p->rchild;
}
else {
if (p->lchild == nullptr)
p->lchild = new special_tree::node;
p = p->lchild;
}
}
}

for (; M > 0; --M) {
int temp;
scanf("%d", &temp);
//化为2进制
bool ans[32] = { 0 };
for (int i = 31; i >= 0; temp = temp >> 1, --i)
ans[i] = temp % 2;
//写入二叉树
auto p = tree_b.root;
for (int i = 0; i < 32; ++i) {
if (ans[i]) {
if (p->rchild == nullptr)
p->rchild = new special_tree::node;
p = p->rchild;
}
else {
if (p->lchild == nullptr)
p->lchild = new special_tree::node;
p = p->lchild;
}
}
}

//寻找最大值
auto p1 = tree_a.root, p2 = tree_b.root;
dfs(p1, p2, 0);
printf("%d",cur_ans);

return 0;
}
``````

Neight99's solution

``````#include <iostream>

using namespace std;

const int maxN = 3e4 + 100;

long long a[maxN], b[maxN];
long long ans = 0;

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int N, M;

cin >> N >> M;
for (int i = 0; i < N; i++) {
cin >> a[i];
}
for (int i = 0; i < M; i++) {
cin >> b[i];
}

for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
long long temp = (a[i] xor b[j]);
if (temp > ans) {
ans = temp;
}
}
}

cout << ans;

return 0;
}
``````

yyong119's solution

``````#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX_N 30005
#define MAX_BIT 32
using namespace std;
const int value_bit[MAX_BIT] = {1073741824, 536870912, 268435456, 134217728,
67108864, 33554432, 16777216, 8388608,
4194304, 2097152, 1048576, 524288,
262144, 131072, 65536, 32768,
16384, 8192, 4096, 2048,
1024, 512, 256, 128,
64, 32, 16, 8, 4, 2, 1};
struct Node {
Node *zero, *one;
}*tree_a, *tree_b;
int num[MAX_BIT];
int n, m, ans;
char ch = getchar(); int res = 0;
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9')
res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return res;
}
void insert(Node *p, const int& x, int depth) {
if (depth == MAX_BIT) return;
if (!(x & value_bit[depth])) {
if (!p->zero) p->zero = new Node();
insert(p->zero, x, depth + 1);
}
else {
if (!p->one) p->one = new Node();
insert(p->one, x, depth + 1);
}
}
int dfs(Node *p, Node *q, int depth) {
if (depth == MAX_BIT) return 0;
int k = 0;
if (p->zero && q->one)
k = value_bit[depth] + dfs(p->zero, q->one, depth + 1);
if (p->one && q->zero)
k = max(k, value_bit[depth] + dfs(p->one, q->zero, depth + 1));
if (!k) {
if (p->zero && q->zero)
k = dfs(p->zero, q->zero, depth + 1);
if (p->one && q->one)
k = max(k, dfs(p->one, q->one, depth + 1));
}
return k;
}
int main() {
tree_a = new Node();
tree_b = new Node();
for (register int i = 0; i < n; ++i) {