博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU 4436 str2int(后缀自动机)
阅读量:6412 次
发布时间:2019-06-23

本文共 1597 字,大约阅读时间需要 5 分钟。

题目链接:

题意:给出一些数字串,每个数字串可以分成若干数字,比如123可以分成1,2,3,12,23,123。求所有数字串分成的数字的集合的和。

思路:后缀自动机:串之间用数字10隔开,建立自动机。节点p和数字j得到的子节点q,q->cnt+=p->cnt,q->sum+=p->sum*10+p->cnt*j。

const int KIND=11;struct SAM{    SAM *son[KIND],*pre;    int len,sum,cnt;    void init()    {        clr(son,NULL);        pre=NULL;        cnt=sum=len=0;    }};SAM sam[N],*head,*last,*b[N];int d[N];int cnt,len;char s[N];void initSAM(){    sam[0].init();    head=last=&sam[0];    cnt=1;}void insert(int x){    SAM *p=&sam[cnt++],*u=last;    p->init();    p->len=last->len+1;    last=p;    for(;u&&!u->son[x];u=u->pre) u->son[x]=p;    if(!u) p->pre=head;    else if(u->son[x]->len==u->len+1) p->pre=u->son[x];    else    {        SAM *r=&sam[cnt++],*q=u->son[x];        *r=*q;        r->len=u->len+1;        p->pre=q->pre=r;        for(;u&&u->son[x]==q;u=u->pre) u->son[x]=r;    }}void init(){    int i;    FOR0(i,len+1) d[i]=0;    FOR0(i,cnt) d[sam[i].len]++;    FOR1(i,len) d[i]+=d[i-1];    FOR0(i,cnt) b[--d[sam[i].len]]=&sam[i];}int n;void deal(){    int ans=0,i,j;        SAM *p;    head->cnt=1;    FOR0(i,cnt)    {        p=b[i];        ans=(ans+p->sum)%mod;        FOR0(j,10) if(p->son[j])        {            if(!i&&!j) continue;            (p->son[j]->cnt+=p->cnt)%=mod;            (p->son[j]->sum+=p->sum*10+p->cnt*j)%=mod;        }    }    PR(ans);}int main(){    while(scanf("%d",&n)!=-1)    {        initSAM(); len=0;        int i,L;        while(n--)        {            RD(s); L=strlen(s);            FOR0(i,L) insert(s[i]-'0'),len++;            insert(10); len++;        }        init();        deal();    }    return 0;}

 

  

 

转载地址:http://jxqea.baihongyu.com/

你可能感兴趣的文章
MySql 查询表字段数
查看>>
mariadb 内存占用优化
查看>>
Centos7安装编译安装zabbix2.219及mariadb-5.5.46
查看>>
怎么获得combobox的valueField值
查看>>
浅谈网络协议(四) IP的由来--DHCP与PXE
查看>>
jre与jdk的区别
查看>>
全景图的种类
查看>>
git 维护
查看>>
jfinal框架下使用c3P0连接池连接sql server 2008
查看>>
Jfinal Generator 不需要生成带某个前缀的表名数组的方法
查看>>
struts2中使用标签操作静态方法等
查看>>
熬夜写了一个小游戏,向SpaceX聊表敬意
查看>>
JPA增删改查,
查看>>
apache 开启 gzip 压缩服务
查看>>
python mysql
查看>>
开源 免费 java CMS - FreeCMS1.5-建站向导
查看>>
jquery 1.6以上版本 全选
查看>>
AppCan 学习
查看>>
flask框架
查看>>
《疯狂Java讲义》学习笔记(十)异常处理
查看>>