权限题...
描述：
题目就是问给定的串最少是由多少个回文串覆盖构成的
关于回文串首先肯定想的是 manacher
用 manacher 可以求出每个回文串
题目问的是给定的串最少是由多少个回文串覆盖构成的
那就变成了经典的线段覆盖问题
贪心一波就好了：
开一个数组 lin[ i ] 表示从第 i 个字符开始的回文串的最长长度
首先第一个字符一定要被覆盖到
那么就选 1~lin[ 1 ] 的线段来覆盖
然后考虑lin[ 1 ] + 1 的点一定要被覆盖到
枚举 2~lin[ 1 ] +1 开头的所有线段，找到右端点最右的线段并选择
然后考虑更后面的点，用同样的方法贪心即可
这么显然的贪心应该不用证明吧
复杂度 O(n)
然后答案就是选择的线段数量-1
代码：
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; const int N=2e5+7;; char s[N],a[N]; int f[N],ans; int lin[N];//注意此时的lin[i]是在原串时下标i void manacher() { int len=strlen(s+1); len=len*2+1; a[0]=‘$‘; for(int i=1;i<=len;i++) a[i]= (i&1) ? ‘#‘ : s[i>>1]; int pos=0,mx=0; for(int i=1;i<=len;i++) { f[i]= i<mx ? min(f[(pos<<1)-i],mx-i) : 1; while(a[i+f[i]]==a[i-f[i]]) f[i]++; if(i+f[i]>mx) mx=i+f[i],pos=i; } } void slove() { int ans=0,mx=0,pos=0,len=strlen(s+1); for(int i=2;i<=len<<1;i++) { pos=(i>>1)-(f[i]>>1)+1; lin[pos]=max(lin[pos],f[i]-1);//计算出lin数组 } int i=1; while(i<=len) { mx=max(mx,i+lin[i]-1); pos=mx; for(int j=i+1;j<=pos;j++) mx=max(mx,j+lin[j]-1);//贪心 ans++; i=pos+1; } printf("%d\n",ans-1);//线段数量-1 } int main() { while(scanf("%s",s+1)!=EOF) { memset(f,0,sizeof(f)); memset(a,0,sizeof(a)); memset(lin,0,sizeof(lin)); manacher(); slove(); } return 0; }
当然因为数据不大，所以 manacher 可以换成哈希
枚举中心然后二分可能长度，复杂度O(nlogn)
代码就不贴了
原文：https://www.cnblogs.com/LLTYYC/p/9701599.html