学步园

Trie

插入一个串：

void insert(char *s, int w) {//这样就实现了字符作下标↓

int cur = 0;//0是根节点,里面存放着一些指针, 存放的位置代表儿子的id,

//值为儿子的地址

    for (int i = 0; s[i]; i++) {//地址是顺序排列的,和节点数保持同步-1

        if (!chd[cur][ID[s[i]]])//若第i个字符不是当前节点的儿子

//儿子可以认为是住在父节点的数组里,他自己的家却住着他自己的儿子 囧 啃老串

            chd[cur][ID[s[i]]] = ++sz;//就插入这个儿子

        cur = chd[cur][ID[s[i]]];//指向下一个节点[第一维]

}//节点按照插入的顺序存在数组的每一行,同时儿子就是指向下一节点的指针; //初始化为0

    v[cur] = w;//cur为节点序号

}

HOJ2353 Card Hands

题意:每组case有若干手牌,均由不相同的52张组成,若a和b手牌末尾的m张完全相同,则可以合并存储.问每组case的所有牌可以用多少个节点存储.

思路:直接按照Trie的结构存,每个节点有52个儿子(一维的话编码转换一下,二维直接对应).由于题意是tail相同可以合并,因此倒着插入Trie.只需最后输出size即可.注意10号牌是两位数,需要特殊判断.

坑:1.写了clear函数忘记调用了..多组就错了

2.10特殊判断,但是由于编码的时候个位数全部减一,‘A’->0, ‘2’->1..但是10的时候一激动就对应了10,导致重复.

细节最后还是慢慢看出来的= =

#include <cstdio>
#include <cstring>
using namespace std;
const int MAX = 100005;
const int MAXC = 52;
//int id[MAXC];
int chd[MAX][MAXC];
int sz;
void clear()
{
    memset(chd,0,sizeof(chd));
    sz = 0;
}
int change(char c)
{
    if(c=='S') return 0;
    if(c=='H') return 13;
    if(c=='D') return 13*2;
    if(c=='C') return 13*3;
    if(c=='A') return 0;
    if(c>'1'&&c<='9') return c-'1';
    if(c=='J') return 10;
    if(c=='Q') return 11;
    return 12;
}
int GetID(char *s)
{
    if(s[1]=='0') return 9+change(s[2]);
    return change(s[0])+change(s[1]);
}
void insert(int *id,int len)
{
    int cur = 0;
    for(int i=len-1;i>=0;i--)
    {
        if(!chd[cur][id[i]])
            chd[cur][id[i]] = ++sz;
        cur = chd[cur][id[i]];
    }
}

int main()
{
    int hand,card;
    char s[4];
    int OneHand[MAX];
    while(scanf("%d",&hand))
    {
        if(!hand) break;
        clear();
        for(int i=0;i<hand;i++)
        {
            scanf("%d",&card);
            for(int j=0;j<card;j++)
            {
                scanf("%s",s);
                OneHand[j] = GetID(s);
            }
            insert(OneHand,card);
        }
        printf("%d\n",sz);
    }
    return 0;
}