BigHead
0%

双剑合并

Posted on Edited on In , Views: Valine:

题意

n把A剑m把B剑，每一把剑都有一个值x，让A和B各自中的某一把剑的值异或，使得异或的值最大，输出此值。n和m不超过1e6,x不超过1e9

分析

1.根据这题范围肯定需要O(n)级别算法，基本上就是固定A，然后B中的每一个值必须要在常数时间内找到最大对应的匹配的A的值。从这个限制描述，隐隐约约能够感觉到要用一个类似于字典树的东西。同时，基于一种贪心策略，尽可能的要让我合并后的值的最高位为1。所以，我们可以以最高位为根建一个深度为31的01二叉树，首先让A中的值一个一个插进去，并在相应节点标记为可走。那么B的某一个值只需要从根节点开始走，尽可能的走和自己不同的位的路(比如当前B的位是0,那么如果有1我就走1否则再走0)，这样能够保证走过的一定是最优的。

2.这题没啥可错的，做这题之前读了一片论文，所以很有帮助：浅谈信息学竞赛中的0和1by武森

思考

1.这题写的比较撮，每一个都特判了一下，后面看到汝佳的伸展树感觉写法挺好的。ch[2],0表示左儿子，1表示右儿子，值为-1表示不存在。这样的话就不用讨论当前是0还是1了，用一个变量o表示x当前的01位，ch[o]如果不存在就!o就好

2.以后遇到两个数值变成最大，那么优先考虑高位。同时异或的性质比较好，可以预处理后很快求出i项和j项的异或和，同时还有一个特点sum[i]^sum[j]=0 的话表明他们两个相等同时还表明第i项到第j项异或和是0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/*************************************************************************
	> File Name: a.cpp
	> Author: 
	> Mail: 
	> Created Time: 2016年05月02日 星期一 19时57分50秒
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
using namespace std;
#define ll long long
#define rep(i,n) for(int i =0; i < n; ++i)
#define CLR(x) memset(x,0,sizeof x)
#define MEM(a,b) memset(a,b,sizeof a)
#define pr(x) cout << #x << " = " << x << " ";
#define prln(x) cout << #x << " = " << x <<  endl; 
const int maxn = 4e6+100;
const int INF = 0x3f3f3f3f;
int code[40];
struct Node{
    int l, r;
}node[maxn];
int ans, sz;
void build(int pos, int id, int x){
    if(pos == -1) return;
    int c = x & (1<<pos);
    if(c) {
        if(node[id].l == -1) {
            node[id].l = sz++;
        }
        build(pos-1, node[id].l, x);
    } else {
        if(node[id].r == -1){
            node[id].r = sz++;
        }
        build(pos-1, node[id].r, x);
    }
}
void dfs(int pos, int id, int x){
    if(pos == -1) {
        if(x > ans) ans = x;
        return;
    }
    int c = x & (1<<pos);
    if(c) {
        if(node[id].r != -1){
            dfs(pos-1, node[id].r, x);
        } else {
            if((ans&(1<<pos)) && ans >= x) return;
            dfs(pos-1, node[id].l, x^(1<<pos));
        }
    } else {
        if(node[id].l != -1){
            dfs(pos-1, node[id].l, x^(1<<pos));
        } else {
            if((ans&(1<<pos)) && ans >= x) return;
            dfs(pos-1, node[id].r, x);
        }
    }
}
 int a[maxn], b[maxn];
int main(){
#ifdef LOCAL
	freopen("/home/zeroxf/桌面/in.txt","r",stdin);
	//freopen("/home/zeroxf/桌面/out.txt","w",stdout);
#endif
    int n, m, t;
    sz = maxn;
    scanf("%d", &t);
    while(t--){
        for(int i = 0; i < sz; ++i){
            node[i].l = node[i].r = -1;
        }
        sz = 1;
        ans = 0;
        int x;
        scanf("%d%d", &n, &m);
        for(int i = 0; i < n; ++i){
            scanf("%d", &x);
            build(30, 0, x);
        }
        for(int i = 0; i < m; ++i){
            scanf("%d", &x);
            dfs(30, 0, x);
        }
        printf("%d\n", ans);
    }
	return 0;
}