【bzoj4319】cerc2008 Suffix reconstruction 贪心
2024-09-08 10:26:05
题目描述
话说练习后缀数组时,小C 刷遍 poj 后缀数组题,
各类字符串题闻之丧胆。就在准备对敌方武将发出连环杀时,对方一记无中生有,又一招顺手牵羊,小C 程序中的原字符数组就被牵走了。幸运的是,小C 早已经求出了 SA[],为了能东山再起,迅速 A 掉此题,他希望各位忠臣们能帮忙求出一组原字符数组的可行方案。已知原字符数组由小写拉丁字母组成。且小C的SA[]也是有可能求错的, 原数组可能不存在。
输入
输入文件只有一行且为用空格隔开的一个正整数 N。
接下来一行有 N 个数,为 1~N 的排列。
其中对于 100%的数据 N≤500000
输出
一行有 N 个小写拉丁字母,若不存在合法方案输出-1;
样例输入
4
2 3 4 1
样例输出
baab
题解
贪心
首先我们肯定是按照sa的顺序按照字典序从小到大设置字母,且尽量小。
那么我们只需要判断在确定一个新位置时能否放原来的字母。
根据sa的求法,我们比较两个后缀的大小时,如果第一位相同则比较后面的大小,相当于比较下一个后缀的rank。
所以我们可以先根据sa得到rank,比较时直接比较下一位字符串的rank的大小关系,如果新添加的位置的下一位字符串rank比上一个小,则需要增加新字母,否则不需要。
说了这么多还是不如直接看代码直白~
#include <cstdio>
#define N 500010
int sa[N] , rank[N];
char str[N];
int main()
{
int n , i;
char ch = 'a';
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &sa[i]) , rank[sa[i]] = i;
str[sa[1]] = ch;
for(i = 2 ; i <= n ; i ++ )
{
if(rank[sa[i] + 1] < rank[sa[i - 1] + 1]) ch ++ ;
if(ch > 'z')
{
printf("-1\n");
return 0;
}
str[sa[i]] = ch;
}
printf("%s\n" , str + 1);
return 0;
}
最新文章
- c#解析XML到DATASET及dataset转为xml文件函数
- Net作业调度(三) — Quartz.Net进阶
- SqlServer删除表中重复记录
- U-Mail邮件网关提醒:谨防像素图片钓鱼窃密
- .NET笔记(一)
- 使用socket()函数创建套接字
- SVN使用教程总结[转]
- 有return语句情况下,try-catch-finally的执行顺序
- jQuery源代码阅读之一——jQuery总体结构及jQuery构造函数
- 基础向量运算-2D镜面反射
- atitit.压缩算法 ZLib ,gzip ,zip 最佳实践 java .net php
- Tachyon框架的Worker心跳及Master高可用性分析
- matlab常用小函数(一)
- kafka安装与使用
- Web.config配置和节点介绍
- NGUI使用教程(2) 使用NGUI创建2D场景而且加入标签和button
- 自用lca模板
- 常用LINQ关键字用法汇总
- 神州数码广域网PPP封装PAP认证配置
- day12 Python数字,字符串,列表,元祖,字典总结