01字典树

01字典树: 解决最大异或问题

和字典树一样，只不过每一个节点的值不再是字符而是01，一个数从高位到低位对应于字典树从根到叶子，一个数二进制有多少位，就应该建几层树，包含根节点的那个编号0

树上的每一个点都有各自的编号，节点有两条边，分别是0和1，开空间时应该多开40倍左右

HDU4825 Xor Sum

题目链接

这道题数据有点水，说是不超过2^32^，其实连int都没有爆，应该开33层(包含根节点)，但是实际上32层就可以，代码是开了33层

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
#include <bits/stdc++.h>
//#pragma G++ optimize(2)
//#pragma G++ optimize(3,"Ofast","inline")
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MAXN=1e5+100;
const ll MOD=1e9+7;
const ll INF=0x3f3f3f3f;
const ll SUB=-0x3f3f3f3f;
const double eps=1e-4;
const double E=exp(1);
const double pi=acos(-1);
int ch[30*MAXN][2];
int val[30*MAXN];
int tot,t,n,m;
void init(){
    memset(val,0,sizeof val);
    memset(ch,0,sizeof ch);
    tot=0;
}
void insert(int v){
    int u=0;
    for(int i=31;i>=0;i--){
        int now=(v>>i)&1;
        if(!ch[u][now]) ch[u][now]=++tot;
        u=ch[u][now];
    }
    val[u]=v;
}
int query(int x){
    int u=0;
    for(int i=31;i>=0;i--){
        int now=(x>>i)&1;
        if(ch[u][now^1]) u=ch[u][now^1];
        else u=ch[u][now];
    }
    return val[u];
}
int main(){
    ios;
    cin>>t;
    int js=0;
    while(t--){
        cin>>n>>m;
        init();
        for(int i=1;i<=n;i++){
            int tmp;
            cin>>tmp;
            insert(tmp);
        }
        cout<<"Case #"<<++js<<":\n";
        while(m--){
            int tmp;
            cin>>tmp;
            cout<<query(tmp)<<'\n';
        }
    }

    return 0;
}

/*

*/

Chip Factory

题目链接

在一个数组中找出 (s[i]+s[j])^s[k] 最大的值，其中 i、j、k 各不相同。

可以找出任意两个数的和，然后把这两个数从字典树中删除，之后查询最大异或，再添加上，再找，如此往复，输出最大值即可

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
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
using namespace std;
const int MAXN=1010;
int t,n,tot;
int ch[MAXN*40][2],arr[MAXN],val[MAXN*40];
int num[MAXN*40]; 
void insert(int x){
    int u=0;
    for(int i=31;i>=0;i--){
        int now=(x>>i)&1;
        if(!ch[u][now]) ch[u][now]=++tot;
        u=ch[u][now];
        num[u]++;
    }
    val[u]=x;
}
int query(int x){
    int u=0;
    for(int i=31;i>=0;i--){
        int now=(x>>i)&1;
        if(ch[u][now^1] && num[ch[u][now^1]]) u=ch[u][now^1];
        else u=ch[u][now];
    }
    return val[u]^x;
}
void update(int x,int c){
    int u=0;
    for(int i=31;i>=0;i--){
    	int now=(x>>i)&1;
    	num[ch[u][now]]+=c;
    	u=ch[u][now];
	}
}
void init(){
	tot=0;
	memset(val,0,sizeof val);
	memset(num,0,sizeof num);
	memset(ch,0,sizeof ch);
}
int main()
{
    ios;
    cin>>t;
    while(t--){
    	init();
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>arr[i];
            insert(arr[i]);
        }
        int ans=-1;
        for(int i=1;i<n;i++){
            for(int j=i+1;j<=n;j++){
                int cur=arr[i]+arr[j];
                update(arr[i],-1);
                update(arr[j],-1);
                ans=max(ans,query(cur));
                update(arr[i],1);
                update(arr[j],1);
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

The xor-longest Path

题目链接

在树上找一段路径（连续）使得边权相异或的结果最大。

image-20210507212604651

CODE

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
const int MAXN=110010;
struct edge{
	int to,w,next;
}e[MAXN*2];
int t,n,tot,cnt,root,ans;
int val[MAXN*32];
int ch[MAXN*32][2];
int head[MAXN];
void add(int u,int v,int c){
	e[cnt]={v,c,head[u]};
	head[u]=cnt++;
}
void insert(int x){
    int u=0;
    for(int i=31;i>=0;i--){
        int now=(x>>i)&1;
        if(!ch[u][now]) ch[u][now]=++tot;
        u=ch[u][now];
    }
    val[u]=x;
}
int query(int x){
    int u=0;
    for(int i=31;i>=0;i--){
        int now=(x>>i)&1;
        if(ch[u][now^1]) u=ch[u][now^1];
        else u=ch[u][now];
    }
    return val[u]^x;
}
void dfs(int x,int f,int pre){
	for(int i=head[x];~i;i=e[i].next){
		int v=e[i].to,w=e[i].w;
		if(v==f) continue;
		ans=max(ans,query(pre^w));
		insert(pre^w);
		dfs(v,x,pre^w);
	}
}
void init(){
	memset(val,0,sizeof val);
	memset(ch,0,sizeof ch);
	memset(head,-1,sizeof head);
	ans=0; cnt=0; tot=0;
}
int main()
{
    ios;
    while(scanf("%d",&n)!=EOF){
    	init();
    	for(int i=0;i<n-1;i++){
    		int u,v,w;
    		scanf("%d%d%d",&u,&v,&w);
    		add(u,v,w);
    		add(v,u,w);
		}
		insert(0);
		dfs(root,-1,0);
		printf("%d\n",ans);
	}
    return 0;
}
/*
4
0 1 3
1 2 4
1 3 6
*/