1 solutions

  • 0
    @ 2022-9-6 21:15:52

    其实这个就是一道马拉车的题,首先因为字符长度本来就为奇数,其次需求的回文长度也为奇数,而马拉车可以很轻松的把以每个字母为中心的回文长度找出来,只需要讲符合要求的回文数计数即可。

    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; 
    }
    

    Information

    ID
    6544
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    8
    Tags
    # Submissions
    35
    Accepted
    5
    Uploaded By