01trie树
admin
|
|
556
|
算法知识总结

2173 字
|
33 分钟

01trie树顾名思义，是trie的一种特殊形式，树上只有0和1两种值，主要用于解决点与点甚至是区间的异或和最大、最小问题。

建树插入数字的时候和普通的trie树一模一样，而求一个数x与树上所有数的异或最大值时主要是用到贪心与二进制的思想：要使得异或和最大，肯定是每一位都最好是1

  • 当x的第i位为1

    • 如果树上此时可以选0，那就选0，此时该位异或后是1
    • 如果树上此时只能选1，那就选1，此时该位异或后是0

  • 当x的第i位为0

    • 如果树上此时可以选1，那就选1，此时该位异或后是1
    • 如果树上此时只能选0，那就选0，此时该位异或后是0

总结来说，看当前树上当前这一位^1的值存不存在，如果有，那就说明二进制下这一位是1，如果不存在，那二进制下这一位就是0

具体请看代码

int getans(int x){
    int ans = 0;
    int root = 0;
    for(int i = 31; i >= 0; --i){
        int id = (x >> i) & 1;//获取x的第i位
        if(tr[root][id ^ 1]){
            ans = ans << 1 | 1;
            root = tr[root][id ^ 1];
        }
        else{
            ans = ans << 1;
            root = tr[root][id];
        }
    }
    return ans;
}

看一个板子题：

The XOR Largest Pair

题目描述：

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

思路：

建树的时候将所有数都放到树上，然后再从头跑一遍，对每个数都查一次，比较出最大值输出即可

取数字x的第i位时，有三种方法：提前转换成字符串来做、用二进制、使用bitset

这三种都可以，不过后两种写起来容易一些。这三种方法中二进制的最快，其次是bitset，最后是字符串（亲测

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX  3300000 + 50
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define max(a,b) (((a)>(b)) ? (a):(b))
//#define min(a,b) (((a)>(b)) ? (b):(a))

typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, tot;
int tr[MAX][2];
int ar[100005];

void insert(int x){
    bitset<32>b(x);
    int root = 0;
    for(int i = 31; i >= 0; --i){
        int id = b[i];
        if(!tr[root][id])tr[root][id] = ++tot;
        root = tr[root][id];
    }
}

int getans(int x){
    int ans = 0;
    bitset<32>b(x);
    int root = 0;
    for(int i = 31; i >= 0; --i){
        int id = b[i];
        if(tr[root][id ^ 1]){
            ans = ans << 1 | 1;
            root = tr[root][id ^ 1];
        }
        else{
            ans <<= 1;
            root = tr[root][id];
        }
    }
    return ans;
}

int main(){
    sd(n);
    for(int i = 1; i <= n; ++i){
        sd(ar[i]);
        insert(ar[i]);
    }
    int ans = -1;
    for(int i = 1; i <= n; ++i){
        ans = max(ans, getans(ar[i]));
    }
    cout<<ans<<endl;
    return 0;   
}

Xor Sum

题目描述：

给n个数，然后m次查询，每次查询都给一个数x，问哪个数k与n异或后的值最大

思路：

这和上个题就有点区别了，上次是输出最大值，这次是要输出谁与x异或后最大

这里只需要对上面那个题进行小小的修改即可，也就是求max的时候进行判断，判断当前是0还是1，根据这个来确定k的每一位

  • 如果此时tr[root] [id ^ 1]不等于0

    • 如果此时id = 1，那k的这一位是0
    • 如果此时id = 0，那k的这一位是1

  • 如果此时tr[root] [id ^ 1]等于0

    • 如果此时id = 1，那k的这一位是1
    • 如果此时id = 1，那k的这一位是0

（id指的是x的第i位，k指的是每次查询需要输出的答案，root就是字典树用的那个东西

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX  3000000 + 50
#define mod 998244353
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define max(a,b) (((a)>(b)) ? (a):(b))
//#define min(a,b) (((a)>(b)) ? (b):(a))

typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int T;
int n, m, x;
int tot;
int tr[MAX][2];
int ans[MAX];
int flag, pos;

void insert(int x){
    int root = 0;
    for(int i = 31; i >= 0; --i){
        int id = (x >> i) & 1;
        if(!tr[root][id])tr[root][id] = ++tot;
        root = tr[root][id];
    }
    ans[root] = x;
}

int getans(int x){
    int cnt = 0;
    int root = 0;
    for(int i = 31; i >= 0; --i){
        int id = (x >> i) & 1;
        if(tr[root][id ^ 1]){
            if(id == 1)cnt = cnt << 1;
            else cnt = cnt << 1 | 1;
            root = tr[root][id ^ 1];

        }
        else{
            if(id == 1)cnt = cnt << 1 | 1;
            else cnt = cnt << 1;
            root = tr[root][id];
        }
    }
    return cnt;
}

void work(){
    flag = -1;tot = 0;
    mem(ans, 0);
    mem(tr, 0);
    sdd(n, m);
    for(int i = 1; i <= n; ++i){
        sd(x);
        insert(x);
    }
    for(int i = 1; i <= m; ++i){
        sd(x);
        cout<<getans(x)<<endl;
    }
}

int main(){
    sd(T);
    for(int t = 1; t <= T; ++t){
        cout<<"Case #"<<t<<":\n";
        work();
    }
    
    return 0;
}

Chip Factory

题目描述：

n个数，找到三个数ai、aj、ak，在i与j与k三者互不相同的条件下，输出(ai+aj)⊕ak的最大值，⊕指的是异或

思路：

n<=1000，说明可以直接暴力计算个ai+aj，将他作为一个数p，来查ak且与p异或后的最大值

但是这里的难点是怎么忽略ai与aj？建树的时候他们俩很大可能和别的数有公共的前缀，那就没法直接删掉了，不然会影响其他的数，但是我们可以通过一个num数组来标记，插入的时候给每个有值的位置的num都++，删除的时候就对要删的数x对应到树上的每一位的num都–，查询的时候就在if那里面加一个num的判断条件即可

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX  300000 + 50
#define mod 998244353
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define max(a,b) (((a)>(b)) ? (a):(b))
//#define min(a,b) (((a)>(b)) ? (b):(a))

typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n;
int x, tot;
int tr[MAX][2];
int num[MAX];
int ar[MAX];

void insert(int x){
    int root = 0;
    ++num[root];
    for(int i = 31; i >= 0; --i){
        int id = (x >> i) & 1;
        if(!tr[root][id])tr[root][id] = ++tot;
        root = tr[root][id];
        ++num[root];
    }
}

void update(int x, int op){
    int root = 0;
    num[root] += op;
    for(int i = 31; i >= 0; --i){
        int id = (x >> i) & 1;
        root = tr[root][id];
        num[root] += op;
    }
}

int getans(int x){
    int ans = 0;
    int root = 0;
    for(int i = 31; i >= 0; --i){
        int id = (x >> i) & 1;
        if(tr[root][id ^ 1] && num[tr[root][id ^ 1]] > 0){
            ans = ans << 1 | 1;
            root = tr[root][id ^ 1];
        }
        else{
            ans = ans << 1;
            root = tr[root][id];
        }
    }
    return ans;
}



void work(){
    tot = 0;
    mem(tr, 0);
    mem(num, 0);
    sd(n);
    for(int i = 1; i <= n; ++i){
        sd(ar[i]);
        insert(ar[i]);
    }
    int maxn = 0;
    for(int i = 1; i <= n; ++i){
        update(ar[i], -1);
        for(int j = i + 1; j <= n; ++j){
            update(ar[j], -1);
            maxn = max(maxn, getans(ar[i] + ar[j]));
            update(ar[j], 1);
        }
        update(ar[i], 1);
    }
    cout<<maxn<<endl;
}

int main(){
    int T;
    sd(T);
    for(int t = 1; t <= T; ++t){
        work();
    }
    
    return 0;
}

Nikitosh 和异或

题目描述：

给一个数组，找两个任意长度且没有重叠的区间[l1, r1], [l2, r2],设这两个区间异或的值分别为a,b，输出最大的a+b

思路：

这个题需要一些思维

求两个没有重叠的区间的异或后的和最大，没有重叠不好搞

我们可以求两个数组ar、br，ar代表从1开始到i中连续区间的异或和的最大值，br代表从i到n中连续区间的异或和的最大值

那ans就只需要从1循环到最后，取max(ar[i] + br[i + 1])即可

这样我们需要做的就是求前缀区间的异或最大值、后缀区间的异或最大值、就想普通的那样做就行

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX  13000000 + 50
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define max(a,b) (((a)>(b)) ? (a):(b))
//#define min(a,b) (((a)>(b)) ? (b):(a))

typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, x, num;
int tr[MAX][2];
int ar[400005], br[400005];
int tot;

void insert(int x){
    int root = 0;
    bitset<32>b(x);
    for(int i = 31; i >= 0; --i){
        int id = b[i];
        if(!tr[root][id])tr[root][id] = ++tot;
        root = tr[root][id];
    }
}

int getans(int x){
    bitset<32>b(x);
    int ans = 0, root = 0;
    for(int i = 31; i >= 0; --i){
        int id = b[i];
        if(tr[root][id ^ 1]){
            ans <<= 1;ans |= 1;
            root = tr[root][id ^ 1];
        }
        else{
            ans <<= 1;
            root = tr[root][id];
        }
    }
    return ans;
}


int main(){
    sd(n);
    for(int i = 1; i <= n; ++i){
        sd(ar[i]);
    }
    insert(0);
    int maxn = -1;
    int pre = 0;
    for(int i = 1; i <= n; ++i){
        pre ^= ar[i];
        maxn = max(maxn, getans(pre));
        ar[i] = maxn;
        insert(pre);
    }
    tot = 0;maxn = -1;
    mem(tr, 0);
    pre = 0;
    for(int i = n; i >= 1; --i){
        pre ^= ar[i];
        maxn = max(maxn, getans(pre));
        br[i] = maxn;
        insert(pre);
    }
    int ans = -1;
    for(int i = 1; i < n; ++i){
        ans = max(ans, ar[i] + br[i + 1]);
    }
    cout<<ans<<endl;
    return 0;
}

奶牛异或

题目描述：

农民约翰在喂奶牛的时候被另一个问题卡住了。他的所有N(1 <= N <= 100,000)个奶牛在他面前排成一行(按序号1..N的顺序)，按照它们的社会等级排序。奶牛#1有最高的社会等级，奶牛#N最低。每个奶牛同时被指定了一个不唯一的附加值，这个数在 [0, 221 – 1] 的范围内。

帮助农民约翰找出应该从哪一头奶牛开始喂，使得从这头奶牛开始的一个连续的子序列上，奶牛的附加值的异或最大。

如果有多个这样的子序列，选择结尾的奶牛社会等级最高的。如果还不唯一，选择最短的。

思路：

求一个连续区间的异或最大值，还要结尾是社会等级最高的

我们边输入边查询答案，再插入前缀异或值

这样就有利于确定结尾是谁而不会混乱

要注意一些边界的细节问题

还有就是ans的初始值必须要小于0，不然如果最终ans是0就会出大问题，你的l和r是不会更新的！

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX  2300000 + 50
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define max(a,b) (((a)>(b)) ? (a):(b))
//#define min(a,b) (((a)>(b)) ? (b):(a))

typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n;
int tot, x, num;
int l, r, ans;
int tr[MAX][2];
int now[MAX];

void insert(int x, int pos){
    int root = 0;
    for(int i = 21; i >= 0; --i){
        int id = (x>>i) & 1;
//        cout<<id;
        if(!tr[root][id])tr[root][id] = ++tot;
        root = tr[root][id];
    }
//    cout<<endl;
    now[root] = pos;
}

void getans(int x, int rr){
    int root = 0;
    int cnt = 0;
    for(int i = 21; i >= 0; --i){
        int id = (x>>i) & 1;
        if(tr[root][id ^ 1]){
            cnt <<= 1;cnt |= 1;
            root = tr[root][id ^ 1];
        }
        else {
            cnt <<= 1;
            root = tr[root][id];
        }
    }
    if(ans < cnt){
        ans = cnt;
        r = rr;
        l = now[root] + 1;
    }
}

int main(){
    sd(n);
    ans = -1;
    insert(0, 0);
    for(int i = 1; i <= n; ++i){
        sd(x);
        num ^= x;
        getans(num, i);
        insert(num, i);
    }
    cout<<ans<<' '<<l<<' '<<r<<endl;
    return 0;
}

 

博客内容均系原创，未经允许严禁转载！
数据结构
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
trie树题单

							
							

							
势能线段树

							
							

							
线段树题单

							
							

							
2022 CCPC Henan Provincial Collegiate Programming Contest「J – Mex Tree dfs序+ST表」

							
							

							
树状数组题单