题解 P5329 【[SNOI2019]字符串】
千年知乎_天才
2019-09-06 07:59:24
题目名称：字符串
来源：2019年陕西省选
# 博客链接
- [博客园](https://www.cnblogs.com/Alvin-Tree/p/11468582.html)
- [CSDN](https://blog.csdn.net/weixin_43890363/article/details/100547332)
- [洛谷博客](https://www.luogu.org/blog/131abc155-7341-6424/solution-p5329)
- [洛谷题解](https://www.luogu.org/problemnew/solution/P5329)
# 提示
本题不需要**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$比后面的都要大，就把它放在双端队列的后面。
最后我们按顺序将双端队列每一个位置上的数字。
## 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)$。
```cpp
//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;
}
```