【字典树】POJ_3283_Card Hands

作者: 今天也继续开心涅普涅普 | 来源:发表于2016-11-05 00:35 被阅读0次

【字典树】POJ_3283_Card Hands
2019-03-31字典树Tire
Trie
(六)树结构---字典树
字典树
字典树
字典树
字典树
字典树
字典树

Card Hands
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 2853 Accepted: 881

Description
Jim is writing a program for statistically analyzing card games. He needs to store many different card hands in memory efficiently. Each card has one of four suits and one of thirteen values. In his implementation, each hand is stored as a linked list of cards in a canonical order: the cards are first ordered by suit: all the clubs come first, followed by all the diamonds, then all the hearts, and finally the spades. Within each suit, the cards are ordered by value: A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K. Each hand contains at most one of any given card.
The card hands are using lots of memory. Jim therefore decides to try a more efficient representation. Whenever any two lists share a common tail, they can be updated to share one copy of the tail, and the other copy can be discarded. This process can be repeated until no two lists share a common tail.
Your job is to tell Jim how many linked list nodes he needs to store all the card hands.

Input
The input contains several test cases followed by a line containing 0. The first line of each case contains the number of card hands. Each subsequent line describes a card hand. It starts with a number indicating the number of cards in the hand. The cards follow, separated by spaces, in the canonical order defined above. For each card, the value is given first, followed by the suit (C, D, H, or S). There are at most 100,000 cards in all hands.

Output
For each test case, output a line containing the number of linked list nodes needed to store all the lists.

Sample Input
3
3 7D AH 5S
4 9C 3D 4D 5S
2 AH 5S
0

Sample Output
6

Source
Waterloo Local Contest, 2006.5.27

题意：
给n个套卡牌（扑克52张），每一套有m张，每一套牌从尾到头指向，形成一颗树，求这颗树有多少节点。

思路：
字典树。

#include<cstdio>
#include<cstring>
#include<string>
#include<map>
using namespace std;

map<string, int> poker;

void init() {
    poker["AC"] = 0; poker["2C"] = 1; poker["3C"] = 2; poker["4C"] = 3; poker["5C"] = 4;
    poker["6C"] = 5; poker["7C"] = 6; poker["8C"] = 7; poker["9C"] = 8; poker["10C"] = 9; 
    poker["JC"] = 10; poker["QC"] = 11; poker["KC"] = 12;
    poker["AD"] = 13; poker["2D"] = 14; poker["3D"] = 15; poker["4D"] = 16; poker["5D"] = 17;
    poker["6D"] = 18; poker["7D"] = 19; poker["8D"] = 20; poker["9D"] = 21; poker["10D"] = 22;
    poker["JD"] = 23; poker["QD"] = 24; poker["KD"] = 25;
    poker["AH"] = 26; poker["2H"] = 27; poker["3H"] = 28; poker["4H"] = 29; poker["5H"] = 30;
    poker["6H"] = 31; poker["7H"] = 32; poker["8H"] = 33; poker["9H"] = 34; poker["10H"] = 35;
    poker["JH"] = 36; poker["QH"] = 37; poker["KH"] = 38;
    poker["AS"] = 39; poker["2S"] = 40; poker["3S"] = 41; poker["4S"] = 42; poker["5S"] = 43;
    poker["6S"] = 44; poker["7S"] = 45; poker["8S"] = 46; poker["9S"] = 47; poker["10S"] = 48;
    poker["JS"] = 49; poker["QS"] = 50; poker["KS"] = 51;
    return; 
}

const int maxn = 100000 + 10;
int cnt;
struct Node{
    int next[52];
}node[maxn];

int n, m;
char pok[maxn][5];

int build(int root, int val) {
    if (node[root].next[val] == 0)
        node[root].next[val] = cnt++;
    return node[root].next[val];
}

int main() {
    init();
    while (scanf("%d", &n) != EOF && n) {
        memset(node, 0, sizeof(node));
        cnt = 2;
        int root;
        for (int i = 0; i < n; ++i) {
            scanf("%d", &m);
            for (int j = 0; j < m; ++j) {
                scanf("%s", pok[j]);
            }
            root = build(1, poker[pok[m - 1]]);
            for (int j = m - 2; j >= 0; --j)
                root = build(root, poker[pok[j]]);
        }
        printf("%d\n", cnt - 2);
    }
    return 0;
}