题目

题意

给定小写字符组成的字符串s，它经过加密后转化为t。
加密规则为，选取一个由26个小写字符组成 的字符环；对于每个字符，它加密后，会转化为它在字符环的下一个字符。

现给定加密后的字符串t，问如何构造由26个小写字符组成 的字符环，使得原始的字符串s，字典序最小。输出对应的、字典序最小的字符串s。

思路

模拟，枚举t上每个元素，尽量为它选取当前能选的、最小的元素去做映射。

注意，因为最终要求是个长度为26的字符环。因此，需要注意判环。

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int maxn = 200010;int n;
char s[maxn];
int pre[26], nxt[26];
bool is_circle(int k, int exp) {while (k != -1) {if (k == exp) {return true;}k = nxt[k];}return false;
}
void solve() {scanf("%d", &n);scanf("%s", s);memset(pre, -1, sizeof(pre));memset(nxt, -1, sizeof(nxt));int tot = 0;for (int i = 0; i < n; ++i) {int cur = s[i] - 'a';for (int k = 0; k < 26; ++k) {if (nxt[k] == cur) { // already assigned.break;}if ('a' + k == s[i] || // case1: should choose self as pre characternxt[k] != -1 && nxt[k] != cur || // case2: nxt[k] exist, nxt[k] != cur.pre[cur] != -1 && pre[cur] != k) { // case3: pre[cur] exist, pre[cur] != kcontinue;}// case4: circle judgeif (pre[k] != -1 && nxt[cur] != -1 && tot != 25 && is_circle(cur, k)) {continue;}++tot;nxt[k] = cur;pre[cur] = k;break;}s[i] = pre[cur] + 'a';}printf("%s\n", s);
}int main() {int t;scanf("%d", &t);while (t--) {solve();}
}
/*
cdaabd
*/