1 solutions
-
0
其实这个就是一道马拉车的题,首先因为字符长度本来就为奇数,其次需求的回文长度也为奇数,而马拉车可以很轻松的把以每个字母为中心的回文长度找出来,只需要讲符合要求的回文数计数即可。
PS:回文数长度为5同时也为3。
下面为代码,本人蒟蒻,大佬轻喷
#include<iostream> #include<string.h> using namespace std; const int n=1e7+1e6+5; char arr[n],brr[n<<1]; int len[n<<1]; int bian(char *str) { int cou=0; int lenn=strlen(str); brr[cou++]='?'; for(int i=0;i<lenn;i++) { brr[cou++]='#'; brr[cou++]=arr[i]; } brr[cou++]='#'; return 2*lenn+1; } int man(char *str) { int lenn=bian(str); int mx=0; int h=0,ans=0; for(int i=1;i<=lenn;i++) { if(i<mx) { len[i]=min(mx-i,len[2*h-i]); } else { len[i]=1; } while(brr[i-len[i]]==brr[i+len[i]]) { len[i]++; } if(i+len[i]>mx) { h=i; mx=i+len[i]; } ans=max(ans,len[i]-1); } return lenn; } int main() { int n; cin>>n; cin>>arr; int lennn=man(arr); int num=0; for(int i=1;i<=lennn;i++) { if(len[i]-1>=n&&i%2==0) { if(len[i]-1==n) { num++; continue; } if((len[i]-1-n)%2==0) num++; } } if(num==0) cout<<"腾云驾雾,我尚且做不到"; else cout<<num; }
- 1
Information
- ID
- 6544
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 8
- Tags
- # Submissions
- 35
- Accepted
- 5
- Uploaded By