Trie樹

模闆帶注釋

// son[][]存儲樹中每個節點的子節點
// cnt[]存儲以每個節點結尾的單詞數量
namespace Trie{
    const int N = 1e5 + 10;
    int son[N][26], cnt[N], idx; // 'son[N][10]'
    void init(){
        memset(son, 0, sizeof son);
        memset(cnt, 0, sizeof cnt);
        idx = 0;
    }
    void insert(char *s){
        int p = 0; // p代表每個節點的下标，現在為根節點
        for(int i = 0; s[i]; ++ i){
            int u = s[i] - 'a'; // '0'代表減數字時
            // u代表p結點的子節點，但不是下标，u和p性質不一樣
            if(!son[p][u]) son[p][u] = ++ idx; // 建立節點，每個節點都有自己的下标
            p = son[p][u]; // 往下走
        }
        cnt[p] ++; // 統計以p下标結尾單詞的數量
    }
    int query(char *s){
        int p = 0;
        for(int i = 0; s[i]; ++ i){
            int u = s[i] - 'a'; // '0'
            if(!son[p][u]) return 0;
            p = son[p][u];
        }
        return cnt[p];
    }
}
using namespace Trie;

無注釋

namespace Trie{
    const int N = 1e5 + 10;
    int son[N][26], cnt[N], idx;
    void init(){
        memset(son, 0, sizeof son);
        memset(cnt, 0, sizeof cnt);
        idx = 0;
    }
    void insert(char *s){
        int p = 0;
        for(int i = 0; s[i]; ++ i){
            int u = s[i] - 'a';
            if(!son[p][u]) son[p][u] = ++ idx;
            p = son[p][u];
        }
        cnt[p] ++;
    }
    int query(char *s){
        int p = 0;
        for(int i = 0; s[i]; ++ i){
            int u = s[i] - 'a';
            if(!son[p][u]) return 0;
            p = son[p][u];
        }
        return cnt[p];
    }
}
using namespace Trie;

Phone List

題意
給定 n n n個長度不超過 10 10 10的數字串，問其中是否存在兩個數字串 S , T S,T S,T，使得 S S S是 T T T的字首，多組資料。

思路

T r i e Trie Trie樹模闆題

正常思路就是把每個字元串都進樹，然後離線處理，這樣時間和空間複雜度都比較大

是以我們可以做到動态查詢

比如 91 91 91和 9134 9134 9134， 91 91 91以 1 1 1結尾，那麼當 9134 9134 9134周遊到 1 1 1時，發現這個下标的 c n t ≠ 0 cnt \ne0 cnt=0，說明前面有單詞 91 91 91，那麼就不符合
比如 9134 9134 9134和 91 91 91， 91 91 91周遊到 1 1 1的時候，發現這個下标的 c n t = 0 cnt = 0 cnt=0，但是 91 91 91是 9134 9134 9134的字首，也不符合要求。要做到這點，隻需要一開始記個 f l a g = f a l s e flag = false flag=false，如果插入的過程中開點了，那麼 f l a g = t u r e flag = ture flag=ture，像剛才就沒有動态開點，是以依然是 f a l s e false false

/*
 * @Author: NEFU AB_IN
 * @Date: 2021-08-26 14:00:53
 * @FilePath: \Vscode\ACM\Project\Trie\Poj3630.cpp
 * @LastEditTime: 2021-08-26 15:25:14
 */
#include<iostream>
#include<vector>
#include<cstring>
#include<string.h>
#include<cstdio>
#include<climits>
#include<cmath>
#include<algorithm>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<string>
#include<stack>
using namespace std;
#define LL                          long long
#define MP                          make_pair
#define SZ(X)                       ((int)(X).size())
#define IOS                         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define DEBUG(X)                    cout << #X << ": " << X << endl;
typedef pair<int , int>             PII;

namespace Trie{
    const int N = 1e5 + 10;
    int son[N][10], cnt[N], idx;
    void init(){
        memset(son, 0, sizeof son);
        memset(cnt, 0, sizeof cnt);
        idx = 0;
    }
    bool insert(char *s){
        int p = 0, flag = 0;
        for(int i = 0; s[i]; ++ i){
            int u = s[i] - '0';
            if(!son[p][u]) son[p][u] = ++ idx, flag = 1;
            p = son[p][u];
            if(cnt[p]) return false;
        }
        cnt[p] ++;
        return flag;
    }
    int query(char *s){
        int p = 0;
        for(int i = 0; s[i]; ++ i){
            int u = s[i] - '0';
            if(!son[p][u]) return 0;
            p = son[p][u];
        }
        return cnt[p];
    }
}
using namespace Trie;

int t;
char s[N];

signed main()
{
    IOS
    cin >> t;
    while(t --){
        init();
        int n, flag = 0;
        cin >> n;
        for(int i = 1; i <= n; ++ i){
            cin >> s;
            if(!insert(s)) flag = 1;
        }
        if(flag) cout << "NO\n";
        else cout << "YES\n";
    }
    return 0;
}

01Trie樹

模闆帶注釋

01 01 01字典樹，每個分支隻有 01 01 01兩個，主要解決異或問題

如果多組資料運用 01 t r i e 01trie 01trie樹時，需要進行初始化，可以像正常 t r i e trie trie樹一樣進行 m e m s e t memset memset操作，但有些題目就會 T T T，這時我們可以采用更好的方法進行初始化。觀察到分支隻有兩個，那麼就可以在建立新分支的同時，對新分支的兩個 01 01 01子節點進行初始化，注意别忘了一開始也要對根節點的子節點進行初始化！

namespace Trie01{
    const int N = 1e5 + 10;
    int son[N * 32][2], val[N * 32], idx; // n個數，每個數最多被拆成不超過32位
    void init(){
        idx = 0;
        son[0][0] = son[0][1] = 0;
        // val沒必要進行初始化，因為是可以覆寫的
    }
    void insert(int x){
        int p = 0;
        for(int i = 31; i >= 0; -- i){ 
            // 貪心時建構01trie樹的基礎，從二進制的高位開始貪心
            int u = (x >> i) & 1;
            if(!son[p][u]){
                son[p][u] = ++ idx;
                p = son[p][u];
                // 構造新節點的同時初始化新節點
                son[p][0] = son[p][1] = 0;
            }
            else p = son[p][u];
        }
        val[p] = x; // 記錄終點
    }
    int query(int x){
        int p = 0;
        for(int i = 31; i >= 0; -- i){
            int u = (x >> i) & 1;
            // 貪心的選擇優先走和目前位不同的路
            if(son[p][u ^ 1]) p = son[p][u ^ 1];
            else p = son[p][u];
        }
        return val[p];
    }
}
using namespace Trie01;

無注釋

namespace Trie01{
    const int N = 1e5 + 10;
    int son[N * 32][2], val[N * 32], idx;
    void init(){
        idx = 0;
        son[0][0] = son[0][1] = 0;
    }
    void insert(int x){
        int p = 0;
        for(int i = 31; i >= 0; -- i){
            int u = (x >> i) & 1;
            if(!son[p][u]){
                son[p][u] = ++ idx;
                p = son[p][u];
                son[p][0] = son[p][1] = 0;
            }
            else p = son[p][u];
        }
        val[p] = x;
    }
    int query(int x){
        int p = 0;
        for(int i = 31; i >= 0; -- i){
            int u = (x >> i) & 1;
            if(son[p][u ^ 1]) p = son[p][u ^ 1];
            else p = son[p][u];
        }
        return val[p];
    }
}
using namespace Trie01;

Xor Sum(hdu4825)

題意
n n n個正整數， m m m次詢問，找一個正整數 K K K，使得 K K K 與 S S S 的異或結果最大

思路

01 T r i e 01Trie 01Trie闆子題

/*
 * @Author: NEFU AB_IN
 * @Date: 2021-08-26 16:40:07
 * @FilePath: \Vscode\ACM\Project\Trie\hdu4825.cpp
 * @LastEditTime: 2021-08-26 22:54:39
 */
#include<bits/stdc++.h>
using namespace std;
#define LL                          long long
#define MP                          make_pair
#define SZ(X)                       ((int)(X).size())
#define IOS                         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define DEBUG(X)                    cout << #X << ": " << X << endl;
typedef pair<int , int>             PII;

namespace Trie01{
    const int N = 1e5 + 10;
    int son[N * 32][2], val[N * 32], idx;
    void init(){
        idx = 0;
        son[0][0] = son[0][1] = 0;
    }
    void insert(int x){
        int p = 0;
        for(int i = 31; i >= 0; -- i){
            int u = (x >> i) & 1;
            if(!son[p][u]){
                son[p][u] = ++ idx;
                p = son[p][u];
                son[p][0] = son[p][1] = 0;
            }
            else p = son[p][u];
        }
        val[p] = x;
    }
    int query(int x){
        int p = 0;
        for(int i = 31; i >= 0; -- i){
            int u = (x >> i) & 1;
            if(son[p][u ^ 1]) p = son[p][u ^ 1];
            else p = son[p][u];
        }
        return val[p];
    }
}
using namespace Trie01;

int t, n, m, x;
signed main()
{
    IOS
    while(~scanf("%d", &t)){
        for(int j = 1; j <= t; ++ j){
            init();
            scanf("%d%d", &n, &m);
            for(int i = 1; i <= n; ++ i){
                scanf("%d", &x);
                insert(x);
            }
            printf("Case #%d:\n", j);
            for(int i = 1; i <= m; ++ i){
                scanf("%d", &x);
                printf("%d\n", query(x));
            }
        }
    }
    return 0;
}

A - L 語言

題意
給出 n n n個字元串構成一個字典 D D D， m m m次詢問，每次詢問一個字元串，輸出這段字元串在字典 D D D可以被了解的最長字首的位置

思路

dp + trie

思路都在注釋中

這裡的查詢函數改了，改成了從字元串的某處開始查詢

主要思路

先，從頭開始進行 d p dp dp，遇到了字首就标記 d p [ ] = 1 dp[] = 1 dp[]=1記作下次 d p dp dp的起點
後，從後往前周遊，最先 d p [ ] = 1 dp[] = 1 dp[]=1的下标就是最佳答案

/*
 * @Author: NEFU AB_IN
 * @Date: 2021-08-27 01:01:30
 * @FilePath: \Vscode\ACM\Project\Trie\L.cpp
 * @LastEditTime: 2021-08-27 01:34:09
 */
#include<bits/stdc++.h>
using namespace std;
#define LL                          long long
#define MP                          make_pair
#define SZ(X)                       ((int)(X).size())
#define IOS                         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define DEBUG(X)                    cout << #X << ": " << X << endl;
typedef pair<int , int>             PII;


namespace Trie{
    const int N = 2e6 + 20;
    int n, m, dp[N];
    int son[N][26], cnt[N], idx;
    char s[N];
    void init(){
        memset(son, 0, sizeof son);
        memset(cnt, 0, sizeof cnt);
        idx = 0;
    }
    void insert(char *s){
        int p = 0;
        for(int i = 0; s[i]; ++ i){
            int u = s[i] - 'a';
            if(!son[p][u]) son[p][u] = ++ idx;
            p = son[p][u];
        }
        cnt[p] ++;
    }
    void query(int x){ // the searching start index of string s
        int p = 0;
        for(int i = x; s[i]; ++ i){
            int u = s[i] - 'a';
            if(!son[p][u]) break;
            p = son[p][u];
            if(cnt[p]) dp[i] = 1; // explain there exists a word's end, so next time
                                  // dp will call this function, the param is id plus one
        }
    }
}
using namespace Trie;

signed main()
{
    IOS;
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i){
        cin >> s;
        insert(s);        
    }
    for(int j = 1; j <= m; ++ j){
        memset(dp, 0, sizeof dp);
        cin >> s + 1;
        dp[0] = 1; // init
        for(int i = 0; s[i]; ++ i){
            if(dp[i]) query(i + 1);
        }
        for(int i = strlen(s); i >= 0; -- i){
            // searching from end to start, in order to gain the max number depend 
            // on greedy thought, and has made sure if there r not exist a solution
            // then output 0 because of dp[0] = 1
            if(dp[i]){
                cout << i << '\n';
                break;
            }
        }
    }
    return 0;
}

B - Secret Message 秘密資訊

題意
有多少資訊和這條暗号有着相同的字首，這些資訊和暗号都是不完整的

思路

既然是不完整的，那麼暗号裡隻要找到在 t r i e trie trie可以比對的即可

比如 11 11 11 配對 1 , 110 1,110 1,110，就分成了兩種情況

一種就是像 1 1 1這種在比對路上
一種就是像 110 110 110正常結束的

是以答案就是（途徑-結尾）

/*
 * @Author: NEFU AB_IN
 * @Date: 2021-08-27 02:41:04
 * @FilePath: \Vscode\ACM\Project\Trie\SecretMessage.cpp
 * @LastEditTime: 2021-08-27 09:57:06
 */
#include<bits/stdc++.h>
using namespace std;
#define LL                          long long
#define MP                          make_pair
#define SZ(X)                       ((int)(X).size())
#define IOS                         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define DEBUG(X)                    cout << #X << ": " << X << endl;
typedef pair<int , int>             PII;

namespace Trie{
    const int N = 2e6 + 10;
    int son[N][2], cnt[N], idx, ans[N];
    char s[N];
    void init(){
        memset(son, 0, sizeof son);
        memset(cnt, 0, sizeof cnt);
        idx = 0;
    }
    void insert(char *s){
        int p = 0;
        for(int i = 0; s[i]; ++ i){
            int u = s[i] - '0';
            if(!son[p][u]) son[p][u] = ++ idx;
            p = son[p][u];
            ans[p] ++;
        }
        cnt[p] ++;
    }
    int query(char *s){
        int p = 0, tot = 0, flag = 0;
        for(int i = 0; s[i]; ++ i){
            int u = s[i] - '0';
            if(!son[p][u]) {
                flag = 1;
                break;
            }
            p = son[p][u];
            tot += cnt[p];
        }
        if(!flag) tot += ans[p] - cnt[p];
        return tot;
    }
}
using namespace Trie;

int n, m;
signed main()
{
    IOS;
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i){
        int k, idx = 0;
        cin >> k;
        for(int j = 1; j <= k; ++ j){
            char x;
            cin >> x;
            s[idx ++] = x;
        }
        s[idx] = '\0';
        insert(s);
    }
    for(int i = 1; i <= m; ++ i){
        int k, idx = 0;
        cin >> k;
        for(int j = 1; j <= k; ++ j){
            char x;
            cin >> x;
            s[idx ++] = x;
        }
        s[idx] = '\0';
        cout << query(s) << '\n';
    }
    return 0;
}

D - The XOR Largest Pair

題意
在給定的 N N N 個整數 A 1 , A 2 , … , A N A1,A2,…,AN A1,A2,…,AN 中選出兩個進行異或運算，得到的結果最大是多少？

思路

O ( n ) O(n) O(n)周遊的 01 T r i e 01Trie 01Trie

/*
 * @Author: NEFU AB_IN
 * @Date: 2021-08-27 10:11:04
 * @FilePath: \Vscode\ACM\Project\Trie\poj3764.cpp
 * @LastEditTime: 2021-08-27 10:32:58
 */
#include<iostream>
#include<vector>
#include<cstring>
#include<string.h>
#include<cstdio>
#include<climits>
#include<cmath>
#include<algorithm>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<string>
#include<stack>
using namespace std;
#define LL                          long long
#define MP                          make_pair
#define SZ(X)                       ((int)(X).size())
#define IOS                         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define DEBUG(X)                    cout << #X << ": " << X << endl;
typedef pair<int , int>             PII;

namespace Trie01{
    const int N = 1e5 + 10;
    int son[N * 32][2], val[N * 32], idx;
    void init(){
        idx = 0;
        son[0][0] = son[0][1] = 0;
    }
    void insert(int x){
        int p = 0;
        for(int i = 31; i >= 0; -- i){
            int u = (x >> i) & 1;
            if(!son[p][u]){
                son[p][u] = ++ idx;
                p = son[p][u];
                son[p][0] = son[p][1] = 0;
            }
            else p = son[p][u];
        }
        val[p] = x;
    }
    int query(int x){
        int p = 0;
        for(int i = 31; i >= 0; -- i){
            int u = (x >> i) & 1;
            if(son[p][u ^ 1]) p = son[p][u ^ 1];
            else p = son[p][u];
        }
        return val[p] ^ x;
    }
}
using namespace Trie01;
int n, a[N];
signed main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i){
        cin >> a[i];
        insert(a[i]);
    }
    int ans = a[1] ^ a[2];
    for(int i = 1; i <= n; ++ i){
        ans = max(ans, query(a[i]));
    }
    cout << ans << '\n';
    return 0;
}

Trie樹Trie樹Phone List01Trie樹Xor Sum(hdu4825)A - L 語言B - Secret Message 秘密資訊D - The XOR Largest Pair

Trie樹

Phone List

題意

思路

01Trie樹

Xor Sum(hdu4825)

題意

思路

A - L 語言

題意

思路

B - Secret Message 秘密資訊

題意

思路

D - The XOR Largest Pair

題意

思路

繼續閱讀

CRC32和CRC8校驗代碼，C語言版

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

hdu 4741 Save Labman No.004（計算幾何） Save Labman No.004

C語言：初學者必定看懂的注釋！！！猴子吃桃問題。猴子第一天摘下若幹個桃子，每天都吃了前一天剩下的一半零一個，到第10天早上想再吃的時候，就剩下一個桃子. 求第一天共摘多少個桃子。

[轉]九大排序算法——C語言實作及詳解

筆試面試題目：滑動視窗(二)

while 循環、do- while 循環和 for 循環之間的那點事C語言自學之三種循環比較

資料結構與算法（27）——排序（二）

結構體：typedef與struct的差別

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希