首页 > 代码库 > 【POJ】3283 Card Hands

【POJ】3283 Card Hands

字典树。

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <stack> 6 using namespace std; 7  8 #define TRIEN 56 9 10 typedef struct Trie {11     Trie *next[TRIEN];12     Trie() {13         for (int i=0; i<TRIEN; ++i)14             next[i] = NULL;15     }16 } Trie;17 18 Trie *root;19 int nn;20 21 Trie *create(const char str[], Trie *r) {22     int i = 0, id;23     Trie *p = r, *q;24 25     if (str[i] == A)26         id = 1;27     else if (str[i] == J)28         id = 11;29     else if (str[i] == Q)30         id = 12;31     else if (str[i] == K)32         id = 13;33     else if (str[i]==1 && ++i)34         id = 10;35     else36         id = str[i] - 0;37     if (str[i+1]==D)38         id += 14;39     if (str[i+1]==H)40         id += 28;41     if (str[i+1]==S)42         id += 42;43     if (p->next[id] == NULL) {44         q = new Trie();45         p->next[id] = q;46         ++nn;47     }48     p = p->next[id];49 50     return p;51 }52 53 void del(Trie *t) {54     if (t == NULL)55         return ;56     for (int i=0; i<TRIEN; ++i)57         del(t->next[i]);58     delete t;59 }60 61 int main() {62     int n, m;63     string tmp;64     stack<string> st;65     Trie *r;66 67     while (scanf("%d", &n)!=EOF && n) {68         root = new Trie();69         nn = 0;70         while (n--) {71             scanf("%d", &m);72             while (m--) {73                 cin >> tmp;74                 st.push(tmp);75             }76             r = NULL;77             while (!st.empty()) {78                 tmp = st.top();79                 st.pop();80                 if (r == NULL)81                     r = create(tmp.data(), root);82                 else83                     r = create(tmp.data(), r);84             }85         }86         printf("%d\n", nn);87         del(root);88     }89 90     return 0;91 }