?

?

1783: 秋實大哥與快餐店

Time Limit:?1 Sec??Memory Limit:?128 MB
Submit:?78??Solved:?12
[Submit][Status][Web Board]

Description

朝為田舍郎，暮登天子堂。秋實大哥從小就懷抱有遠大的理想，所以他開了一家快餐店。

秋實大哥根據菜的口感，給每一道菜一個唯一的CID，同時對于前來的客人，根據他們的口味喜好，秋實大哥會給每一個客人一個PID。

對于一個標號為PID的客人，他對標號為CID的菜的喜愛程度為PID∧CID(∧表示按位異或），該值越大表示越喜歡。

秋實大哥實在太忙了，現在他需要你來幫忙照看一下他的店鋪。

?

Input

第一行包含一個整數n，表示秋實大哥的餐館內現在有n道菜。接下來一行包含n個整數，分別表示每一道菜的CID。

接下來一行包含一個整數m，表示接下來發生了m件事。接下來的m行，每一行為以下兩種事件之一：

0 c : 表示秋實大哥最新研制出一道標號為c的菜

1 p : 表示來了一位標號為p的客人，請你在已有的菜中找出一道他最喜愛的菜

1≤n，m≤100000，0≤PID，CID≤1000000。

?

Output

對于每一個1 p事件輸出一個整數，表示該客人最喜歡的菜的標號

?

Sample Input

1

1

3

1 1

0 2

1 1

Sample Output

1

2

?因為題目說了是cid^pid最大的數，所以根據異或相同則0，不同則1的性質可知，只要是高位二進制各異就是最大的數了。所以我們可以用菜的價值來建立一顆0-1的二叉樹。也就是01字典樹。

第一種寫法：

#include<bits/stdc++.h> using namespace std;#define MAXN 100005 #define ll long long int n,m; int trie[32*MAXN][2]; ll val[32*MAXN]; int tot; void insert(ll d) {int root=0;for(int i=32;i>=0;i--){int id=(d>>i)&1;if(!trie[root][id]) trie[root][id]=++tot;root=trie[root][id];}val[root]=d; } ll query(ll d) {int root=0;for(int i=32;i>=0;i--){int id=(d>>i)&1;if(trie[root][id^1]) root=trie[root][id^1];else root=trie[root][id];}return val[root]; } int main() {while(~scanf("%d",&n)){//題目沒有說要多組輸入，但是是多組輸入的要不然就會Wrongmemset(trie,0,sizeof trie);for(int i=0;i<n;i++){ll d;scanf("%lld",&d);insert(d);}scanf("%d",&m);for(int i=0;i<m;i++){int t;ll d;scanf("%d%lld",&t,&d);if(t&1)printf("%lld\n",query(d));else insert(d);}}return 0; }

第二種是在網上看到別的大佬寫的 （搞不清里面的rt<<1|1和rt<<1）

#include<bits/stdc++.h> using namespace std; int n,m; const int maxbit = 20;struct node {int L,R,id; }tire[1<<22];//其實就是一顆0-1組成的二叉樹的葉子節點處標記一個菜品idvoid Insert(int x)//插入一個數 {int rt = 1;for(int i=1;i<=maxbit;++i){//一共有20位if((x >>(maxbit - i))&1){//x當前二進制的maxbit-i+1位當前是否為1tire[rt].R = 1;//標記在右子樹rt=(rt<<1|1);}else{tire[rt].L = 1;//標記在左子樹rt=(rt<<1);printf("%d**\n",rt);}}//printf("%d**\n",rt);tire[rt].id = x;//放入菜品id }int query(int x) {int rt = 1,tar = ~x;for(int i=1;i<=maxbit;++i){if((tar >>(maxbit-i))&1){//取反后的數在右子樹if(tire[rt].R){//如果右子樹標記過，則肯定是這個數最大rt = rt<<1|1;}else {//否則應該走回與x原來的二進制位才能繼續找最大rt = rt << 1;}}else {if(tire[rt].L){rt = rt<<1;}else {rt = rt<<1|1;}}}return tire[rt].id; }int main() {int i,j,k,c,p;while(~scanf("%d",&n)){memset(tire,0,sizeof(tire));for(i=0;i<n;++i){scanf("%d",&k);Insert(k);}scanf("%d",&m);for(i=0;i<m;++i){scanf("%d%d",&c,&p);if(c&1){printf("%d\n",query(p));}else {Insert(p);}}}return 0; }

?

總結

以上是生活随笔為你收集整理的zcmu-1783（01字典树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。