A Asya And Kittens：每次合并两个集合时新建一个父节点，左右儿子分别指向两个集合的根，并查集维护。最后得到一棵二叉树，DFS先左后右输出叶子编号，就是还原的原始序列。

code

#include <bits/stdc++.h>
using namespace std;
const int N = 1.5e5 + 5;
int n, head[N << 1], edgecnt, headcnt, fa[N << 1], l[N << 1], r[N << 1];
int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void uni(int x, int y) {
	++headcnt;
	x = find(x);
	y = find(y);
	l[headcnt] = x;
	r[headcnt] = y;
	fa[x] = fa[y] = headcnt;
	return;
}
void dfs(int x) {
	if(l[x] == 0 && r[x] == 0) {
		printf("%d ", x);
		return;
	}
	dfs(l[x]);
	dfs(r[x]);
	return;
}
int main() {
	scanf("%d", &n);
	headcnt = n;
	for(int i = 1; i <= 2 * n; i++) fa[i] = i;
	for(int i = 1, u, v; i < n; i++) {
		scanf("%d%d", &u, &v);
		uni(u, v);
	}
	dfs(headcnt);
	return 0;
}

B String Transformation 1：对每对(s1[i], s2[i])，若s1[i]>s2[i]则无解。否则将字母看成26个节点，连有向边s1->s2，用并查集维护连通块，每合并一次答案加1，统计总合并次数。

code

#include<bits/stdc++.h>
using namespace std;
int f[30];
int ans;
int find(int x) {
	return f[x] == x ? x : f[x] = find(f[x]);
}
void uni(int x, int y) {
	int rx = find(x), ry = find(y);
	if (rx != ry) {
		f[rx] = ry;
		ans++;
	}
}
void solve() {
	int n;
	string s1, s2;
	cin >> n >> s1 >> s2;
	for(int i = 1; i <= 26; i++) f[i] = i;
	ans = 0;
	bool ok = true;
	for(int i = 0; i < n; i++) {
		if (s1[i] > s2[i]) {
			cout << -1 << '\n';
			ok = false;
			break;
		}
		uni(s1[i] - 'a' + 1, s2[i] - 'a' + 1);
	}
	if(ok) cout << ans << '\n';
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--) {
		solve();
	}
	return 0;
}

C Phase Shift：贪心构造替换表。从左到右处理s的每个字符，若已有映射则跳过；否则从a到z找未使用的字符，且要保证不会形成长度小于26的环，用DFS检查合法性，找到后建立映射。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t, n;
string s;
char son[130];
bool vis[130], dis[130];
bool check(ll u, ll cnt) {
    if(vis[u]) return cnt == 26;
    vis[u] = 1;
    if(son[u] == '-') return true;
    ll v = son[u] - 96;
    return check(v, cnt + 1);
}
int main() {
    cin >> t;
    while(t--) {
        cin >> n >> s;
        for(int i = 1; i <= 26; i++) {
            son[i] = '-';
            dis[i] = 0;
        }
        ll sum = 26;
        for(int i = 0; i < n; i++) {
            ll p = s[i] - 96;
            if(son[p] != '-') continue;
            for(int j = 1; j <= 26; j++) {
                if(dis[j]) continue;
                for(int k = 1; k <= 26; k++) vis[k] = 0;
                vis[p] = 1;
                if(check(j, 1)) {
                    son[p] = char(j + 96);
                    dis[j] = 1;
                    break;
                }
            }
        }
        for(int i = 0; i < n; i++) {
            ll p = s[i] - 96;
            cout << son[p];
        }
        cout << endl;
    }
    return 0;
}

D Perfect Security：将数组p建01字典树，对每个a[i]在树上贪心查询异或值最小的p[j]（优先走与a[i]当前位相同的分支），查询后删除该节点，输出异或结果。

code

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
const int NODE = 30 * N;
int son[NODE][2], cnt[NODE], idx;
int n;
int a[N], p[N];
void insert(int x) {
	int u = 0;
	for(int i = 30; i >= 0; i--) {
		int bit = (x >> i) & 1;
		if(!son[u][bit]) son[u][bit] = ++idx;
		u = son[u][bit];
		cnt[u]++;
	}
}
int query(int x) {
	int u = 0;
	int p = 0;  
	for(int i = 30; i >= 0; i--) {
		int bit = (x >> i) & 1;
		if(son[u][bit] && cnt[son[u][bit]] > 0) {
			u = son[u][bit];
			p |= (bit << i);
		} else {
			u = son[u][bit ^ 1];
			p |= ((bit ^ 1) << i);
		}
		cnt[u]--;
	}
	return (x ^ p);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) {
		cin >> p[i];
		insert(p[i]);
	}
	for(int i = 1; i <= n; i++) {
		cout << query(a[i]) << " ";  
	}
	cout << "\n";
	
	return 0;
}

E Correct Bracket Sequence Editor：栈预处理括号匹配位置，双向链表维护序列。删除时找到匹配括号对，将左右端点连接，光标移到右端点右侧或左端点左侧，最后按链表顺序输出剩余字符。

code

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int len, oplen, pos;
string s;
string op;
int kpos[N], l[N], r[N];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> len >> oplen >> pos;
	cin >> s >> op;
	s = ' ' + s;
	stack<int> st;
	for(int i = 1; i <= len; i++) {
		if(s[i] == '(') {
			st.push(i);
		} else {
			kpos[i] = st.top();
			kpos[st.top()] = i;
			st.pop();
		}
	}
	for(int i = 1; i <= len; i++) {
		l[i] = i - 1;
		r[i] = i + 1;
	}
	r[0] = 1;
	l[len + 1] = len;
	for(char c : op) {
		if(c == 'L') {
			pos = l[pos];
		} else if(c == 'R') {
			pos = r[pos];
		} else {
			int ll = min(pos, kpos[pos]);
			int rr = max(pos, kpos[pos]);
			int lnode = l[ll];
			int rnode = r[rr];
			r[lnode] = rnode;
			l[rnode] = lnode;
			if(rnode != len + 1) {
				pos = rnode;
			} else {
				pos = lnode;
			}
		}
	}
	int cur = r[0];
	while(cur != len + 1) {
		cout << s[cur];
		cur = r[cur];
	}
	cout << "\n";
	return 0;
}

F Prefix-Suffix Palindrome：先去掉两端已匹配的最长回文前后缀，剩余中间部分找最长回文前缀或后缀作为中心，拼接前缀+中心+后缀即为答案。

code

#include<bits/stdc++.h>
using namespace std;
bool huiwen(string s) {
    int i = 0, j = s.size() - 1;
    while(i < j) {
        if(s[i] != s[j]) return 0;
        i++;
        j--;
    }
    return 1;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--) {
        string s;
        cin >> s;
        int n = s.size();
        int i = 0, j = n - 1;
        while(i < j && s[i] == s[j]) {
            i++;
            j--;
        }
        if(i >= j) {
            cout << s << "\n";
            continue;
        }
        string a = s.substr(0, i);
        string b = s.substr(j + 1);
        string m = s.substr(i, j - i + 1);
        string ans = "";
        for(int len = 1; len <= m.size(); len++) {
            string t = m.substr(0, len);
            if(huiwen(t) && t.size() > ans.size()) {
                ans = t;
            }
        }
        for(int len = 1; len <= m.size(); len++) {
            string t = m.substr(m.size() - len);
            if(huiwen(t) && t.size() > ans.size()) {
                ans = t;
            }
        }
        cout << a + ans + b << "\n";
    }
    return 0;
}