fdfsdf
名称:字符串
来源:2019年陕西省选
题目内容
传送门
-
题目描述
给出一个长度为$n$的由小写字母组成的字符串$a$,设其中第$i$个字符为$a_i(1≤i≤n)$。
设删掉第$i$个字符之后得到的字符串为$s_i$,请按照字典序对$s_1,s_2,……,s_n$从小到大排序。若两个字符串相等,则认为编号小的字符串字典序更小。输入&&输出
格式
输入
第一行一个整数$n$。
第二行一个长为$n$的由小写字母组成的字符串$a$。输出
输出一行$n$个整数¥k_1,k_2,……,k_n$,用空格隔开。表示$s_{k_1}<s_{k_2}<……<s_{k_n}$。
样例
输入
7
aabaaab
输出
3 7 4 5 6 1 2
数据范围
对于所有数据,$1\leq n\leq10^6$。
对于10%的数据,$1\leq n\leq2000$。
对于另外20%的数据,$1\leq n\leq10^5$。且任意两个相邻字符$a_i,a_{i+1}$不相等;
对于另外30%的数据,$1\leq n\leq10^5$。
对于余下40%的数据,无特殊限制。
提示
本题不需要SA或者SAM等高级算法。
题解
10分
暴力构造出$s$,再用快速排序进行排序。时间复杂度为$O(n^2log(n))$,在$n\leq2000$的数据下跑得过。
30分
注意到:其中20%的数据没相邻两个字符不相等。
引理
当其任意两个字符不相等时,$s_i$和$s_j(i<j)$的大小关系实际上就是$a_{i+1}$与$a_i$的大小关系。
证明:由题意得。
$$
s_i[1……i-1]=a[1……i-1]=s_j[1……i-1]\
s_i[j……n-1]=a[j+1……n]=s_j[j……n-1]
$$
重点在于比较$s_i[i……j-1]$和$s_j[i……j-1]$的大小关系。
$s_i[i……j-1]$正对应$a[i+1……j]$;
$s_j[i……j-1]$正对应$a[i……j-1]$;
而$a[i+1]!=a[i]$,故二者的大小关系可以确定。于是,我们可以开一个双端队列。逆序处理整个字符串。
当我们发现$a[i+1]<a[i]$时,则说明$s_i$比后面的(即已经被处理过放进双端队列里的)都要小,就把数字$i$放在双端队列的前面;否则说明$s_i$比后面的都要大,就把它放在双端队列的后面。
start=>start: 开始处理状态i
cmp=>condition: a[i+1]<a[i]
front=>operation: 将i插在双端队列前面。
back=>operation: 将i插在双端队列后面
end=>end: 进入下一轮操作
start->cmp
cmp(yes)->front->end
cmp(no)->back->end
最后我们按顺序将双端队列每一个位置上的数字。
100分
那么,我们如何拿到100分呢???
实际上,我们只需要将原来30分的做法进行扩展,或者说将所有情况转换为两两相邻字符不相等的情况就行。
引理
当$a[i]=a[i+1]$时,$s[i]=s[i+1]$
证明略由此,我们就可以将字符串连续相同的一段进行压缩,其中每一个字母都代表着原字符串的一段区间。
例如$"bbbcaa"$压缩成$"bca"$,并且处理出来如下数据:
|字母|开始位置|结束位置|
|:-|-|-|
|b|1|3|
|c|4|4|
|a|5|6|
将压缩后的串排序得$3\quad1\quad2$。
将原来处理出来的数据带入得$(5\quad6)(1\quad2\quad3)(4)$。
//C++
#include<iostream>
#include<stdio.h>
#include<string>
#include<deque>
using namespace std;
const int nn=1000001;
inline void output(long long o);
int start[nn],final[nn];
inline long long input();
string a;
deque<int>k;
int main()
{
int n=input(),size=0;
cin>>a;
for(int i=0,PREV=0;i<n;i++)
{
PREV=i;
while(a[i]==a[i+1]&&i<n)i++;
a[size]=a[i],start[size]=PREV+1,final[size++]=i+1;
}
for(int i=size-1;i>=0;i--)
if(a[i+1]<a[i])k.push_front(i);
else k.push_back(i);
for(;k.front()!=k.back();k.pop_front())
for(int i=start[k.front()],f=final[k.front()];i<=f;i++)output(i),putchar(' ');
for(int i=start[k.front()],f=final[k.front()];i<f;i++)output(i),putchar(' ');
output(final[k.front()]),putchar('\n');
return 0;
}
inline void output(long long o)
{
if(o<0)putchar('-'),o=-o;
if(o>=10)output(o/10);
putchar(o%10^'0');
}
inline long long input()
{
bool positive=true;
char now=getchar();
long long i=0;
for(;!isdigit(now);now=getchar())
if(now=='-')positive=!positive;
for(;isdigit(now);now=getchar())i=(i<<3)+(i<<1)+(now^'0');
return positive?i:-i;
}
最新文章
- swift-可选值
- JS组件系列——分享自己封装的Bootstrap树形组件:jqTree
- [Python &; Machine Learning] 学习笔记之scikit-learn机器学习库
- MVC:上传文件
- 0环境设置 - Statspack设置
- Forget asp.net membership,ASP.NET Identity Overview
- firefox HackBar组件模拟请求POST请求
- YII学习(第一天)
- HTTP POST和GET的区别[转]
- 第二章排错的工具:调试器Windbg(下)
- CSDN编程挑战——《高斯公式》
- svn签出单个文件
- Centos下安装mysql 和挂载硬盘
- VueJs(12)---vue-router(导航守卫,路由元信息)
- 根据dateFormatter创建NSDate类型数据
- UnicodeEncodeError: &#39;gbk&#39; codec can&#39;t encode character &#39;\xee&#39;
- thinkphp5.1 使用success();和error();要注意的点
- 快速排序的两种实现方法(js)
- 25 个常用的 Linux iptables 规则
- 使用entitiy
热门文章
- vue中el-upload上传多图片且携带参数,批量而不是一张一张的解决方案
- 物联网网关MQTT应用与配置测试介绍
- 基于Spring框架应用的权限控制系统的研究和实现
- oracle 正确删除归档日志,并清除 V$ARCHIVED_LOG 数据
- iview中page组件的跳转功能BUG解决方案
- Two types of people with high scores of English exams
- APPCAN &#160; 版本控制SVN
- Css3动画效果,彩色文字效果,超简单的loveHeart
- JVM 内存模型概述
- vi编辑器基础指令