C. Phase Shift（模拟/链表）

题目

题意

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

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

思路

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

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

代码

#include 
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