Manacher[Cover.NOIP模拟赛]

[我们这里还有鱼] Problem B. 序列

对于一个长度为偶数的序列 a₁,a₂,a₃,…,a_n， 定义这个序列为好的序列，当且仅当

a₁ + a_n = a₂ + a_n−1 = a₃ + a_n-2 = ……

定义一个对序列的翻滚操作，使所有元素向前移一个位置，第一个元素移到最后的位置。 现在小 A 有一个长度为偶数的序列 b₁,b₂,b₃,…,b₃，他想知道至少需要翻滚多少次才能使这个序列 成为好的序列。

马拉车是什么？

(大误)

Manacher’s Algorithm，是一个叫做Manacher的人发明的一种线性求字符串最长回文子串的方法。

Manacher’s Algorithm

现在我们有两种回文串的类型：CABAC & CABBAC，那么怎么处理呢？如果分类讨论的话太丑陋，一个好的算法就应该男女通吃。我们考虑在每两个字符中插入一个’#’，这样的话就成了#C#A#B#A#C# & #C#A#B#B#A#C#，我们可以发现，这两个字串都是一种类型的了：从某一个字符向两边对称。再考虑这个字串的长度，因为在每个字符的右边加了一个’#’，又在字符串末尾加了一个’#’，所以有 S_{处理后字符串}=S_原字符串*2+1。

我们在暴力找回文子串的时候，是枚举当每个字符为一个回文子串的中心，再向两边暴力拓展。在这里我们可以把每一个以第i个字符为中心的最长回文子串的半径记为P[i] (我们考虑半径就是$(Len+1)/2$ ,反推则回文子串长度为$2*P[i]-1$)

接下来我们考虑一个问题，ABCBABCBA这个字符串，我把它的P数组记录下来：

i	0	1	2	3	4	5	6	7	8
P[i]	1	1	3	1	5	1	3	1	1

我们先考虑P[2]，P[2]的最长回文子串为：ABCBA。我们再考虑P[6]，P[6]的最长回文子串也为：ABCBA。排除巧合的可能，真相只有一个，这一定有什么原因在里面。我们考虑第4位，不难发现，由第4位拓展出的回文子串覆盖了0~8位字符。那么，0~3位和5~8位应该是完全对称的！所以我们算到在第4位后面的字符的时候，它的初始P[i]就应该是对称回去的P值！

接下来我们考虑怎么实现这个对称优化：我们维护两个值，mx，id。mx表示算到现在之前的回文子串所覆盖到的最右点，id表示覆盖到该最右点的子串的中心点。在计算某一个字位的P值时，我们先看一下该字位是否在之前的回文子串所覆盖的范围内，如果在，则该P值先赋为对称过去的那个点的P值。但是，我们还得注意，对称过去的P值有可能会超出了id所在回文子串的覆盖范围。碰到这种情况，只需要在P[id*2-i]和mx-i取min值就行了。另外当当前字位不在mx范围内，不妨先把半径设为1，表示目前可知最大回文就是它本身。赋完初值后，接下来再暴力向外拓展就行了。

if (mx>i) p[i]=min(p[id*2-i],mx-i);
else p[i]=1;
for (int j=i+p[i];j<s.size();j++){
	if (j>mx) mx=j,id=i;
	if (s[j]==s[2*i-j]) p[i]++;
	else break;
}

现在我们知道了字符串每一位的P值，我要是想知道以某一位(一般来讲是求最大位)为中心的回文子串在原串中的起始位置呢？

我们考虑一下，字符串是”%QXQ”这种情况。现在我们知道的P值，是以”#%#Q#X#Q#”为基础的。考虑’X’位，它的半径是4，在处理后的字串中位置是5。当我们用该位置减去(半径/2)(半径中原字符和’#’数量相等)，就得到了在回文子串前一位的字符’%’的位置。我们可以发现，前面的原字符和’#’数量也等，于是也要除以2。于是我们得到了这样的公式（设处理后字符的位置为W₀​）：W_原字符=(W₀+1-P[W₀])/2 (要注意字符串开头标号是0哦)

这样我们得到了以下代码：

#include<bits/stdc++.h>//祈福无Bug
#define N 100005

using namespace std;

string change(string &s){
	string ans="#";
	for (int i=0;i<s.size();i++){
		ans.push_back(s[i]);
		ans.push_back('#');
	}
	return ans;
}

string str;
int p[N];
int mx,id;

int manacher(string &s){
	int ans=0;mx=0;
	for (int i=0;i<s.size();i++){
		if (mx>i) p[i]=min(p[id*2-i],mx-i);
		else p[i]=1;
		for (int j=i+p[i];j<s.size();j++){
			if (j>mx) mx=j,id=i;
			if (s[j]==s[2*i-j]) p[i]++;
			else break;
		}
		ans=max(ans,p[i]);
	}
	return ans-1;
}

int main(void){
	cin>>str;
	str=change(str);
	cout<<manacher(str)<<endl;
}

我们考虑他的复杂度，这个算法求解就是一个对mx更新的过程，对mx的更新是线性的，所以考虑复杂度为$O(n)$。

对马拉车算法的应用(在模拟赛中是马翻车)

Problem B. 序列

输入文件： sequence.in

输出文件： sequence.out

时间限制： 1 秒

内存限制： 512 MiB

题目描述：

对于一个长度为偶数的序列 a1, a2, a3, . . . , an，定义这个序列为好的序列，当且仅当 a1 + an = a2 + an−1 = a3 + an−2 = . . . = a n2+ a n2 +1。定义一个对序列的翻滚操作，使所有元素向前移一个位置，第一个元素移到最后的位置。现在小 A 有一个长度为偶数的序列 b1, b2, b3, . . . , bn，他想知道至少需要翻滚多少次才能使这个序列成为好的序列。

输入：

第一行一个整数 n 表示序列的长度，保证 n 为一个偶数。第二行 n 个正整数，第 i 个数表示 bi。

输出：

如果有解，输出一个正整数，表示最少需要翻滚多少次才能使这个序列成为好的序列。如果没有解，输出 IMPOSSIBLE。

样例输入：

6

2 8 7 9 1 3

样例输出：

1

限制：

对于 30% 的数据，n ≤ 1000。

对于 60% 的数据，n ≤ 200000。

对于 100% 的数据，n ≤ 1000000，bi ≤ 1000000。

咋一看这道题，非常棘手，但是在经过我两个小时的仔细思考后，我还是觉得非常棘手。
我们可以观察一下样例，对成功变化过的样例相邻两数做差。

我们发现了什么！回……回文子串！

对于任意这个数列中相对的任意两组数，我们把他设为 a b B A，a+A=b+B，进行简单的移位后，我们得到a-b=B-A，两两相邻的数相减，就可以得到一个回！文！数！列！所以求差后的如果能得到回文序列的序列，就是”好的序列”！

接下来我们考虑进行马拉车了。考虑一个有解的数列，它一定是由两个”好的序列”构成的。假设一个”好的序列”，将它的最后一位移到第一位，第一位与原第二位相加还是符合原数列的标准，所以第一位和第二位可以构成一个”好的序列”。再把后面的数移上来……以此类推。

那么接下来我们的任务就是找到两个刚好填满空间的回文序列，并且使前一个序列尽可能小。 我们考虑回文序列为数组b，原序列为数组a。

b[i]=a[i-1]-a[i];

于是从前往后枚举，判断每一位作为前一个回文序列的中心，写下以下代码：

if (p[i]==i && p[n/2+i]==n/2-i+1){
		printf("%d\n",i-1);
		return 0;
	}

其中计算i对应的另外一个序列的中心的位置很容易算错……

完整代码以下：

#include<bits/stdc++.h>//祈福无Bug
#define N 1000005
#define INF 10000005
#define min(x,y) ((x<y)?(x):(y))
#define max(x,y) ((x>y)?(x):(y))

using namespace std;

int n;
int a[N],b[N],p[N];

void read(int &x){
	char c;
	while((c=getchar())<'0' || c>'9');
	x=c-'0';
	while((c=getchar())>='0' && c<='9')
		x=x*10+c-'0';
}

int main(void){
	//freopen("sequence8.in","r",stdin);
	read(n);
	for (int i=1;i<=n;i++) read(a[i]);
	a[0]=a[n];
	for (int i=1;i<=n;i++) b[i]=a[i-1]-a[i];
	b[0]=INF;b[n+1]=-INF;
	
	int mx=1,id=p[1]=1;
	for (int i=2;i<=n;i++){
		if (i<=mx) p[i]=min(p[id*2-i],mx-i+1);
		else p[i]=1;
		while (b[i+p[i]]==b[i-p[i]] && i+p[i]<=n) p[i]++;
		if (mx<i+p[i]-1) mx=i+p[i]-1,id=i;
	}
	for (int i=1;i<=n;i++){
		if (p[i]==i && p[n/2+i]==n/2-i+1){
			printf("%d\n",i-1);
			return 0;
		}
	}
	printf("IMPOSSIBLE\n");
}

咕咕咕！QXQ快找彩蛋！