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

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3790]神奇项链  

2015-04-23 21:33:57|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3790: 神奇项链

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 132  Solved: 65
[Submit][Status][Discuss]

Description

母亲节就要到了,小 H 准备送给她一个特殊的项链。这个项链可以看作一个用小写字
母组成的字符串,每个小写字母表示一种颜色。为了制作这个项链,小 H 购买了两个机器。第一个机器可以生成所有形式的回文串,第二个机器可以把两个回文串连接起来,而且第二个机器还有一个特殊的性质:假如一个字符串的后缀和一个字符串的前缀是完全相同的,那么可以将这个重复部分重叠。例如:aba和aca连接起来,可以生成串abaaca或 abaca。现在给出目标项链的样式,询问你需要使用第二个机器多少次才能生成这个特殊的项链。 

Input

输入数据有多行,每行一个字符串,表示目标项链的样式。 

Output

多行,每行一个答案表示最少需要使用第二个机器的次数。 

Sample Input

abcdcba abacada abcdef

Sample Output

0 2 5

HINT

每个测试数据,输入不超过 5行 
每行的字符串长度小于等于 50000 

Solution

用回文自动机处理出每个节点往前能回文的最大长度,然后问题转化为用尽量少的线段覆盖1~n整个区间。
贪心解决,按左端点排序。注意分情况讨论
(怎么办怎么办我又被坑了好久结果发现右端点r与下一个区间左端点相等没判......)

Code

/**************************************************************
    Problem: 3790
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:336 ms
    Memory:12628 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100010
char s[N];int n,i,j,len[N],las,ch[N][26],fail[N],tot,fa,now,ans,r;
struct D{int x,y;}a[N];
bool operator<(const D&i,const D&j){return i.x<j.x||i.x==j.x&&i.y>j.y;}
int nn(int l){fail[tot]=0,len[tot]=l;return tot++;}
int gf(int x){
    while(s[n-1-len[x]]!=s[n])x=fail[x];
    return x;
}
void add(char c){
    if(!ch[fa=gf(las)][c]){
        now=nn(len[fa]+2);
        fail[now]=ch[gf(fail[fa])][c];
        ch[fa][c]=now;
    }
    las=ch[fa][c];a[n]=(D){n-len[las],n};
}
#define cmax(a,b) (a<b?a=b:a)
int main(){
    while(~scanf("%s",s+1)){
        memset(ch,0,sizeof(ch));
        s[0]=-1,las=tot=0;nn(0),nn(-1),fail[0]=fail[1]=1;
        for(n=1;s[n];n++)add(s[n]-'a');
        std::sort(a+1,a+n);n--;
        ans=1,now=r=a[1].y;
        for(i=2;i<=n;i++){
            if(a[i].x<r)cmax(now,a[i].y);
            else if(a[i].x==r)ans++,r=cmax(now,a[i].y);
            else ans++,r=now,cmax(now,a[i].y);
        }
        if(r!=n)ans++;
        printf("%d\n",ans-1);
    }
}
  评论这张
 
阅读(33)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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