Trie——解決字符串搜索、異或最值問題

Trie——解決字符串搜索、異或最值問題

  • 在說到Trie之前,我們設想如下問題:

給我們1e5個由小寫字母構成的不重復的字符串,每個字符串長度不超過6,之后是1e5次查詢操作,每次給我們一個字符串,要求我們判斷這個字符串是否出現過,如果是則求出它是多少個其他的字符串的前綴,并在之后的操作中無視這個字符串(刪除)。

  • 查詢是否出現這個可以用set或者hash,但是前綴,,其實也有辦法,但是這里要介紹的方法是使用一種易于理解的數據結構——Trie

建立Trie

  • 字典樹Trie的結構比較自然,如對于字符串集合{"abca", "ab", "bcd", "abcde", "bcde", "bcdf"},可以建立一棵這樣的Trie:

可知:

- 每一條邊代表一個字符
- 節點不為0代表從根節點到此為一個完整的字符串

實現的方法也比較簡單,建立一棵單向樹,每個節點都有

  • 26個子節點(所有小寫字母);

  • 一個isstr,bool值,代表這里是否為一個字符串的結束

  • 一個vis,int值,代表到這里已經有多少個字符串遍歷過(是多少字符串的前綴)

一開始樹為空,我們每得到一個字符串,就從它的第一個字符開始,從根節點遍歷,沒有對應的節點就創建,同時把所經過的節點的vis值加一,到最后字符串終止時,在終止的節點處置isstr為true。

更多操作

1.查詢

從樹的形狀就可以看出,這是一棵專門查詢字符串存在與否的數據結構(同時也付出了巨大的空間代價)。查詢操作很簡單,從根節點開始,按照要查詢的字符串的每一位來遍歷,如果遇到空節點或者終止時的節點的isstr為false,則字符串不存在,否則存在。

2.查詢某個串是多少個字符串的前綴

這個就是讀取要查詢的字符串的終止節點的vis值即可

3.刪除某個字符串

首先查詢成功之后,我們從底部開始回溯刪除這個串的信息,將終止節點的isstr置為false,同時將路過的vis值減一,如果vis值減為0則將將此節點在其父節點中刪除即可。

01Trie解決xor最值問題

原題鏈接

題意


給我們一個序列A和序列B,要求我們找到B序列的一種排列,使得

\[C_i \quad xor \quad B_i == A_i \]

中的序列C字典序最小,并輸出序列C,長度<=3e5,每個數小于2^30

思路

  • 首先按照運算規則C xor B == A意味著A xor B == C 也就是說 尋找一種B的排列,使得A逐個與B異或的結果的字典序最小

  • 3e5基本不可能在其他操作中間搞什么排序了,應該從異或運算的結果出發,我們追求結果的字典序最小,也就是說,對于每個Ai,我們都要找到一個Bj,使得其異或結果最小。這個如果直接找的話,是比較難的。但是如果使用Trie的話,可以直接求得每一個Ai的最小結果,方法如下:

    • 對B序列建立一棵只包含01字符的Trie(也就是二叉樹),我們規定A與B的每一個數都是30位二進制數,左邊補零,從左邊的第一位開始建樹。

    • B序列的01Trie建好之后,對A序列從1到n每個數都按位在Trie中遍歷,一開始先設ans為0,之后優先走與當前自己的二進制位相同的邊,如果沒有則讓ans或上這一位的1。(確保ans盡可能地小)

    • 之后輸出這個ans,并將走過的路線所代表的Bi刪除掉就可以

  • 可以看出時間復雜度為

    \[O(30*n) \]

  • 對空間復雜度來說,不要使用滿二叉樹的存儲方式,使用動態開點的方式,空間復雜度不超過

    \[O(30*n) \]

01Trie代碼如下:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int n;
int aa[10000005][2] = {{0}}, vv[10000005][2] = {{0}}, co = 1;
int A[300005] = {0};

void add(int x)
{
	int o = 1;
	for (int i = 29; i >= 0; --i)
	{
		int bitt = (x >> i) & 1;
		if (!aa[o][bitt])
		{
			aa[o][bitt] = ++co;
		}
		++vv[o][bitt];
		o = aa[o][bitt];
	}
}

int trie(int x)
{
	int o = 1, ans = 0;
	for (int i = 29; i >= 0; --i)
	{
		int bitt = (x >> i) & 1;
		if (vv[o][bitt])
		{
			--vv[o][bitt];
			o = aa[o][bitt];
			
		}
		else
		{
			--vv[o][bitt ^ 1];
			o = aa[o][bitt ^ 1];
			ans |= (1 << i);
		}
	}
	return ans;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", &A[i]);
	}
	for (int i = 1; i <= n; ++i)
	{
		int xx;
		scanf("%d", &xx);
		add(xx);
	}
	for (int i = 1; i < n; ++i)
	{
		printf("%d ", trie(A[i]));
	}
	printf("%d", trie(A[n]));
	return 0;
}
posted @ 2020-07-17 19:23  _int_me  閱讀(...)  評論(...編輯  收藏
最新chease0ldman老人|无码亚洲人妻下载|大香蕉在线看好吊妞视频这里有精品www|亚洲色情综合网