紧跟jk大佬的步伐 这道题哇 因为机器一能生成回文串 所以我们只要用manacher跑一遍求出q【i】这样就把问题转化成了类似线段覆盖的题目 贪心就好了 至于,BIT优化dp我不会所以直接贪心了 注意答案是所需线段减一 因为是合并两条需要一次二机器 当然我ans(答案)直接初始化了0 懒得减一了 剩下的看代码吧
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int M=100007; char s[M]; int p[M],sum,len; struct node{int l,r;}e[M]; bool cmp(node a,node b){ if(a.l!=b.l) return a.l<b.l; return a.r>b.r; } void add(int x,int y){sum++; e[sum].l=x; e[sum].r=y;} void manacher(){ len=strlen(s); memset(p,0,sizeof(p)); for(int i=len;i>=0;i--) s[i*2+2]=s[i],s[i*2+1]='#'; s[0]='&'; int id=0; len=len*2; for(int i=1;i<=len;i++){ if(id+p[id]>i) p[i]=min(p[id*2-i],id+p[id]-i); else p[i]=1; while(s[i-p[i]]==s[i+p[i]]) p[i]++; if(i+p[i]>id+p[id]) id=i; add(i-p[i]+1,i+p[i]-1); } } void push_ans(){ int r=e[1].r,ans=0,k=2; while(r<len){ int now=r; while(k<=sum&&e[k].l<=r) now=max(now,e[k].r),k++; ans++; r=now; } printf("%d ",ans); } int main() { while(~scanf("%s",s)){ sum=0; manacher(); sort(e+1,e+1+sum,cmp); //for(int i=1;i<=sum;i++) printf("[%d %d] ",e[i].l,e[i].r); push_ans(); } return 0; }