文章目录

HDU 4513 吉哥系列故事——完美队形II

题意：

求一个最长的完美队形，满足左右对称，从左到中间身高需保证不下降

题解：

在manacher模板的基础上增加改动，

 while(newStr[i-p[i]]==newStr[i+p[i]] &&  newStr[i-p[i]]<=newStr[i-p[i]+2] )

多添加一个newStr[i-p[i]]<=newStr[i-p[i]+2]条件，使得所求的回文串满足要求

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define PI acos(-1.0)
#define E 1e-9
#define INF 0x3f3f3f3f
#define LL long long
const int MOD=10007;
const int N=200000+5;
const int dx[]= {
   -1,1,0,0};
const int dy[]= {
   0,0,-1,1};
using namespace std;
int str[N];
int newStr[N*2];
int p[N*2];
int n;
int init(){
   
    newStr[0]=-1;
    newStr[1]=0;
 
    int j=2;
    int len=n;
    for (int i=0;i<len;i++){
   
        newStr[j++]=str[i];
        newStr[j++]=0;
    }
 
    return j;
}
 
int manacher(){
   
    int len=init();
    int res=-1;
 
    int id;
    int mx=0;
    for(int i=1;i<len;i++){
   
        int j=2*id-i;
        if(i<mx)
            p[i]=min(p[j], mx-i);
        else
            p[i]=1;
 
        while(newStr[i-p[i]]==newStr[i+p[i]] &&  newStr[i-p[i]]<=newStr[i-p[i]+2] )
            p[i]++;
 
        if(mx<i+p[i]){
   
            id=i;
            mx=i+p[i];
        }
        res=max(res,p[i]-1);
    }
    return res;
}
 
int main(){
   
    int t;
    scanf("%d",&t);
    while(t--)
    {
   
        scanf("%d",&n);
        for(int i=0;i<n;++i)
            scanf("%d",&str[i]);
        printf("%d\n",manacher());
    }
    return 0;
}

HDU 3613 Best Reward

题意：

一个由26个字母组成的项链，中间切开分成两部分
两部分必须是回文串，否则价值为0，26个字母的价值会给出
问两个部分的价值和是多少

题解：

先求出项链价值的前缀和
跑一遍manacher
我们要将回文串分为两部分，然后分别枚举两部分的中心，判断左右两部分是否为回文串，并记录各自的价值，最后更新最大价值

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
 
const int mn = 500010;
 
char ch[mn];
int val[30], VAL[mn];
 
char temp[2 * mn];
int tp[2 * mn];
void manacher(char ch[])
{
   
	int len = strlen(ch);
 
	temp[0] = '@';
	for (int i = 1; i <= 2 * len; i += 2)
	{
   
		temp[i] = '#';
		temp[i + 1] = ch[i / 2];
	}
	temp[2 * len + 1] = '#';
	temp[2 * len + 2] = '$';
	temp[2 * len + 3] = '\0';
	int tlen = 2 * len + 1;
 
	int mx = 0, id = 0;
	for (int i = 1; i <= tlen; i++)
	{
   
		if (mx >= i)
			tp[i] = min(tp[2 * id - i], mx - i + 1);
		else
			tp[i] = 1;
 
		while (temp[i - tp[i]] == temp[i + tp[i]])
			tp[i]++;
 
		if (mx < i + tp[i] - 1)
		{
   
			mx = i + tp[i] - 1;
			id = i;
		}
	}
}
 
int main()
{
   
	int T;
	scanf("%d", &T);
	while (T--)
	{
   
		for (int i = 0; i < 26; i++)
		{
   
			int t;
			scanf("%d", &t);
			val[i] = t;
		}
		scanf("%s", ch);
		int len = strlen(ch);
 
		VAL[0] = val[ch[0]- 'a'];
		for (int i = 1; i < len; i++)
			VAL[i] = VAL[i - 1] + val[ch[i] - 'a'];
 
		manacher(ch);
 
		int ans = -0x3f3f3f3f;
		int tlen = 2 * len + 1;
		for (int i = 3; i < tlen; i++)
		{
   	/// 枚举切割点
			if (temp[i] == '#')
			{
   
				int l = 0, r = 0;
				if (tp[(i + 1) / 2] == (i + 1) / 2) // 左侧回文
					l = VAL[i / 2 - 1];
				if (tp[(i + tlen) / 2] == (tlen - i) / 2 + 1) // 右侧回文
					r = VAL[len - 1] - VAL[i / 2 - 1];
				ans = max(ans, l + r);
			}
		}
		printf("%d\n", ans);
	}
}

HDU 3068 最长回文

题意：

求回文串的长度

题解：

裸题套模板

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 22000010;
char s[N];
char str[N];
int p[N];
int init() {
   
    int len = strlen(s);
    str[0] = '@', str[1] = '#';
    int j = 2;
    for (int i = 0; i < len; ++i) str[j++] = s[i], str[j++] = '#';
    str[j] = '\0';
    return j;
}
int manacher() {
   
    int ans = -1, len = init(), mx = 0, id = 0;
    for (int i = 1; i < len; ++i) {
   
        if (i < mx) p[i] = min(p[id * 2 - i], mx - i);
        else p[i] = 1;
        while (str[i + p[i]] == str[i - p[i]]) p[i]++;
        if (p[i] + i > mx) mx = p[i] + i, id = i;
        ans = max(ans, p[i] - 1);
    }
    return ans;
}
 
int main() {
   
	while(cin>>s)
	{
   
		 cout << manacher()<<endl;
	}
  // cin >> s;
   
    return 0;
}
//abahabuk

HDU 5371 Hotaru’s problem

题意：

找一个序列，满足第一部分和第三部分一样，第一部分和第二部分是对称的。
例如2,3,4,4,3,2,2,3,4
求最长长度是多少？

题解：

满足题目要求的序列，就是两个相邻的回文串，共享中间的一部分
我们可以认为，
左边的回文串长度的一半>=共享部分的长度
右边的回文串长度的一半>=共享部分的长度
不可能小于，不然中间共享部分就不成立了
所以我们根据左边的回文串长度的一半，来判断右边回文串是否符合要求，如果如何就记录最大值
如果左边回文串的中心是i
那么右边回文串的中心就是i+p[i]-1

while( len>an && p[i+len]-1-len<0 )

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000*3;
int s[maxn],str[maxn],p[maxn];
int len1,len2;
void init()
{
   
    str[0]=-2;
    str[1]=0;
    for(int i=0;i<len1;i++){
   
        str[i*2+2]=s[i];
        str[i*2+3]=0;
    }
    len2=len1*2+2;
    str[len2]=-3;
}
void manacher()
{
   
    init();
    int id=0,mx=0;
    for(int i=1;i<len2;i++){
   
        if(mx>i)
            p[i]=min(p[2*id-i],mx-i);
        else
            p[i]=1;
        for(;str[i+p[i]]==str[i-p[i]];p[i]++);
        if(p[i]+i>mx){
   
            mx=p[i]+i;
            id=i;
        }
    }
}
int main()
{
   
    int t;
    scanf("%d",&t);
    int cas=0;
    while(t--){
   
        cas++;
        scanf("%d",&len1);
        for(int i=0;i<len1;i++){
   
            scanf("%d",&s[i]);
        }
        manacher();
        int sum=0;
		for(int i=3;i<len2;i+=2)
		{
   
			if(p[i]-1>sum)
			{
   
				int len=p[i]-1;
				while( len>sum && p[i+len]-1<len)
					len--;
				sum=max(sum,len);
			}
		}
		printf("Case #%d: %d\n",cas,sum/2*3);
    }
}

ABB (2020牛客国庆集训派对day1)

题意：

长度为n的字符串，问最少添加多少字符可以使其构成回文字符串

题解：

最长回文字符串我的第一反应是manacher马拉车算法，那我们直接马拉车找到已有最长回文串，然后总长度减去不就是答案吗？非也 ~ ~ 。注意是让我们构造最长回文字符串，我们会发现，如果我们用马拉车找到的最长回文串的最右端不是字符串最右端，那此情况就相当于作废
比如：
murderforajarofz
我们可以找到最长回文串forajarof，但是最后一位z并不在里面，那你无论怎么构造也用不到forajarof这个回文串，也就是我们要找最长的带最后一个字符的回文字符串
我们直接在manacher的基础上改就可以，原本式子中的ans，我们每查找完一次清零，也就是如果找到的回文串不是带尾的不要，如果带尾保留最大值
详细看代码

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 9*1e5+4;
char s[maxn];
char str[maxn];
int p[maxn];//表示以i为中心的最长回文子串长度，

int init() {
   
    int len = strlen(s);
    str[0] = '@', str[1] = '#';
    int j = 2;
    for (int i = 0; i < len; ++i) str[j++] = s[i], str[j++] = '#';
    str[j] = '\0';
// cout<<j<<endl;
    return j;
}
int manacher() {
   
   
	int len = init(),sum=-1; 
	int mx = 0;//同时记录一个当前延伸最远的回文子串 
	int id = 0;//对称中心 
	int ans = -1;
    for (int i = 1; i < len; ++i) {
   
    	
        if (i < mx) p[i] = min(p[id * 2 - i], mx - i);
        else p[i] = 1;
        while (str[i + p[i]] == str[i - p[i]]) p[i]++;
        //if(i+p[i]==len-1) 
        if (p[i] + i > mx) mx = p[i] + i, id = i;
     // cout<<"id="<<id<<endl;
    	ans = max(ans, p[i] - 1);
		if(mx==len)sum=max(sum,ans);
		
		//cout<<"ans="<<ans<<endl;
    	//cout<<"mx="<<mx<<endl;
    	//cout<<"sum="<<sum<<endl;
 		ans=0;
	}
	return sum;
}
int main() 
{
   
	int t;
	cin>>t;
	for(int i=0;i<t;i++)cin>>s[i];
	if(manacher()==0)
	cout<<t-1<<endl;
	else 
  	cout <<t-manacher()<<endl;
    return 0;
}