自动搬运

查看原文

来自洛谷，原作者为

	MC_Launcher 多做题，少整没用的

搬运于2025-08-24 21:21:14，当前版本为作者最后更新于2020-06-16 17:41:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

发一弹题解啦

我第一眼看到这题就懵了，自己模拟一下，诶，有个规律！

什么规律呢，来，我放个图——等等，我先讲一下。

咱们先把输入的那个$S'$给按字典序排个序，然后捏，咱们就得到压缩前依次每个首字母了，那之前输入的那个不就是对应的尾字母吗？这玩意我之前照到了规律想了半天才想明白为哈。

接着呢，咱们再接着把这个尾字母变成首字母重复上述过程，到现在，细心的读者朋友们肯定能想到这是怎么回事了：这不是个环吗？首字母其实和尾字母连在一起的！然后一步步把这个环推出来，香！

好的现在可以放图了~~(作图粗糙，请原谅)~~。

恩好的大家已经看到一步步怎么推出来的了是吧，剩下就不用我赘术了就可以让我偷懒了

但是呢，我们正着写虽然直观易懂，但是会有错，可能有些字母会错位，我第一次正着排就才10分，所以我们要倒着找，最后反着输出，如果不理解，可以输出中间变量，然后也就懂了。

献上代码+注释

#include<bits/stdc++.h>//可食用头文件
using namespace std;
int main()
{
	int n,shou,now;//n为S串长度，shou即为题目中p，首字母所在压缩后的位置，now为现在进行到哪个位置了
	cin>>n;//输入
	char a[n],b[n],ans[n];//a——压缩串，b——字典序串，ans——答案串
	cin>>a>>shou;//万能cin
	for(int i=0;i<n;i++)b[i]=a[i];//a带给b
	sort(b,b+n);//自动排序
	for(int i=0;i<n;i++)//首先按首字母找到最后一个字母
	{
		if(b[i]==a[shou-1])
		{
			now=i;
			b[i]=')';//标记，退出
			break;
		}
	}
	ans[0]=a[now];//计入答案
	for(int i=1;i<n;i++)//ans[i]表示倒数第i+1个字母
	{
		for(int j=n-1;j>=0;j--)//从后往前搜到第一个与原char串匹配的字典序串
		{
			if(b[j]==a[now])
			{
				now=j;//更改现在所在位置，即跳到前一个字母
				ans[i]=a[now];//计入答案
				b[j]=')';//标记
				break;
			}
		}	
	}
	for(int i=n-1;i>=0;i--)cout<<ans[i];//倒序输出
}

MC_Launcher衷心提醒您：题解千万条，理解第一条。直接粘题解，棕名两行泪。