首页 > 代码库 > BZOJ3790: 神奇项链
BZOJ3790: 神奇项链
3790: 神奇项链
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 79 Solved: 40
[Submit][Status]
Description
母亲节就要到了，小 H 准备送给她一个特殊的项链。这个项链可以看作一个用小写字
母组成的字符串，每个小写字母表示一种颜色。为了制作这个项链，小 H 购买了两个机器。第一个机器可以生成所有形式的回文串，第二个机器可以把两个回文串连接起来，而且第二个机器还有一个特殊的性质：假如一个字符串的后缀和一个字符串的前缀是完全相同的，那么可以将这个重复部分重叠。例如：aba和aca连接起来，可以生成串abaaca或 abaca。现在给出目标项链的样式，询问你需要使用第二个机器多少次才能生成这个特殊的项链。
Input
输入数据有多行，每行一个字符串，表示目标项链的样式。
Output
多行，每行一个答案表示最少需要使用第二个机器的次数。
Sample Input
abcdcba
abacada
abcdef
abacada
abcdef
Sample Output
0
2
5
2
5
HINT
每个测试数据，输入不超过 5行
每行的字符串长度小于等于 50000
题解：
我想呵呵。。。
我是这样想得，我们先manacher一遍，令f[i]表示打出1--i的最小花费
然后可以O（n）求出以每个点结尾的最长回文子串，不妨设最远扩展到x，
然后就可以用min（f[j]）（x-1<=j<=i-1） +1来更新f[i]
就可以线段树搞了。
代码：
View Code
我是这样想得，我们先manacher一遍，令f[i]表示打出1--i的最小花费
然后可以O（n）求出以每个点结尾的最长回文子串，不妨设最远扩展到x，
然后就可以用min（f[j]）（x-1<=j<=i-1） +1来更新f[i]
就可以线段树搞了。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 500000+5 26 27 #define maxm 20000000+5 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 int n,m,a[maxn],f[maxn],p[maxn]; 61 char s[maxn]; 62 struct seg{int k,l,r,mi;}t[4*maxn]; 63 inline void build(int k,int l,int r) 64 { 65 t[k].l=l;t[k].r=r;int mid=(l+r)>>1;t[k].mi=inf; 66 if(l==r){if(!l)t[k].mi=-1;return;} 67 build(k<<1,l,mid);build(k<<1|1,mid+1,r); 68 } 69 inline void pushup(int k) 70 { 71 t[k].mi=min(t[k<<1].mi,t[k<<1|1].mi); 72 } 73 inline void change(int k,int x,int y) 74 { 75 int l=t[k].l,r=t[k].r,mid=(l+r)>>1; 76 if(l==r){t[k].mi=min(t[k].mi,y);return;} 77 if(x<=mid)change(k<<1,x,y);else change(k<<1|1,x,y); 78 pushup(k); 79 } 80 inline int query(int k,int x,int y) 81 { 82 int l=t[k].l,r=t[k].r,mid=(l+r)>>1; 83 if(l==x&&r==y)return t[k].mi; 84 if(y<=mid)return query(k<<1,x,y); 85 else if(x>mid)return query(k<<1|1,x,y); 86 else return min(query(k<<1,x,mid),query(k<<1|1,mid+1,y)); 87 } 88 89 int main() 90 91 { 92 93 freopen("input.txt","r",stdin); 94 95 freopen("output.txt","w",stdout); 96 97 while(scanf("%s",s)!=EOF) 98 { 99 n=strlen(s);100 build(1,0,n);101 for1(i,n)a[i<<1]=s[i-1];102 m=n;n=2*n+1;103 int id=0,mx=0;104 for1(i,n)105 {106 if(mx>i)p[i]=min(p[2*id-i],mx-i);107 while(i-p[i]-1>0&&i+p[i]+1<=n&&a[i-p[i]-1]==a[i+p[i]+1])p[i]++;108 if(i+p[i]>mx)mx=i+p[i],id=i;109 }110 int now=0;111 for1(i,n)if(i+p[i]>now)112 {113 for2(j,now+1,i+p[i])f[j]=2*i-j;114 now=i+p[i];115 }116 for1(i,m)change(1,i,query(1,max(0,(f[i<<1]>>1)-1),i-1)+1);117 printf("%d\n",query(1,m,m));118 memset(a,0,sizeof(a));119 memset(s,0,sizeof(s));120 memset(p,0,sizeof(p));121 memset(f,0,sizeof(f));122 }123 124 return 0;125 126 }
刚开始装逼用gets结果WA了好几发感觉人生无望，这种题都A不了，就颓了一节课T_T
UPD：orzky的题解http://blog.csdn.net/iamzky/article/details/41852799
BZOJ3790: 神奇项链
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。