0x16 Trie

比眉伴天荒 2021-11-29 12:36 254阅读 0赞

模板：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
     2 #include <cstdio>
     3 #include <cmath>
     4 #include <cstring>
     5 #include <algorithm>
     6 using namespace std;
     7 const int INF=0x3f3f3f3f;
     8 const int maxn=1000000+10;
     9 int n;
    10 int trie[maxn][26], tot=1;
    11 bool end[maxn];
    12 
    13 void insert(char *str) {
    14     int len=strlen(str), p=1;
    15     for (int i=0; i<len; ++i) {
    16         int ch=str[i]-'a';
    17         if (trie[p][ch]==0) trie[p][ch]=++tot;
    18         p=trie[p][ch];
    19     }
    20     end[p]=true;
    21 }
    22 
    23 bool search(char *str) {
    24     int len=strlen(str), p=1;
    25     for (int i=0; i<len; ++i) {
    26         int ch=str[i]-'a';
    27         p=trie[p][ch];
    28         if (p==0) return false;
    29     }
    30     return end[p];
    31 }
    32 
    33 int main() {
    34     //freopen("a.txt", "r", stdin);
    35     //freopen("a.out", "w", stdout);
    36     scanf("%d", &n);
    37     for (int i=1; i<=n; ++i) {
    38         char s[maxn];
    39         scanf("%s", s);
    40         insert(s);
    41     }
    42     int m;
    43     scanf("%d", &m);
    44     for (int i=1; i<=n; ++i) {
    45         char s[maxn];
    46         scanf("%s", s);
    47         printf("%d\n", search(s));
    48     }
    49     return 0;
    50 }  
    51 /*
    52 10
    53 abssad
    54 sdas
    55 dsad
    56 dssfsfs
    57 avdsvd
    58 fbvfd
    59 fdsf
    60 dsf
    61 abs
    62 ds
    63 100
    64 */

**[【例题】CH1601 前缀标记][CH1601]**

坑：不能只做结尾标记，要记录个数。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
     2 #include <cstdio>
     3 #include <cmath>
     4 #include <cstring>
     5 #include <algorithm>
     6 using namespace std;
     7 const int INF=0x3f3f3f3f;
     8 const int maxn=1000000+10;
     9 const int maxm=26*1000000+10;
    10 int n, m;
    11 int trie[maxn][26], tot=1;
    12 int endd[maxm];
    13 
    14 void insert(char *str) {
    15     int len=strlen(str), p=1;
    16     for (int i=0; i<len; ++i) {
    17         int ch=str[i]-'a';
    18         if (trie[p][ch]==0) trie[p][ch]=++tot;
    19         p=trie[p][ch];
    20     }
    21     endd[p]++;    //不能只做结尾标记，需要统计以该节点结尾的字符串的个数 
    22 }
    23 
    24 int search(char *str) {
    25     int ans=0;
    26     int len=strlen(str), p=1;
    27     for (int i=0; i<len; ++i) {
    28         int ch=str[i]-'a';
    29         p=trie[p][ch];
    30         if (p==0) return ans;
    31         ans+=endd[p];
    32     }
    33     return ans;
    34 }
    35 
    36 int main() {
    37     //freopen("a.txt", "r", stdin);
    38     //freopen("a.out", "w", stdout);
    39     scanf("%d%d", &n, &m);
    40     for (int i=1; i<=n; ++i) {
    41         char s[maxn];
    42         scanf("%s", s);
    43         insert(s);
    44     } 
    45     for (int i=1; i<=m; ++i) {
    46         char s[maxn];
    47         scanf("%s", s);
    48         printf("%d\n", search(s));
    49     }
    50     return 0;
    51 }

[**【例题】CH1602 The XOR Largest Pair**][CH1602 The XOR Largest Pair]

把每个数转化为32位二进制整数，插入到Trie中，然后对于每个数贪心的选择与当前位相反的位。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
     2 #include <cstdio>
     3 #include <cmath>
     4 #include <cstring>
     5 #include <algorithm>
     6 using namespace std;
     7 const int INF=0x3f3f3f3f;
     8 const int maxn=40;
     9 const int maxm=100000+10;
    10 int n;
    11 int trie[maxn*maxm][2], tot=1;
    12 
    13 void insert(int x) {
    14     int p=1;
    15     for (int i=31; i>=0; --i) {
    16         int c=(x>>i)&1;
    17         if (trie[p][c]==0) trie[p][c]=++tot;
    18         p=trie[p][c];
    19     }
    20 }
    21 
    22 int search(int x) {
    23     //printf("%d:\n", x);
    24     int p=1, ans=0;
    25     for (int i=31; i>=0; --i) {
    26         int c=(x>>i)&1;
    27         if (trie[p][c^1]) {
    28             p=trie[p][c^1];
    29             ans=(ans<<1)|1;
    30         }
    31         else {
    32             p=trie[p][c];
    33             ans=ans<<1;
    34         }
    35         //printf("%d ", ans);
    36     }
    37     return ans;
    38 }
    39 
    40 int main() {
    41     //freopen("a.txt", "r", stdin);
    42     //freopen("a.out", "w", stdout);
    43     scanf("%d", &n);
    44     int x, ans=-INF;
    45     for (int i=1; i<=n; ++i) {
    46         scanf("%d", &x);
    47         ans=max(ans, search(x));
    48         //printf("\n");
    49         insert(x);
    50     } 
    51     printf("%d\n", ans);
    52     return 0;
    53 }

转载于:https://www.cnblogs.com/kkkstra/p/11118467.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211129/d556a121ba0f493f9ccd1bd38b2e07e2.png
[CH1601]: http://contest-hunter.org:83/contest/0x10%E3%80%8C%E5%9F%BA%E6%9C%AC%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E3%80%8D%E4%BE%8B%E9%A2%98/1601%20%E5%89%8D%E7%BC%80%E7%BB%9F%E8%AE%A1
[CH1602 The XOR Largest Pair]: http://contest-hunter.org:83/contest/0x10%E3%80%8C%E5%9F%BA%E6%9C%AC%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E3%80%8D%E4%BE%8B%E9%A2%98/1602%20The%20XOR%20Largest%20Pair