[SCOI2013]密码

NC20292. [SCOI2013]密码

描述

Fish 是一条生活在海里的鱼。有一天他很无聊，就到处去寻宝。他找到了位于海底深处的宫殿，但是一扇带有密码锁的大门却阻止了他的前进。通过翻阅古籍，Fish 得知了这个密码的相关信息：

1. 该密码的长度为N。

2. 密码仅含小写字母。

3. 以每一个字符为中心的最长回文串长度。

4. 以每两个相邻字符的间隙为中心的最长回文串长度。

很快Fish 发现可能有无数种满足条件的密码。经过分析，他觉得这些密码中字典序最小的一个最有可能是答案，你能帮他找到这个密码么？

注意：对于两个串A和B，如果它们的前i个字符都相同，而A的第i+1个字符比B的第i+1个字符小，那么认为是则称密码A 的字典序小于密码B 的字典序，例如字符串abc 字典序小于字符串acb。如果密码A的字典序比其他所有满足条件的密码的字典序都小，则密码A是这些密码中字典序最小的一个。

输入描述

输入由三行组成。
第一行仅含一个整数N，表示密码的长度。
第二行包含N 个整数，表示以每个字符为中心的最长回文串长度。
第三行包含N - 1 个整数，表示每两个相邻字符的间隙为中心的最长回文串长度。
对于20% 的数据，1 ≤ n ≤  100。
另有30% 的数据，1 ≤ n  ≤ 1000。
最后50% 的数据，1 ≤ n ≤  10^5。

输出描述

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

示例1

输入:

3
1 1 1
0 0

输出:

abc

示例2

输入:

3
1 3 1
0 0

输出:

aba

示例3

输入:

3
1 3 1
2 2

输出:

aaa

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 44ms, 内存消耗: 6756K, 提交时间: 2020-03-28 22:47:53

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
int n,len[N*2],ans[N];
bool t[N*2][26];
int get_mex(int x)
{
	for(int i=0;;i++)
	if(!t[x][i])
	return i;
}
void build()
{
	int mx=0,pos=0;
	for(int i=1;i<=n*2+1;i++)
	{
		if(i>mx&&!(i&1)) ans[i/2]=get_mex(i);
		if(i+len[i]-1>mx)
		{
			for(int j=max(mx+1,i+1);j<=i+len[i]-1;j++)
			if(!(j&1)) ans[j/2]=ans[(i*2-j)/2];
			mx=i+len[i]-1;
			pos=i;
		}
		if(i+len[i]-1==mx&&i*2-mx-1>0)
		t[mx+1][ans[(i*2-mx-1)/2]]=1;
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		len[i*2]=x+1;
	}
	for(int i=1;i<n;i++)
	{
		int x;
		scanf("%d",&x);
		len[i*2+1]=x+1;
	}
	len[1]=len[n*2+1]=1;
	build();
	for(int i=1;i<=n;i++)
	putchar(ans[i]+'a');
	return 0;
}

上一题

下一题

详情