CF1656G Cycle Palindrome
ZXT的优点在于不怕代码丑，因为他是Elephant，他认为打很丑的代码是一种光荣
切的首道3200，发个题解庆祝一下
Problem
给一个串，找到一个循环置换，使得这个串变成回文串
没看懂对吧
-
置换
假设原序列是 \(a\)，新序列是 \(b\) ，置换是 \(p\)
那么 \(b_i=a_{p_i}\)
-
循环置换
我们定义 \(u\) 为任意下表
每次 \(u=p_u\)
发现 \(u\) 完整遍历了 \([1,n]\) 这个区间，则为循环置换
Solution
初步判断无解
令 \(cnt_{a_i}\) 为 \(a_i\) 出现的个数，\(s\) 为 \(cnt_{a_i}\) 为奇数的个数
显然 \(s > 1\) 是无论如何也构造不出来的
如果 \(s = 1\) 并且 \(n\) 是偶数也是无解
构造回文
考虑先处理回文条件
我们刚刚处理了 \(cnt\)，不妨开桶记录每个值出现的下标
我们遍历每个值 \(i\)
如果 \(cnt_i\) 为奇数，那么将它的末尾元素放在序列 \(p\) 中间
否则将其两两配对，放在两边
构造循环
对于每个数连一条 \(i\to p_i\) 的边
用并查集来维护这样的关系
发现当前图上面是由很多小的循环组成的
就像这样
然后我们想让整个序列成为一个大环
我们可以交换 \(p_i\) 和 \(p_j\) 的值
也就是这样
然后它们就合并了！
想一想可以交换 \(p_i\) 和 \(p_j\) 的值的条件
只有 \(a_{p_i}\) 和 \(a_{p_j}\) 在同一集合才能交换
事实上，在代码实现中，我们不需要枚举 \(i、j\)
我们可以将 \(a_{p_i}\) 为权值装一个桶
然后将遍历整个桶
直接将同一 \(a_{p_i}\) 的所有下标，连向桶的第一个，交换权值
然后就可以实现环的合并了
除了这个情况，还有没有什么合法的合并呢
考虑第 \(i\) 个点不在第一个点（大环）上
但是 \(p_i\) 和 \(p_j\) 我们都交换完了
但是考虑回文的性质
两个局部可以完全互换！
我们直接交换 \([1,i]、[n,n-i+1]、[i,n]\)
观察前后序列不变
回到图上
相当于这样
接下来就是愉快的代码了
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, a[N], cnt[N], fa[N], p[N];
vector <int> e[N], vec[N];
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
void merge(int x, int y) {int fx = find(x), fy = find(y);if (fx != fy) fa[fx] = fy;
}
void solve() {cin >> n;for (int i = 1; i <= n; i++) cnt[i] = 0, vec[i].clear();for (int i = 1; i <= n; i++) cin >> a[i], cnt[a[i]]++, vec[a[i]].emplace_back(i);int s = 0, x = 0;for (int i = 1; i <= n; i++) s += cnt[i] & 1, x |= (a[i] == 1);if (s >= 2 || (s == 1 && n % 2 == 0)) return cout << "No\n", void();int k = 1;for (int i = 1; i <= n; i++) {if (cnt[i] & 1) p[n / 2 + 1] = vec[i].back(), cnt[i]--;for (int j = 1; j <= cnt[i]; j += 2) p[k] = vec[i][j - 1], p[n - k + 1] = vec[i][j], k++;} for (int i = 0; i <= n; i++) fa[i] = i;for (int i = 1; i <= n; i++) merge(i, p[i]);for (int i = 1; i <= n; i++) vec[i].clear();for (int i = 1; i <= n; i++) vec[a[p[i]]].emplace_back(i);for (int i = 1; i <= n; i++)for (auto v : vec[i]) if (find(vec[i].front()) != find(v)) merge(vec[i].front(), v), swap(p[vec[i].front()], p[v]);for (int i = 2; i < n - i + 1; i++) if(find(1) != find(i)) merge(1, i), swap(p[1], p[i]), swap(p[n], p[n - i + 1]), swap(p[1], p[n]);for (int i = 2; i <= n; i++) if (find(1) != find(i)) return cout << "No\n", void();cout << "Yes\n";for (int i = 1; i <= n; i++) cout << p[i] << ' ';cout << '\n';
}
int main() {int t; cin >> t;while (t--) solve();return 0;
}