题目描述

给出一个只包含小写字母的字符串的长度、以每一个字符为中心的最长回文串长度、以及以每两个相邻字符的间隙为中心的最长回文串长度，求满足条件的字典序最小的字符串。

输入

输入由三行组成。

第一行仅含一个整数N，表示密码的长度。

第二行包含N 个整数，表示以每个字符为中心的最长回文串长度。

第三行包含N - 1 个整数，表示每两个相邻字符的间隙为中心的最长回文串长度。

1 <= n <= 10^5。 

输出

输出仅一行。输出满足条件的最小字典序密码。古籍中的信息是一定正确的，故一定存在满足条件的密码。 

样例输入

Sample #1

3

1 1 1

0 0

Sample #2

3

1 3 1

0 0

Sample #3

3

1 3 1

2 2

样例输出

Sample #1

abc

Sample #2

aba

Sample #3

aaa

---

题解

逆模拟Manacher

本题和 类似，只不过变成了回文串长度。

那么可以考虑逆模拟Manacher算法的过程：从上一个已经确定的回文串位置开始，到当前回文半径结束，这些串都满足回文串的性质，所以后面的字符可以直接由前面的字符确定。

而如果当一个字符没有确定，此时的情况较那题更难处理——一个位置结尾的所有回文串。

我们不妨换一个思路：当一个位置达到最大回文长度时，说明下一个长度不再满足回文串的性质。因此可以直接对于每个位置开一个大小为26的桶，当达到最大回文长度时，就让后面的下一个字符与前面的上一个字符标记为不同。当一个字符没有确定时，就在其对应的桶中找到字典序最小的字符，设为当前字符。

时间复杂度$O(26n)$。

#include 
     
      #include 
      
       #include 
       
        using namespace std;char str[200010];int p[200010] , vis[200010][26];int main(){	int n , i , j , mx = 0 , last;	scanf("%d" , &n);	for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &p[i * 2 - 1]);	for(i = 1 ; i < n ; i ++ ) scanf("%d" , &p[i * 2]);	str[0] = '#';	for(i = 1 ; i <= n * 2 - 1 ; i ++ )	{		if(mx < i)		{			for(j = 0 ; j < 26 ; j ++ )				if(!vis[i][j])					break;			str[i] = j + 'a';		}		for(j = (mx >= i ? min(mx - i + 1 , p[2 * last - i]) : 1) ; j <= p[i] ; j ++ ) str[i + j] = str[i - j];		if(i > p[i]) vis[i + p[i] + 1][str[i - p[i] - 1] - 'a'] = 1;		if(i + p[i] > mx) mx = i + p[i] , last = i;	}	for(i = 1 ; i < n * 2 ; i += 2) putchar(str[i]);	printf("\n");	return 0;}