题目大意

一个长度为 \(n\) 的字符串 \(S\)，进行以下操作。

假设 \(s\) 为 acbdef，每一次将首字母移至末尾，得到 \(6\) 个字符串：

acbdef
cbdefa
bdefac
defacb
efacbd
facbde

将每个字符串的首字母排序：

acbdef
bdefac
cbdefa
defacb
efacbd
facbde

每个字符串的末尾连在一起为 fcabde，这就是 \(S'\)。

最后让你反推出 \(S\)。

解题思路

1. 原串将首字母移至末尾就得到构造串。
2. 构造的第一个串就是原串。
3. 构造的其余字符串的“末尾字符”是“该串首字母”在“原串 \(ans[\ ]\) ”中的前一个字符。
4. 维护 \(cur\) 表示 \(s1[\ ]\) 的位置，则 \(s_{cur}\) 是 \(s1_{cur}\) 的前一个字符。
5. 倒序确认原串的位置，因为倒序的字符在 \(s1[\ ]\) 中寻找是有序的，反之正序确认则需要在 \(s[\ ]\) 中找，是无序的。

代码

#include<bits/stdc++.h>
using namespace std;
int n, p, cur;
char s[10005], s1[10005], ans[10005]; // s1表示排序后的串，s表示排序前的串
bool vis[10005];
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> s[i];
		s1[i] = s[i];
	}
	cin >> p;
	sort(s1 + 1, s1 + n + 1);
	ans[1] = s[p]; // 首字母确认
	for(int i = 1; i <= n; i++) {
		if(s1[i] == s[p]) {
			cur = i; // 找构造的第一个串编号
			break;
		}
	}
	for(int i = n; i >= 2; i--) { // 倒序确认位置
		vis[cur] = 1; // 标记s1[cur]已经使用
		ans[i] = s[cur]; // 原串i个位置的字母就是s[cur]
		for(int j = n; j >= 1; j--) {
			if(s1[j] == s[cur] && !vis[j]) {
				cur = j;
				break;
			}
		}
	}
	for(int i = 1; i <= n; i++) {
		cout << ans[i];
	}
	return 0;
}