11367: 【原1367】最大异或

题目

题目描述

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

Description

给两个长度不超过30000的数列a，b，求 a_i xor b_j的最大值。

Input Format

第一行N，M表示a和b的长度

接下来N行，表示a的每个元素，不超过1000000000

接下来M行，表示b的每个元素，不插过1000000000

Output Format

一行一个整数，表示a和b中异或的最大值

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;
inline int read() {
    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() {
    n = read(), m = read();
    tree_a = new Node();
    tree_b = new Node();
    for (register int i = 0; i < n; ++i) {
        register int x = read();
        insert(tree_a, x, 0);
    }
    for (register int i = 0; i < m; ++i) {
        register int x = read();
        insert(tree_b, x, 0);
    }
    ans = dfs(tree_a, tree_b, 0);
    printf("%d", ans);
    return 0;
}