[一本通学习笔记] 字典树与 0-1 Trie

字典树中根到每个结点对应原串集合的一个前缀，这个前缀由路径上所有转移边对应的字母构成。我们可以对每个结点维护一些需要的信息，这样即可以去做很多事情。

#10049. 「一本通 2.3 例 1」Phone List

#include <bits/stdc++.h>

using namespace std;

namespace Trie {

    struct Node {

        Node *ch[];

        int val;

        Node* clear() {

            for(int i=;i<;i++) ch[i]=NULL;

            val=;

            return this;

        }

    };

    Node *root;

    Node pool[];

    int ind=;

    Node* newnode() {

        return pool[ind++].clear();

    }

    void clear() {

        ind=;

        root=newnode();

    }

    void insert(string s) {

        Node *pos=root;

        for(int i=;i<s.length();i++) {

            if(pos->ch[s[i]]==NULL) pos->ch[s[i]]=newnode();

            pos->val++;

            pos=pos->ch[s[i]];

        }

    }

    int query(string s) {

        Node *pos=root;

        for(int i=;i<s.length();i++) {

            if(pos->ch[s[i]]==NULL) return ;

            pos=pos->ch[s[i]];

        }

        return pos->val;

    }

    string str[];

    void solve() {

        int n;

        cin>>n;

        clear();

        for(int i=;i<=n;i++) {

            cin>>str[i];

            for(int j=;j<str[i].length();j++) str[i][j] -= '';

            insert(str[i]);

        }

        int flag=;

        for(int i=;i<=n;i++) {

            if(query(str[i])) {

                flag=;

                break;

            }

        }

        if(flag) cout<<"NO"<<endl;

        else cout<<"YES"<<endl;

    }

}

int main() {

    int t;

    ios::sync_with_stdio(false);

    cin>>t;

    while(t--) Trie::solve();

    return ;

}

#10050. 「一本通 2.3 例 2」The XOR Largest Pair

0-1 Trie通常用于异或相关的问题，思路是记录所有01串后，我们找最大异或和的时候可以从高位到低位贪心，此时Trie发挥的作用就是在当前前缀已经选择的情况下，能使得正在考虑位异或为1的后缀是否存在。

#include <bits/stdc++.h>

using namespace std;

namespace Trie {

struct Node {

    Node *ch[];

    Node *clear() {

        ch[] = ch[] = ;

        return this;  // Don't forget this

    }

};

Node *root;

Node pool[];

int ind;

Node *newnode() { return pool[ind++].clear(); }

void insert(int x) {

    Node *pos = root;

    for (int i = ; i >= ; --i) {

        int b = (x / ( << i)) & ;

        if (pos->ch[b] == NULL)

            pos->ch[b] = newnode();

        pos = pos->ch[b];

    }

}

int query(int x) {

    Node *pos = root;

    int ans = ;

    for (int i = ; i >=  && pos != NULL; --i) {

        int b = (x / ( << i)) & ;

        if (pos->ch[b ^ ] != NULL)

            pos = pos->ch[b ^ ], ans += ( << i);

        else

            pos = pos->ch[b];

    }

    return ans;

}

int a[];

void solve() {

    int n, ans = ;

    cin >> n;

    root = newnode();  // Don't forget this

    for (int i = ; i <= n; i++) cin >> a[i], insert(a[i]);

    for (int i = ; i <= n; i++) ans = max(ans, query(a[i]));

    cout << ans << endl;

}

}  // namespace Trie

int main() {

    ios::sync_with_stdio(false);

    Trie::solve();

}

#10051. 「一本通 2.3 例 3」Nikitosh 和异或

看到这个算式我们很容易想到前缀和转化。问题转化为求s[r1]^s[l1-1] + s[r2]^s[l2-1]最大。

由于要r1<l2，所以可考虑去处理出一个前缀max和一个后缀max，然后枚举分界点。那么答案就是

Max{pre[i]+suf[i+1]}

#include <bits/stdc++.h>

using namespace std;

namespace Trie {

struct Node {

    Node *ch[];

    Node *clear() {

        ch[] = ch[] = ;

        return this;  // Don't forget this

    }

};

Node *root;

Node pool[];

int ind;

Node *newnode() { return pool[ind++].clear(); }

void insert(int x) {

    Node *pos = root;

    for (int i = ; i >= ; --i) {

        int b = (x / ( << i)) & ;

        if (pos->ch[b] == NULL)

            pos->ch[b] = newnode();

        pos = pos->ch[b];

    }

}

int query(int x) {

    Node *pos = root;

    int ans = ;

    for (int i = ; i >=  && pos != NULL; --i) {

        int b = (x / ( << i)) & ;

        if (pos->ch[b ^ ] != NULL)

            pos = pos->ch[b ^ ], ans += ( << i);

        else

            pos = pos->ch[b];

    }

    return ans;

}

int a[], pre[], suf[];

void solve() {

    int n, ans = ;

    cin >> n;

    root = newnode();  // Don't forget this

    for (int i = ; i <= n; i++) cin >> a[i], insert(a[i]), pre[i] = max(pre[i - ], query(a[i]));

    ind = ;

    root = newnode();

    reverse(a + , a + n + );

    for (int i = ; i <= n; i++) insert(a[i]), suf[i] = max(suf[i - ], query(a[i]));

    reverse(suf + , suf + n + );

    for (int i = ; i < n; i++) ans = max(ans, pre[i] + suf[i + ]);

    cout << ans << endl;

}

}  // namespace Trie

int main() {

    ios::sync_with_stdio(false);

    Trie::solve();

}

#10052. 「一本通 2.3 练习 1」Immediate Decodability

和前面那题一样

#include <bits/stdc++.h>

using namespace std;

namespace Trie {

struct Node {

    Node *ch[];

    int val;

    Node *clear() {

        for (int i = ; i < ; i++) ch[i] = NULL;

        val = ;

        return this;

    }

};

Node *root;

Node pool[];

int ind = ;

Node *newnode() { return pool[ind++].clear(); }

void clear() {

    ind = ;

    root = newnode();

}

void insert(string s) {

    Node *pos = root;

    for (int i = ; i < s.length(); i++) {

        if (pos->ch[s[i]] == NULL)

            pos->ch[s[i]] = newnode();

        pos->val++;

        pos = pos->ch[s[i]];

    }

}

int query(string s) {

    Node *pos = root;

    for (int i = ; i < s.length(); i++) {

        if (pos->ch[s[i]] == NULL)

            return ;

        pos = pos->ch[s[i]];

    }

    return pos->val;

}

string str[];

bool solve(int t) {

    clear();

    int n = ;

    while (cin >> str[++n]) {

        if (str[n][] == '')

            break;

        for (int j = ; j < str[n].length(); j++) str[n][j] -= '';

        insert(str[n]);

    }

    --n;

    if (n <= )

        return false;

    int flag = ;

    for (int i = ; i <= n; i++) {

        if (query(str[i])) {

            flag = ;

            break;

        }

    }

    if (flag)

        cout << "Set " << t << " is not immediately decodable" << endl;

    else

        cout << "Set " << t << " is immediately decodable" << endl;

    return true;

}

}  // namespace Trie

int main() {

    int t = ;

    ios::sync_with_stdio(false);

    while (Trie::solve(++t))

        ;

    return ;

}

#10053. 「一本通 2.3 练习 2」L 语言

我们记录u[i]表示文章的每一个前缀s[1..i]是否可被理解。做一个类似dp的处理即可。

刚开始忘记传引用T了半天……

#include <bits/stdc++.h>

using namespace std;

char buf[];

void readstr(string &tar) {

    scanf("%s", buf);

    tar = buf;

}

int __cnt = ;

namespace Trie {

struct Node {

    Node *ch[];

    int val;

    Node *clear() {

        for (int i = ; i < ; i++) ch[i] = NULL;

        val = ;

        return this;

    }

};

Node *root;

Node pool[];

int u[];

int ind = , ans = ;

Node *newnode() { return pool[ind++].clear(); }

void clear() {

    ind = ;

    root = newnode();

}

void insert(string &s) {

    Node *pos = root;

    for (int i = ; i < s.length(); i++) {

        if (pos->ch[s[i]] == NULL)

            pos->ch[s[i]] = newnode();

        pos = pos->ch[s[i]];

    }

    pos->val++;

}

void query(string &s, int start) {

    Node *pos = root;

    int len = s.length();

    for (int i = start; i < len; i++) {

        __cnt++;

        if (pos->ch[s[i]] == NULL)

            return;

        pos = pos->ch[s[i]];

        if (pos->val)

            u[i + ] = , ans = max(ans, i + );

    }

}

string str[];

string art;

void solve() {

    int n, m;

    scanf("%d%d", &n, &m);

    clear();

    for (int i = ; i <= n; i++) {

        readstr(str[i]);

        for (int j = ; j < str[i].length(); j++) str[i][j] -= 'a';

        insert(str[i]);

    }

    for (int i = ; i <= m; i++) {

        ans = ;

        memset(u, , sizeof u);

        readstr(art);

        int len = art.length();

        for (int j = ; j < len; j++) art[j] -= 'a';

        u[] = ;

        for (int j = ; j < len; j++) {

            if (u[j] == )

                continue;

            query(art, j);

        }

        cout << ans << endl;

    }

}

}  // namespace Trie

int main() {

    int t;

    ios::sync_with_stdio(false);

    Trie::solve();

    // cout<<__cnt<<endl;

    return ;

}

#10054. 「一本通 2.3 练习 3」Secret Message 秘密信息

对信息建Trie，仍然是在每个串的结束点上打标记。结果就等于把密码串丢上去跑，跑的路径上的标记和，加上最终停在的结点（如果整个密码串都成功匹配）的子树的标记和。前一个直接记录，后一个用树上前缀和预处理一下即可。

#include <bits/stdc++.h>

using namespace std;

namespace Trie {

struct Node {

    Node *ch[];

    int val, sum;

    Node *clear() {

        for (int i = ; i < ; i++) ch[i] = NULL;

        val = sum = ;

        return this;

    }

};

Node *root;

Node pool[];

int ind = ;

Node *newnode() { return pool[ind++].clear(); }

void clear() {

    ind = ;

    root = newnode();

}

void insert(int len) {

    Node *pos = root;

    for (int i = ; i < len; i++) {

        int si;

        cin >> si;

        if (pos->ch[si] == NULL)

            pos->ch[si] = newnode();

        pos = pos->ch[si];

    }

    pos->val++;

}

void dfs(Node *p) {

    if (p == NULL)

        return;

    dfs(p->ch[]);

    dfs(p->ch[]);

    p->sum = p->val;

    if (p->ch[])

        p->sum += p->ch[]->sum;

    if (p->ch[])

        p->sum += p->ch[]->sum;

}

int query(int len) {

    Node *pos = root;

    int ans = ;

    for (int i = ; i < len; i++) {

        int si;

        cin >> si;

        ans += pos->val;

        if (pos->ch[si] == NULL) {

            for (int j = ; j <= len - i - ; j++) cin >> si;

            return ans;

        }

        pos = pos->ch[si];

    }

    return ans + pos->sum;

}

string str[];

void solve() {

    int m, n;

    cin >> m >> n;

    clear();

    for (int i = ; i <= m; i++) {

        int len;

        cin >> len;

        insert(len);

    }

    dfs(root);

    for (int i = ; i <= n; i++) {

        int len;

        cin >> len;

        cout << query(len) << endl;

    }

}

}  // namespace Trie

int main() {

    int t;

    ios::sync_with_stdio(false);

    Trie::solve();

    return ;

}

#10056. 「一本通 2.3 练习 5」The XOR-longest Path

树上前缀异或和以后直接转化为两点最大异或和。其实用欧拉序也可以。

#include <bits/stdc++.h>

using namespace std;

namespace Trie {

    struct Node {

        Node *ch[];

        Node* clear() {

            ch[]=ch[]=;

            return this; // Don't forget this

        }

    };

    Node *root;

    Node pool[];

    int ind;

    Node* newnode() {

        return pool[ind++].clear();

    }

    void insert(int x) {

        Node *pos = root;

        for(int i=;i>=;--i) {

            int b=(x/(<<i))&;

            if(pos->ch[b]==NULL) pos->ch[b]=newnode();

            pos=pos->ch[b];

        }

    }

    int query(int x) {

        Node *pos = root;

        int ans = ;

        for(int i=;i>= && pos!=NULL;--i) {

            int b=(x/(<<i))&;

            if(pos->ch[b^]!=NULL)

                pos=pos->ch[b^], ans+=(<<i);

            else pos=pos->ch[b];

        }

        return ans;

    }

    int a[];

    void solve(int n) {

        int ans=;

        root=newnode(); // Don't forget this

        for(int i=;i<=n;i++) insert(a[i]);

        for(int i=;i<=n;i++) ans=max(ans,query(a[i]));

        cout<<ans<<endl;

    }

}

int n,vis[];

vector<pair<int,int> > g[];

void dfs(int p) {

    vis[p]=;

    for(int i=;i<g[p].size();i++) {

        int q=g[p][i].first;

        if(vis[q]==) {

            Trie::a[q]=Trie::a[p] ^ g[p][i].second;

            dfs(q);

        }

    }

}

int main() {

    ios::sync_with_stdio(false);

    cin>>n;

    for(int i=;i<n;i++) {

        int u,v,w;

        cin>>u>>v>>w;

        g[u].push_back(make_pair(v,w));

        g[v].push_back(make_pair(u,w));

    }

    dfs();

    Trie::solve(n);

}