精华内容
下载资源
问答
  • 01 Trie

    2020-07-31 21:22:54
    01 Trie 一般是从高位向低位建树,因为高位的贡献大,方便贪心。 void add(int x) { int p = 0; for (int i = 30; i >= 0; i--) { //int int d = (n >> i) & 1; if (!trie[p][d]) trie[p][d] = +...

    构造

    01 Trie 一般是从高位向低位建树,因为高位的贡献大,方便贪心。

    void add(int x) {
    	int p = 0;
    	for (int i = 30; i >= 0; i--) { //int
    		int d = (x >> i) & 1;
    		if (!trie[p][d]) trie[p][d] = ++cnt;
    		p = trie[p][d];
    	}
    	val[p] = x;
    }
    

    查询

    01 Trie 的查询一般是这样的形式:给定一个数 xx,求与 xx 异或最大的数是多少。假设已经建立了所有数的 01 Trie,那么找这个数的复杂度近似 O(1)O(1)。因为异或的特征是相同为 00,不同为 11,所以从高位到低位,贪心地走不一样的路。

    int query(int x) {
    	int p = 0;
    	for (int i = 30; i >= 0; i--) {
    		int d = (x >> i) & 1;
    		if (trie[p][d ^ 1]) p = trie[p][d ^ 1];
    		else if (trie[p][d]) p = trie[p][d]; // ( ) 不要落了
    	}
    	return val[p];
    }
    

    删除

    如何删除 Trie 树上的一个数字?只需要记录一个 visvis,为经过某个点的数字的数量,删的时候沿途 vis ⁣vis-\!-。在查询的时候,走 vis>0vis > 0 的点即可。

    void update(int x, int k) {
    	int p = 0; 
    	for (int i = 20; i >= 0; i--) {
    		int d = (x >> i) & 1;
    		p = trie[p][d]; vis[p] += k;
    	}
    }
    

    Trie 树合并

    给定一个数 xx,求与 xx and、or 最大的数是多少。

    那么还是从高到低建 01 Trie。以 and 为栗子,从高到低贪心时,如果当前位是 11,那么在树上就走 11。如果当前位是 00,那么 1100 都可以,怎么办?

    可以在建出字典树后,用类似线段树合并的方法,合并 Trie 树每个点的左右儿子,即为把 00 变成 0101 的结合体。注意合并的顺序,先合并儿子。这样查询的时候,就放心往 00 走就行了。

    void merge(int &x, int y) {
    	if (!x || !y) {
    		x += y;
    		return ;
    	}
    	merge(trie[x][0], trie[y][0]);
    	merge(trie[x][1], trie[y][1]);
    }
    void dfs(int x) {
    	if (trie[x][0]) dfs(trie[x][0]);
    	if (trie[x][1]) dfs(trie[x][1]);
    	merge(trie[x][0], trie[x][1]);
    }
    int query_and(int x) { 
    	int p = 0, ans = 0;
    	for (int i = 20; i >= 0; i--) {
    		int d = (x >> i) & 1;
    		if (d == 1 && trie[p][1] && vis[trie[p][1]] > 0) p = trie[p][1]; 
    		else if (trie[p][0]&& vis[trie[p][0]] > 0) p = trie[p][0];
    	}
    	return val[p];
    }
    

    Trick

    abb=aa \oplus b \oplus b= a

    x=[1,l],y=[1,r]l,r=xy\forall x = \oplus_{[1,l]}, y = \oplus_{[1,r]} \to\oplus_{l,r} = x \oplus y

    x=(a,b),y=(b,c)(a,c)=xy\forall x = \oplus_{(a,b)}, y = \oplus_{(b,c)} \to \oplus_{(a,c)} = x \oplus y

    P4551 最长异或路径

    (u,v)\oplus_{(u,v)} 转化成 u\oplus_{u}v\oplus_{v}。建立一棵字典树,枚举一个 u\oplus_{u} ,在字典树上贪心去找最大的 v\oplus_{v},并更新答案即可。

    ZR956 集合


    相关内容 AT3913 XOR Tree

    这一道题和 01 Trie 的关系不大,但关于异或的知识有许多。

    展开全文
  • 01trie

    2017-12-25 22:34:00
    把所有的f(i)都插入一个01trie上,然后枚举一个f(i),再贪心另一个。   BZOJ - 3261 #include #include using namespace std; inline char nc() { static char b[ 1 12 ],*s=b,*t= b; ...

    貌似可以解决一些跟异或相关的问题?

     

    POJ - 3764 

     1 #include<vector>
     2 #include<cstdio>
     3 #include<iostream>
     4 #define pb push_back
     5 #define nc getchar
     6 #define read(x) scanf("%d", &x)
     7 using namespace std;
     8 struct Edge{int v, w, n;} E[200005];
     9 int n, d[100005], head[100005], ec;
    10 inline void aE(int u, int v, int w) {
    11     E[++ec] = (Edge){v, w, head[u]}; head[u] = ec;
    12     E[++ec] = (Edge){u, w, head[v]}; head[v] = ec;
    13 }
    14 void dfs(int u, int f, int w) {
    15     d[u] = w; for (int i = head[u]; i; i = E[i].n)
    16         if (E[i].v != f) dfs(E[i].v, u, E[i].w ^ w);
    17 }
    18 struct Node {
    19     Node *ch[2];
    20 } Tnull, *null = &Tnull, *root;
    21 Node mem[2000000], *C;
    22 inline Node* newNode() {
    23     C->ch[0] = C->ch[1] = null; return C++;    
    24 }
    25 void insert(int x) {
    26     Node *u = root;
    27     for (int i = 31; ~i; --i) {
    28         int c = (x >> i) & 1;
    29         if (u->ch[c] == null) u->ch[c] = newNode();
    30         u = u->ch[c];
    31     }
    32 }
    33 int find(int x) {
    34     Node *u = root; int res = 0;
    35     for (int i = 31; ~i; --i) {
    36         int c = !((x >> i) & 1);
    37         if (u->ch[c] == null) u = u->ch[!c];
    38         else u = u->ch[c], res += 1 << i;
    39     } return res;
    40 }
    41 void solve() {
    42     for (int i = 1; i <= n; ++i) insert(d[i]);    int res = 0;
    43     for (int i = 1; i <= n; ++i) res = max(res, find(d[i]));
    44     printf("%d\n", res);
    45 }
    46 int main() {
    47     while (~scanf("%d", &n)) {
    48         for (int u, v, w, i = 1; i < n; ++i)
    49             read(u), read(v), read(w), aE(u + 1, v + 1, w);
    50         for (int i = head[1]; i; i = E[i].n) dfs(E[i].v, 1, E[i].w);
    51         C = mem; root = newNode(); solve();
    52         for (int i = 1; i <= n; ++i) d[i] = 0;
    53         for (int i = 1; i <= n; ++i) head[i] = 0;
    54         ec = 0;
    55     }
    56     return 0;    
    57 }
    View Code

    这题咱用vector存边T了。

    记f(i)为从根节点出发到i点时边权的异或和。

    根据异或的性质,u-v这条路径的异或和就是f(u) xor f(v)。

    把所有的f(i)都插入一个01trie上,然后枚举一个f(i),再贪心另一个。

     

    BZOJ - 3261

    #include<cstdio>
    #include<iostream>
    using namespace std;
    inline char nc() {
        static char b[1<<12],*s=b,*t=b;    
        return s==t&&(t=(s=b)+fread(b,1,1<<12,stdin),s==t)?-1:*s++;
    }
    inline void read(int &x) {
        char b = nc(); x = 0;
        for (; !isdigit(b); b = nc());
        for (; isdigit(b); b = nc()) x = x * 10 + b - '0';
    }
    inline int read() {
        char b = nc();
        for (; !isalpha(b); b = nc());
        return b == 'A';
    }
    struct Node {
        Node *ch[2]; int v;    
    } Tnull, *null = &Tnull;
    Node mem[24000010], *rt[600010], *C = mem;
    inline Node* newNode() {
        C->ch[0] = C->ch[1] = null;    C->v = 0; return C++;
    }
    int n, m, xr;
    void insert(int x, Node *u, Node *p) {
        for (int i = 24; ~i; --i) {
            int c = (x >> i) & 1;
            if (u->ch[c] == null) u->ch[c] = newNode();
            u->ch[!c] = p->ch[!c];
            u = u->ch[c]; p = p->ch[c];
            u->v = p->v + 1;
        }
    }
    int query(int x, Node *L, Node *R) {
        int res = 0;
        for (int i = 24; ~i; --i) {
            int c = !((x >> i) & 1);
            if (R->ch[c]->v - L->ch[c]->v > 0) res += 1 << i; else c = !c;
    //        R->ch[c]->v - L->ch[c]->v > 0 ? res += 1 << i : c = !c;
            R = R->ch[c], L = L->ch[c];
        } return res;
    }
    int main() {
        null->ch[0] = null->ch[1] = null;
        read(n); read(m); ++n;
        rt[0] = newNode(); rt[1] = newNode(); insert(0, rt[1], rt[0]);
        for (int i = 2, t; i <= n; ++i) 
            read(t), xr ^= t, rt[i] = newNode(), insert(xr, rt[i], rt[i-1]);
        for (int x, l, r, i = 0; i < m; ++i) {
            if (read()) {
                read(x); xr ^= x; ++n; rt[n] = newNode(); insert(xr, rt[n], rt[n-1]);
            } else {
                read(l); read(r); read(x);
                printf("%d\n", query(xr ^ x, rt[l-1], rt[r]));
            }
        }    
        return 0;
    }
    View Code

    记 $f_n = a_1 \; xor \; a_2 \; xor \; ... \; xor \; a_n$

    即求 $x \; xor \; f_n \; xor \; f_{p-1}$ 的最大值。

    注意到 $x \; xor \; f_n$ 为一定值,所以我们只需要在只存$[l-1, r-1]$这段区间值的trie上贪心就行。

     

    BZOJ - 3689

     1 #include<queue>
     2 #include<cstdio>
     3 #include<iostream>
     4 #define nc getchar
     5 using namespace std;
     6 inline void read(int &x) {
     7     char b = nc(); x = 0;
     8     for (; !isdigit(b); b = nc());
     9     for (; isdigit(b); b = nc()) x = x * 10 + b - '0';
    10 }
    11 struct Node {
    12     Node *ch[2]; int sz;
    13 } Tnull, *null = &Tnull, *root;
    14 Node mem[3200000], *C = mem;
    15 inline Node* newNode() {
    16     C->sz = 0; C->ch[0] = C->ch[1] = null; return C++;
    17 }
    18 void insert(int x) {
    19     Node *u = root; ++u->sz;
    20     for (int i = 30; ~i; --i) {
    21         int c = (x >> i) & 1;
    22         if (u->ch[c] == null) u->ch[c] = newNode();
    23         u = u->ch[c]; ++u->sz;
    24     }
    25 }
    26 int query(int x, int k) {
    27     Node *u = root; int res = 0;
    28     for (int i = 30; ~i; --i) {
    29         int c = (x >> i) & 1;
    30         if (k > u->ch[c]->sz) 
    31             res |= 1 << i, k -= u->ch[c]->sz, c = !c;
    32         u = u->ch[c];
    33     } return res;
    34 }
    35 struct Info {
    36     int v, k, p;
    37     inline bool operator<(const Info &o) const {return v > o.v;}
    38 };
    39 int n, m, a[100010];
    40 priority_queue < Info > q;
    41 int main() {
    42     read(n); read(m); m *= 2; root = newNode();
    43     for (int i = 1; i <= n; ++i) read(a[i]), insert(a[i]);
    44     for (int i = 1; i <= n; ++i) q.push((Info){query(a[i], 2), 2, i});
    45     while (m--) {
    46         Info h = q.top(); q.pop();
    47         if (m & 1) printf("%d ", h.v);
    48         if (h.k == n) continue;
    49         q.push((Info){query(a[h.p], h.k + 1), h.k + 1, h.p});
    50     }
    51     return 0;
    52 }
    View Code

    堆+01trie。

    在trie树上的每个节点处记录一个v,表示经过的次数,这样就可以资磁查询第k大的操作了。

    用一个堆来维护当前最小的异或值。要记录这个值是从哪里来的,第几大。

    因为$x_i \; xor \; x_j$ 和 $x_j  \;xor\; x_i$ 是一种情况,所以要循环2k次,并在奇数次输出。

    然后再找到a_i异或后的第k+1大值,放入堆中。 

     

    BZOJ - 4103

     1 #include<queue>
     2 #include<cstdio>
     3 #include<iostream>
     4 using namespace std;
     5 inline char nc() {
     6     static char b[1<<14],*s=b,*t=b;
     7     return s==t&&(t=(s=b)+fread(b,1,1<<14,stdin),s==t)?-1:*s++;
     8 }
     9 inline void read(int &x) {
    10     char b = nc(); x = 0;
    11     for (; !isdigit(b); b = nc());
    12     for (; isdigit(b); b = nc()) x = x * 10 + b - '0';
    13 }
    14 struct Node {
    15     Node *ch[2]; int sz;    
    16 } Tnull, *null = &Tnull, *rt[300010], *L[1005], *R[1005];
    17 Node mem[20000000], *C = mem;
    18 inline Node* newNode() {
    19     C->ch[0] = C->ch[1] = null; C->sz = 0; return C++;    
    20 }
    21 int n, m, a[1005], q;
    22 void insert(int x, Node *u, Node *v) {
    23     for (int c, i = 30; ~i; --i) {
    24         c = (x >> i) & 1;
    25         if (u->ch[c] == null) u->ch[c] = newNode();
    26         u->ch[!c] = v->ch[!c];
    27         u = u->ch[c]; v = v->ch[c]; u->sz = v->sz + 1;
    28     }
    29 }
    30 int query(Node *ll, Node *rr, int l, int r, int k) {
    31     int res = 0;
    32     for (int i = l; i <= r; ++i) L[i] = ll, R[i] = rr;
    33     for (int c, sz, d = 30; ~d; --d) {
    34         sz = 0;
    35         for (int i = l; i <= r; ++i) {
    36             c = (a[i] >> d) & 1;
    37             sz += R[i]->ch[c]->sz - L[i]->ch[c]->sz;
    38         }
    39         if (k <= sz) {
    40             for (int i = l; i <= r; ++i) {
    41                 c = (a[i] >> d) & 1;
    42                 L[i] = L[i]->ch[c]; R[i] = R[i]->ch[c];
    43             }
    44         } else {
    45             k -= sz; res |= 1 << d; 
    46             for (int i = l; i <= r; ++i) {
    47                 c = !((a[i] >> d) & 1);
    48                 L[i] = L[i]->ch[c]; R[i] = R[i]->ch[c];
    49             }
    50         }
    51     } return res;
    52 }
    53 int main() {
    54     read(n); read(m); null->ch[0] = null->ch[1] = null;
    55     for (int i = 0; i <= m; ++i) rt[i] = newNode();
    56     for (int i = 1; i <= n; ++i) read(a[i]);
    57     for (int t, i = 1; i <= m; ++i) read(t), insert(t, rt[i], rt[i-1]);
    58     read(q);
    59     for (int i = 0, u, d, l, r, k; i < q; ++i) {
    60         read(u); read(d); read(l); read(r); read(k);
    61         printf("%d\n", query(rt[l-1], rt[r], u, d, (r - l + 1) * (d - u + 1) - k + 1));
    62     }
    63     return 0;
    64 }
    View Code

    注意到n很小而m很大,所以我们在m上建立可持久化trie树,n直接暴力就行。

    查询第k大也很好搞,咱只要看看使异或值小的个数就行,看看与当前二进制位相同的儿子的size就行。

    转载于:https://www.cnblogs.com/p0ny/p/8111567.html

    展开全文
  • 01Trie是什么?它是一种较为特殊的权值线段树,可以解决一类与按位运算有关的问题。

    之前一直不把Trie当回事,直到今天看了篇博客,据说01trie可以当平衡树使?然后就学了学,发现和权值线段树也没什么区别

    01Trie

    权值线段树的本质是一棵01Trie
    01Trie就是把数字的二进制位从高到低当做字符串扔进Trie里
    巨佬一眼就能看出,把最高位是0的当做左儿子,最高位是1的当做右儿子,这玩意就是权值线段树。
    只是01Trie的边界有一些特性其实权值线段树也能实现,可以用来做一些按位运算的题。当然,权值线段树能实现的所有功能它都能实现。

    例题:【模板】普通平衡树

    做法:就和权值线段树做法是一样的。这题中平衡树能实现的功能01Trie也都能实现
    妈妈再也不用教我写平衡树了
    好吧平衡树还是有独特的功能的,比如区间翻转。
    方法就和权值线段树实现一样。
    感觉代码硬生生地比splay少了rotate和splay函数。
    应该很好懂的 自认码风比较友好
    代码:

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std; 
    
    const int Q = 1e7; 
    struct tree
    {
    	int ch[2], size, end; 
    }; 
    struct Trie
    {
    	tree b[4000005]; 
    	int cnt; 
    	
    	Trie()
    	{
    		memset(b, 0, sizeof(b)); 
    		cnt = 1; 
    	}
    	void insert(int x)
    	{
    		int p = 1; 
    		for(int i = 30; i >= 0; i--)
    		{
    			int f = ((x & (1 << i)) >> i); 
    			if(!b[p].ch[f])b[p].ch[f] = ++cnt; 
    			p = b[p].ch[f]; b[p].size++; 
    		}
    		b[p].end++; 
    	}
    	void del(int x)
    	{
    		int p = 1; 
    		for(int i = 30; i >= 0; i--)
    		{
    			int f = ((x & (1 << i)) >> i); 
    			if(!b[p].ch[f])b[p].ch[f] = ++cnt; 
    			p = b[p].ch[f]; b[p].size--; 	
    		}
    		b[p].end--; 
    	}
    	int get_sum(int x)
    	{
    		int p = 1; 
    		for(int i = 30; i >= 0; i--)
    		{
    			int f = ((x & (1 << i)) >> i); 
    			p = b[p].ch[f]; 
    			if(!p)return 0; 
    		}
    		return b[p].end; 		
    	}
    	int get_rank(int x)
    	{
    		int ret = 0, p = 1, tmp = 0; 
    		for(int i = 30; i >= 0; i--)
    		{
    			int f = ((x & (1 << i)) >> i); 
    			if(f)
    				ret += b[b[p].ch[0]].size; 
    			p = b[p].ch[f]; tmp = (tmp << 1 | f); 				
    		}
    		return ret + 1; 
    	}
    	
    	int get_Kth(int k)
    	{
    		int ret = 0, p = 1; 
    		for(int i = 30; i >= 0; i--)
    		{
    			int t = b[b[p].ch[0]].size; 
    			if(k <= t)
    				p = b[p].ch[0]; 
    			else
    			{
    				k -= t; 
    				p = b[p].ch[1]; 
    				ret += (1 << i); 
    			}			
    		}
    		return ret; 
    	}
    	int get_fr(int x)
    	{
    		return get_Kth(get_rank(x) - 1); 
    	}
    	int get_nx(int x)
    	{
    		return get_Kth(get_rank(x) + get_sum(x)); 
    	}
    }T; 
    int main()
    {
    	int n, opt, x; 
    	scanf("%d", &n); 
    	
    	for(int i = 1; i <= n; i++)
    	{
    		scanf("%d%d", &opt, &x); 
    		if(opt == 1)
    			T.insert(x + Q); 
    		else if(opt == 2)
    			T.del(x + Q); 
    		else if(opt == 3)
    			printf("%d\n", T.get_rank(x + Q)); 
    		else if(opt == 4)
    			printf("%d\n", T.get_Kth(x) - Q); 
    		else if(opt == 5)
    			printf("%d\n", T.get_fr(x + Q) - Q); 
    		else
    			printf("%d\n", T.get_nx(x + Q) - Q); 
    	} 
    	return 0; 
    }
    
    可持久化01Trie

    其实和主席树没什么区别
    就是边界有了一些特性。

    例题:最大异或和

    做法:设sns_n = a1a_1 xorxor a2a_2 xorxor ...... xorxor ana_n
    apa_p xorxor ap+1a_{p + 1} xorxor ...... xorxor ana_n = sp1s_{p - 1} xorxor sns_n
    于是我们发现,这里的sns_n是个常量,只需在添加数的时候计算一下即可
    于是我们只需要求max(simax(s_i xorxor (snxorx))(s_n xor x)),其中l1&lt;=i&lt;=r1l - 1 &lt;= i &lt;= r - 1
    可持久化01Trie。从高往低能取1就取即可。
    注意特判一下l=1l = 1的情况。
    时间复杂度O(qlogW)O(qlogW)
    代码:

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std; 
    
    const int N = 600005, K = 26; 
    struct tree
    {
    	int ch[2], size, end; 
    }b[N * 27]; 
    int n, m, x, l, r, c; 
    char ch[10]; 
    int T[N], s[N], cnt; 
    
    int update(int t, int x, int k)
    {
    	int p = ++cnt; b[p] = b[t]; b[p].size++; 
    	if(k == -1){b[p].end++; return p; }
    	if(x & (1 << k))
    		b[p].ch[1] = update(b[t].ch[1], x, k - 1); 
    	else
    		b[p].ch[0] = update(b[t].ch[0], x, k - 1); 
    	return p; 
    }
    int query(int p, int q, int x)
    {
    	int k = K, ret = 0; 
    	while(~k)
    	{
    		int f = (x & (1 << k)) >> k; 
    		if(b[b[q].ch[!f]].size - b[b[p].ch[!f]].size)
    		{
    			ret += (1 << k); 
    			p = b[p].ch[!f]; q = b[q].ch[!f]; 
    		}
    		else
    		{
    			p = b[p].ch[f]; q = b[q].ch[f]; 
    		}
    		k--; 
    	}
    	return ret; 
    }
    int main()
    {
    	scanf("%d%d", &n, &m); 
    	
    	for(int i = 1; i <= n; i++)
    	{
    		scanf("%d", &x); 
    		s[i] = s[i - 1] ^ x; 
    		T[i] = update(T[i - 1], s[i], K); 
    	}
    	for(int i = 1; i <= m; i++)
    	{
    		scanf("%s", ch); 
    		if(ch[0] == 'A')
    		{
    			scanf("%d", &x); 
    			n++; s[n] = s[n - 1] ^ x; 
    			T[n] = update(T[n - 1], s[n], K); 
    		}
    		else
    		{
    			scanf("%d%d%d", &l, &r, &x); 
    			if(l == r)
    				printf("%d\n", s[l - 1] ^ s[n] ^ x); 
    			else
    				printf("%d\n", query(T[(l - 2 >= 0) ? (l - 2) : 0], T[r - 1], s[n] ^ x)); 
    		}
    	}
    	return 0; 
    }
    

    结语:01Trie本质上与权值线段树并无差异,只是有了二进制位的特性,还有就是01Trie较为容易写非递归版本,常数上稍稍好一些。可持久化01Trie可以解决与按位运算有关的一类问题。

    展开全文
  • 01 Trie 专题

    2020-11-19 20:52:13
    01 Trie 专题 异或最大值 The xor largest pair 题意: 异或最大值的模板。一个数和一个序列中一个数的异或最大值是多少?要支持询问。 思路:考虑把序列插入,构建一个 Trie\text{Trie}Trie 树。那么在询问时,只...

    01 Trie 专题

    异或最大值

    The xor largest pair

    题意: 异或最大值的模板。一个数和一个序列中一个数的异或最大值是多少?要支持询问。

    思路:考虑把序列插入,构建一个 Trie\text{Trie} 树。那么在询问时,只需要讨论该数的位是 00 还是 11 就行了。这样就需要 O(nlogw)O(n\log w) 的预处理,O(logw)O(\log w) 的询问和修改,为什么是对的。因为异或中我们如果可以满足最高位,那么没有理由不改变最高位,因为 2bit>i=0i<bit2i2^{bit} >\sum_{i=0}^{i < bit}2^i 。那么由高位到地位贪心就可以了。

    /*
    https://ac.nowcoder.com/acm/problem/50993
    */
    #include<bits/stdc++.h>
    using namespace std;
    
    const int maxn = 2e6 + 100;
    int ch[maxn][2];
    
    int sz = 0, rt, n;
    
    int read() {int x; scanf("%d", &x); return x;}
    
    void insert(int u, int t, int x){
        if(t < 0) return;
        int f = ((x >> t) & 1);
        if(!ch[u][f]) ch[u][f] = ++sz;
        insert(ch[u][f], t-1, x);
    }
    
    int ask(int u, int t, int x){
        if(t < 0) return 0;
        int f = ((x >> t) & 1);
        if(ch[u][!f]) return ask(ch[u][!f], t-1, x) + (1 << t);
        
        return ask(ch[u][f], t-1, x);
    }
    
    int main(){
        n = read();
        int ans = 0;
        rt = ++ sz;
        for(int i = 0; i < n; i++){
            int x = read();
            insert(rt, 30, x);
            if(i != 0) ans = max(ans, ask(rt, 30, x));
        }
        printf("%d\n", ans);
        return 0;
    }
    

    Xor Sum

    Problem Description

    Zeus 和 Prometheus 做了一个游戏,Prometheus 给 Zeus 一个集合,集合中包含了N个正整数,随后 Prometheus 将向 Zeus 发起M次询问,每次询问中包含一个正整数 S ,之后 Zeus 需要在集合当中找出一个正整数 K ,使得 K 与 S 的异或结果最大。Prometheus 为了让 Zeus 看到人类的伟大,随即同意 Zeus 可以向人类求助。你能证明人类的智慧么?

    Input

    输入包含若干组测试数据,每组测试数据包含若干行。
    输入的第一行是一个整数TT<10T(T < 10),表示共有T组数据。
    每组数据的第一行输入两个正整数NM<1=N,M<=100000N,M(<1=N,M<=100000),接下来一行,包含N个正整数,代表 Zeus 的获得的集合,之后M行,每行一个正整数S,代表 Prometheus 询问的正整数。所有正整数均不超过2322^{32}

    Output

    对于每组数据,首先需要输出单独一行”Case #?:”,其中问号处应填入当前的数据组数,组数从1开始计算。
    对于每个询问,输出一个正整数K,使得K与S异或值最大。

    Sample Input

    2
    3 2
    3 4 5
    1 5
    4 1
    4 6 5 6
    3
    

    Sample Output

    Case #1:
    4
    3
    Case #2:
    4
    

    同上题,简单板子

    代码
    /*
    http://acm.hdu.edu.cn/showproblem.php?pid=4825
    */
    #include<bits/stdc++.h>
    using namespace std;
    
    int read(){int x; scanf("%d", &x); return x;}
    
    const int maxn = 5e6 + 10;
    int ch[maxn][2], value[maxn];
    int a[maxn];
    int sz = 1, rt = 1;
    int m, n, t, T;
    
    void insert(int u, int t, int x){
        if(t < 0) { value[u] = x; return; }
        int i = (x >> t) & 1;
        if(!ch[u][i]) ch[u][i] = ++sz;
        insert(ch[u][i], t - 1, x);
    }
    
    int query(int u, int t, int x){
        if(t < 0) return value[u];
        int i = (x >> t) & 1;
        if(ch[u][!i]) return query(ch[u][!i], t-1, x);
        return query(ch[u][i], t - 1, x);
    }
    
    void solve(){
        n = read(); m = read();
        memset(ch, 0, sizeof ch);
        sz = rt = 1;
        memset(value, 0, sizeof value);
        for(int i = 1; i <= n; i++) a[i] = read(), insert(rt, 31, a[i]);
    
        printf("Case #%d:\n", t - 1);
        for (int i = 1; i <= m; i++){
            int s = read();
            printf("%d\n", query(rt, 31, s));
        }
    }
    
    int main(){
        t = 1; T = read();
        while(t++ <= T) solve();
        return 0;
    }
    

    异或最小值

    Vitya and Strange Lesson

    (a1,a2,a3..an)AB(a_1,a_2,a_3..a_n) \oplus A\oplus B 根据结合率,等价于 (a1,a2,a3..an)(AB)(a_1,a_2,a_3..a_n) \oplus (A\oplus B)

    因为我们要求的是 mexmex ,那么我们就考虑 00mex1mex-1 的数是否全部出现过。那么就变为查询异或最小值了,我们在构建 01 Trie\text{01 Trie} 时要顺便记录 Trie\text{Trie} 中的元素个数,也就是szsz,当一个节点的元素个数填满时,我们是不能考虑的。

    /*
    https://ac.nowcoder.com/acm/problem/112209
    */
    #include<bits/stdc++.h>
    using namespace std;
    
    const int maxn = 6e6 + 10;
    int read(){ int x; scanf("%d", &x); return x;}
    int sz[maxn], ch[maxn][2];
    int size = 1, rt = 1;
    int n, m, last;
    
    void insert(int u, int t, int x){
        if(t < 0){sz[u] = 1; return;}
        int i = (x >> t) & 1;
        if(!ch[u][i]) ch[u][i] = ++size;
        insert(ch[u][i], t - 1, x);
        sz[u] = sz[ch[u][i]] + sz[ch[u][!i]];
    }
    int query(int u, int t, int x){
        if(t < 0 || u == 0) return 0;
        int i = (x >> t) & 1;
        if((1 << t) != sz[ch[u][i]]) return query(ch[u][i], t - 1, x);
        else return query(ch[u][!i], t - 1, x) + (1 << t);
    }
    
    int main(){
        n = read(); m = read(); 
        for(int i = 1; i <= n; i++) insert(rt, 20, read());
        while(m--){
            last ^= read();
            printf("%d\n", query(rt, 20, last));
        }
        return 0;
    }
    

    保存值的异或最大值

    奶牛异或

    aa=0a\oplus a = 0 ,我们可以考虑做一次前缀异或和。那么区间操作就变为单点操作了。

    /*
    https://ac.nowcoder.com/acm/problem/22998
    */
    #include<bits/stdc++.h>
    using namespace std;
    
    const int maxn = 2e7 + 100;
    int ch[maxn][2], id[maxn], a[maxn];
    
    int sz = 0, rt, n;
    int ans1, ans2 = 1, ans3 = 1;
    
    int read() {int x; scanf("%d", &x); return x;}
    
    void insert(int u, int t, int x, int ID){
        if(t < 0){ id[u] = ID; return; }
        int f = ((x >> t) & 1);
        if(!ch[u][f]) ch[u][f] = ++sz;
        insert(ch[u][f], t-1, x, ID);
    }
    
    int ask(int u, int t, int x){
        if(t < 0) return id[u];
        int f = ((x >> t) & 1);
        if(ch[u][!f]) return ask(ch[u][!f], t-1, x);
        
        return ask(ch[u][f], t-1, x);
    }
    
    int main(){
        n = read(); a[0] = 0;
        for(int i = 1; i <= n; i++) (a[i] = a[i-1] ^ read());
        rt = ++ sz;
        for(int i = 1; i <= n; i++){
            insert(rt, 22, a[i-1], i);
            int x = ask(rt, 22, a[i]) - 1;
            if(ans1 < (a[x] ^ a[i])){
                ans1 = (a[x] ^ a[i]);
                ans2 = x + 1;
                ans3 = i;
            }
        }
        printf("%d %d %d\n", ans1, ans2, ans3);
        return 0;
    }
    

    带删除的异或最小值

    Perfect Security

    我们在01 Trie\text{01 Trie} 上再维护一个szisz_i 标记,表示是否这个节点下还有没有可用元素。那么删除和插入都只会影响一条链。

    /*
    https://ac.nowcoder.com/acm/problem/112567 
    */
    #include<bits/stdc++.h>
    using namespace std;
    
    int read(){int x; scanf("%d", &x); return x;}
    
    const int maxn = 6e6 + 10;
    int ch[maxn][2], sz[maxn];
    int size = 0, rt = 0;
    int n, m;
    int a[maxn], b[maxn], c[maxn];
    
    void insert(int u, int t, int x){
        if(t < 0) return;
        int i = (x >> t) & 1;
        if(!ch[u][i])  ch[u][i] = ++size;;
        sz[ch[u][i]]++;
        insert(ch[u][i], t - 1, x);
    }
    
    void erase(int u, int t, int x){
        if(t < 0) return;
        int i = (x >> t) & 1;
        sz[ch[u][i]]--;
        erase(ch[u][i], t - 1, x);
    }
    
    int query(int u, int t, int x){
        if(t < 0) return 0;
        int i = (x >> t) & 1;
        if(sz[ch[u][i]]) return query(ch[u][i], t-1, x) + (i << t);
        else return query(ch[u][!i], t-1, x) + ((!i) << t);
    }
    int main(){
        n = read(); 
        for(int i = 1; i <= n; i++) a[i] = read();
        for(int i = 1; i <= n; i++) b[i] = read(), insert(rt, 30, b[i]);
    
        for(int i = 1; i <= n; i++){
            int x = query(rt, 30, a[i]);
            printf("%d\n", a[i] ^ x);
            erase(rt, 30, x);
        }
        return 0;
    }
    

    带删除的异或最大值

    D. Vasiliy’s Multiset

    题意

    初始有个一个空集,n个操作,操作分三种

    • +x,将一个 x 加入集合
    • -x,删除集合内的一个 x
    • ?x,询问集合中与 x 异或的最大值
    代码
    #include<bits/stdc++.h>
    using namespace std;
    
    const int maxn = 6e6 + 10;
    int ch[maxn][2], sz[maxn], val[maxn], cnt[maxn];
    int size = 0, rt = 0;
    int n, m;
    
    void insert(int u, int t, int x){
        if(t < 0) { val[u] = x; return;}
        int i = (x >> t) & 1;
        if(!ch[u][i])  ch[u][i] = ++size;
        sz[ch[u][i]]++;
        insert(ch[u][i], t - 1, x);
    }
    
    void erase(int u, int t, int x){
        if(t < 0) return;
        int i = (x >> t) & 1;
        sz[ch[u][i]]--;
        erase(ch[u][i], t - 1, x);
    }
    
    int query(int u, int t, int x){
        if(t < 0) return val[u];
        int i = (x >> t) & 1;
        if(sz[ch[u][!i]]) return query(ch[u][!i], t-1, x);
        else return query(ch[u][i], t-1, x);
    }
    
    int main(){
        cin >> n;
        
        for(int i = 1; i <= n; i++){
            char c; cin >> c;
            int t; cin >> t;
            if(c == '+') insert(rt, 30, t);
            else if(c == '-') erase(rt, 30, t);
            else  printf("%d\n", max(t, query(rt, 30, t) ^ t));
        }
        return 0;
    }
    /*
    12
    ? 1
    + 1
    + 4
    ? 5
    ? 6
    */
    
    展开全文
  • 01trie树学习笔记

    2021-01-01 11:33:51
    01trie树学习笔记问题引入什么是01trie树问题解答两个扩展例题1.第kkk大异或和2.树上最大异或路径 问题引入 给一个长为nnn的数列,要求一个aia_iai​,aja_jaj​,使得aixoraja_i xor a_jai​xoraj​最大。 什么是01...
  • 可持久化 01Trie

    2020-09-27 20:18:04
    01TrieP4551 最长异或路径 (01trie) P4551 最长异或路径 (01trie) 链接:https://www.luogu.com.cn/problem/P4551 题意:给定一棵 nnn 个点的带权树,结点下标从 1 开始到 n 。寻找树中找两个结点,求最长的异或...
  • 01Trie学习笔记

    2019-10-03 19:49:23
    \(01Trie\)学习笔记 前置知识: \(Trie\)树 \(xor\)的一些性质 \(xor\)对于\(0\)和\(1\),两个数相同返回\(0\),不同返回\(1\) 所以我们可以得到一些很有意思的结论 \[0\ xor\ 1\ =\ 1\] \[1\ xor\ 1\ =\ 0\] \[p...
  • 可持久化01Trie

    2019-09-24 04:12:15
    建可持久化01Trie。 每次建一个新版本把序列的每个前缀和插进去。 添加操作亦如此。 查询的话就看每个数位取反的一侧在01Trie的这个区间内是否出现过(也就是\(sum\)是否相等),然后跳儿子。 这里蕴含了高位贪心的...
  • 三元组[01 Trie计数]

    2019-09-23 20:24:22
    也许更好的阅读体验 Description\mathcal{Description}Description Solution\mathcal{Solution}Solution 有两种方法都可以拿到满分 ...建两个01Trie01Trie01Trie,要支持删除操作 一颗TrieTrieTrie维护y...
  • 最长异或路径 板子题,但是如果把边权改成了点权的话好像就不好...最大异或对就没啥说的了,按顺序(随便什么顺序)把每个点加入01trie01trie01trie中,然后在每加入一个点前先判定当前点能与01trie01trie01trie中异...
  • cf706d 01trie

    2017-03-09 14:30:26
    **思路**01trie,这个trie的方法就是你每次都用一个0,或者1来当字典,然后你每次查找的时候用一个贪心的思想去查找。,。,。,。能1就尽量取,如果实在没招也只能取0,最后就得到一个值,输出出来就好了。以前的...
  • HDU 5536 Chip Factory 01trie

    2017-08-28 17:22:03
    题目:http://acm.hdu.edu.cn/showproblem.php?pid=5536题意:给出nn个数,从这些数字中任选33个不同...然后正解是用字典树去求最大异或值,首先把nn个数字插入到01trie01trie中,然后枚举x+yx+y,首先从字典树中删掉x,
  • 把每个前缀异或和依次插入$01trie$,插之前找一个最优的(就是从高位向低位贪心,尽量走相反方向)看看能不能更新答案,此时相当于找到了区间右端点不超过某个点$r$的最大或和$f[r]$。对于后缀也同理来一波上面的操作...
  • Nikitosh和异或 因为下面这段代码卡了接近一小时! int s=p&1<<i; // wrong int s=p>>...题意:最大化两个异或对之和(还是看...当然整个过程都利用了01trie01trie01trie性质,即在已经构建的01trie...
  • Trie树 & 01Trie

    2016-10-05 00:36:00
    指针版 #define MAXNUM 26 //定义字典树结构体 typedef struct Trie { bool flag;//从根到此是否为一个单词 Trie *next[MAXNUM]; }Trie; ...Trie *root;... root = (Trie *)malloc(siz...
  • 最大异或和 题意:转化后的题意是有一种操作+一种询问: 1. 操作:在序列末尾插入一个数 2. 询问:给定l,r,xl,r,xl,r,x,求区间l,rl,rl,r中与xxx...然后还是简单的贪心跑01trie01trie01trie 最后小心给定的l,rl,r...
  • 01Trie树模板 - 亦或最小生成树 CF888G Xor-MST 题意 给定一个有nnn个结点的图的点权 连每两个点的边权是两端点点权的亦或值 求该图最小生成树值和 数据范围: 1≤n≤2×105,ai≤2301\leq n\leq 2\times 10^5 , a...
  • 思路:这题可以暴力也可以01trie. 来说说01trie. 其实遇到异或求最大最小啊啥的都可以想01trie是否可做. 那么这个题肯定就是枚举两个和,然后跑01trie了.关键是怎么解决下标不同的问题,这里解决办法是增加一个del...
  • HDU 5536 01Trie

    2015-11-04 23:00:19
    HDU 5536 题目链接: ...题意: 1000个数里面,选三个下标不同的数构成函数(ai+aj)^ak。...01Trie的话本质是贪心,把所有数按照二进制插入Trie里,枚举i和j,然后每次用32的常数级查询就能得到对应最大值
  • Codechef REBXOR(01Trie)

    2017-10-12 19:26:48
    01Trie mu版题emmmmm题目(手打) 一个序列A,求两个不相交的区间,使得异或和之和最大 对于100%的数据,2∗1054*10^5,0^9。#include #include #include #include #include #include <al

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 766
精华内容 306
关键字:

01trie