这道题别看题面这么长，其实题意很简单
就是让你求从起点开始的最长合法区间
合法的要求有两个：兜圈子和直飞
且这两个条件相互独立
（也就是说兜圈子的末尾不会对下面可能出现的直飞造成影响）
举个例子：
1 2 3 2 1 5 4 3 8 9
这个序列他的合法长度是8
因为直飞是 5 4 3 8 9
1是兜圈子的末尾，对直飞无影响
这样看来，兜圈子比直飞优秀的多
因为如果直飞的某段属于兜圈子
那么把这一段归于兜圈子后对序列的合法性无影响
但如果兜圈子的某段属于直飞，那归于直飞后
剩下的这部分可能就不是兜圈子了
所以我们先用manacher跑出回文区间
用差分数组维护一下回文区间
如果在回文区间内，则不考虑
否则判断是否直飞即可
只要确保完全符合，就记下来这个区间和这个区间的末尾值
后面的就是贪心了
最优情况自然是你选的那条正好是飞船所在
飞船所在正好是最短的
最坏情况是你最后一次选到的是最短的
且这个位置是飞船所在
几率我们会惊讶的发现其实是一样的
排个序第二个也很好求
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define rii register int i #define rij register int j #define mod 19260817 using namespace std; char s[200005],cp[200005]; int p[200005],cd,t,n,ans,cnt,jl[105],cf[200005],lnt; char zcq1[200005]; int zcq2[200005],m; void ycl() { int k=0; cp[k]=1; k++; for(rii=0;i<=cd-1;i++) { cp[k]='#'; k++; cp[k]=s[i]; k++; } cp[k]='#'; k++; cd=k; } void manacher() { ycl(); int mx=0; int last=0; for(rii=1;i<=cd-1;i++) { if(mx>i) { p[i]=min(p[2*last-i],mx-i); } else { p[i]=1; } while(cp[i+p[i]]==cp[i-p[i]]) { p[i]++; } if(p[i]+i>mx) { mx=p[i]+i; last=i; } } } void cfs() { for(rii=1;i<=cnt;i++) { if(zcq2[i]>1) { cf[i-(zcq2[i])/2]++; cf[i+(zcq2[i])/2]--; } } } int yz() { int sl=0,pre=0,pd=0; for(rii=1;i<=cnt;i++) { sl+=cf[i]; if(sl==0&&cf[i]>=0) { if(pre==0) { pre=zcq1[i]; continue; } if(pd==0) { if(zcq1[i]>pre) { pd=1; } else { if(zcq1[i]==pre) { pd=0; } else { pd=2; } } pre=zcq1[i]; continue; } if(pd==1) { if(pre>zcq1[i]) { return i; } else { pre=zcq1[i]; } } if(pd==2) { if(pre<zcq1[i]) { return i; } else { pre=zcq1[i]; } } } else { pre=0; } } return cnt+1; } long long pw(long long ds,int ms) { long long res=1; while(ms!=0) { if(ms%2==1) { ms--; res*=ds; res%=mod; } else { ds*=ds; ds%=mod; ms/=2; } } return res; } bool cmp(int kl,int lk) { return kl<lk; } void sr() { memset(s,0,sizeof(s)); memset(p,0,sizeof(p)); memset(cf,0,sizeof(cf)); for(rij=0;j<t;j++) { s[j]=getchar(); } getchar(); getchar(); } void fz() { for(rij=2;j<=cd-1;j+=2) { cnt++; zcq1[cnt]=cp[j]; zcq2[cnt]=p[j]-1; } } int main() { scanf("%d %d",&n,&t); scanf("%d ",&m); for(rii=1;i<=n;i++) { sr(); cd=t; manacher(); cnt=0; fz(); cfs(); int bnt=cnt; int ltt=yz(); if(ltt==m+1) { lnt++; jl[lnt]=pw(zcq1[bnt],zcq1[bnt]); } // printf("%d ",ans-1); } if(lnt==0) { cout<<"-1"; return 0; } if(lnt==1) { cout<<jl[1]<<" "<<jl[1]<<" 1.00000000 1.00000000"; return 0; } sort(jl+1,jl+lnt+1,cmp); int minx=jl[1]; // jl[1]; int ant=1; long long js=0; for(rii=2;i<=lnt;i++) { if(jl[i]==minx) { ant++; } else { break; } } for(rii=2;i<=lnt;i++) { js+=jl[i]; } js*=2; js+=minx; cout<<minx<<" "<<js<<" "; double kn=((1.0)*ant)/lnt; kn/=lnt; printf("%.8lf %.8lf",kn,kn); }