= =吃的好饱，明天再写吧= =

写傻逼树(SBT)有什么意思，傻逼树的功能太少了.

唉。这个题是那么显然的字符串hash或者trie,你们都在干什么？

我想说几句对于starwing不好听的话，但是对你个人有好处：（忠言逆耳）<br>starwing你回去好好练你的算法和数据结构，练好了再过来说。<br>话说如果你真会写sbt,只需要5分钟好不好，你找理由没写出来基本上表示你不会sbt或者最多只知道思想或者十分不熟练.<br>这个题能想到SBT,表明你算法能力还差得多.（多么显然的hash,trie!)

[ 本帖最后由 rofor 于 2009-8-25 21:24 编辑 ]

LS:我的算法本来就很差嘛，而且到目前为止还是图论+动规白痴
另外，我的hash代码见上，是因为某人说要看看avl，我才想过我根本没有写过任何平衡树，所以想练练手，因此你的批评是完全正确的。本题我根本就不认为平衡树是解决方案：因为string的比较操作太昂贵。
最后，我的确没找理由，我的确没写出来，不过不是因为写不出来（也许的确写不出来——而且概率非常大），而是因为我根本就没有写……
好吧，我看看sbt（反正现在没事），说实话，对于平衡树，我好像只会旋转，剩下的全部不通= =

另外，这题trie怎么写？复杂不？我总觉得trie好像不怎么好实现（除非用二叉树来模拟多元树），当然trie我也完全没写过……

= =NOCOW访问不上去了……只能看纯文字实现了……555没有图真痛苦（虽然如果直接照抄伪码不求甚解应该也能写出来……）算了，就当锻炼想像力吧……

恩，照猫画虎写了个SBT，不过不保证适合本题

#include <stdio.h>
#include <string.h>
#define N 10001
char str[N][201], count[N];
int left[N] = {0}, right[N] = {0}, size[N] = {0};
int root = 0, last = 0;
void left_rotate(int *t)
{
    int k = right[*t];
    right[*t] = left[k];
    left[k] = *t;
    size[k] = size[*t];
    size[*t] = size[left[*t]] + size[right[*t]];
    *t = k;
}
void right_rotate(int *t)
{
    int k = left[*t];
    left[*t] = right[k];
    right[k] = *t;
    size[k] = size[*t];
    size[*t] = size[left[*t]] + size[right[*t]];
    *t = k;
}
void sbt_maintain(int *t, int flags)
{
    if (flags)
    {
        if (size[left[left[*t]]] > size[right[*t]])
            right_rotate(t);
        else if (size[right[left[*t]]] > size[right[*t]])
        {
            left_rotate(&left[*t]);
            right_rotate(t);
        }
        else return;
    }
    else
    {
        if (size[right[right[*t]]] > size[left[*t]])
            left_rotate(t);
        else if (size[left[right[*t]]] > size[left[*t]])
        {
            right_rotate(&right[*t]);
            left_rotate(t);
        }
        else return;
    }
    sbt_maintain(&left[*t], 0);
    sbt_maintain(&right[*t], 1);
    sbt_maintain(t, 0);
    sbt_maintain(t, 1);
}
int sbt_search(int t, char *s)
{
    int res;
    if (t == 0)
        return 0;
    if ((res = strcmp(s, str[t])) == 0)
        return t;
    return sbt_search(res < 0 ? left[t] : right[t], s);
}
int sbt_insert(int *t, char *s)
{
    int res = 0, ret;
    if (*t == 0)
    {
        ++last;
        strcpy(str[last], s);
        *t = last;
        ret = *t;
        count[*t] = 1;
    }
    else
    {
        ++size[*t];
        ret = sbt_insert((res = strcmp(s, str[*t]) < 0) ?
                &left[*t] : &right[*t], s);
    }
    sbt_maintain(t, !res);
    return ret;
}
int sbt_remove(int *t, char *s)
{
    int cnt = 0;
    if (*t != 0)
    {
        int res = strcmp(s, str[*t]);
        if (res == 0)
        {
            *t = size[left[*t]] > size[right[*t]] ?
                left[*t] : right[*t];
            ++cnt;
        }
        cnt += sbt_remove(&left[*t], s);
        cnt += sbt_remove(&right[*t], s);
    }
    return cnt;
}
int main(void)
{
    int n, ret;
    (void)(scanf("%d", &n) == 1);
    while (n--)
    {
        char s[201];
        (void)(scanf("%s", s) == 1);
        if ((ret = sbt_search(root, s)) != 0)
            ++count[ret];
        else
            sbt_insert(&root, s);
    }
    for (n = 1; n <= last; ++n)
    {
        printf("%s %d\n", str[n], count[n]);
    }
    return 0;
}
/* cc: run='!$output <in' */

哎，对别人来说只需要五分钟的东西，竟然写了一个小时= =

回复 59楼 StarWing83
呵呵，我想我照你的这个练一遍打字，也不一定能在5分钟内搞定~