注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zorksylar

Nothing is impossible , if distributed.

 
 
 

日志

 
 

【字典树】 hdu 1251 统计难题  

2011-12-16 21:27:48|  分类: ACM_数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目链接:
题目大意:
中问题,你懂的
分析:
字典树,
开始的时候没有记录每个点访问的次数,所以TLE,后来在每次insert的时候更新每个节点的访问次数AC

代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 500000
using namespace std;

const int tk = 26,tb = 'a';
int tree[MAXN][tk+1],top;
int cont[MAXN];

void tree_init()
{
        top = 1;
        memset(tree[0],0,sizeof(tree[0]));
}

void insert(char *s,int rank = 1)
{
        int nxt,rt;
        for(rt = 0; *s ; rt = nxt, ++s)
        {
                nxt = tree[rt][*s - tb];
                cont[rt] ++;
                if(nxt == 0)
                {
                        tree[rt][*s - tb] = nxt = top;
                        top ++;
                        memset(tree[nxt],0,sizeof(tree[nxt]));
                }
        }
        cont[rt] ++;
        tree[rt][tk] = rank;
}

int find(char *s)
{
        for(int rt = 0;rt = tree[rt][*s - tb]; )
        {
                if(*(++s) == 0)
                {
                        return cont[rt];
                }
        }
        return 0;
}

void init()
{
        char tch[11];
        tree_init();
        memset(cont,0,sizeof(cont));
        while(gets(tch) != NULL)
        {
                if(tch[0] == 0) break;
                insert(tch,1);
        }
}

void work()
{
        char tch[11];
        while(gets(tch) != NULL)
        {
                printf("%d\n",find(tch));
        }
}

int main()
{
        init();
        work();
        return 0;
}
  评论这张
 
阅读(141)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018