构造+置换环,CF 1983D - Swap Dilemma
目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
1983D - Swap Dilemma
二、解题报告
1、思路分析
首先二者的元素集合必须相同
我们可以将二者离散化为排列
考虑一个数组变化的同时另一个数组也变化太过于复杂,我们考虑先将数组a 经过交换变为升序
然后再考虑将数组b 变为一个升序排列
但是数组a也会变化呀
我们考虑 每次对 b 施加相邻元素交换, 来一步步消除逆序对
同时对a 施加 swap(a[0], a[1]),那么如果a 和 b 能都变相等,即升序排列,那么二者的逆序对的奇偶性应该相同
到这里这道题就能做了
但是还可以从置换环的角度考虑
每次交换,逆序对的奇偶性翻转,置换环的奇偶性呢?
考虑相邻元素在两个环:那么两个环将合并
考虑相邻元素在一个环:那么将分裂成两个环
所以:置换环和逆序对的奇偶性变化是等价的
对于排列而言,我们可以O(N)求出置换环的数目
2、复杂度
时间复杂度: O(NlogN)空间复杂度:O(N)
3、代码详解
#include <bits/stdc++.h>
// #define DEBUG
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
int parity(const std::vector<int> &p) {
int n = p.size();
std::vector<bool> vis(n);
int res = 0;
for (int i = 0; i < n; ++ i) {
if (vis[i]) {
continue;
}
for (int j = i; !vis[j]; j = p[j]) {
vis[j] = true;
}
res ^= 1;
}
return res;
}
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n), b(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
for (int i = 0; i < n; ++ i) {
std::cin >> b[i];
}
std::vector<int> ida(a), idb(b);
std::ranges::sort(ida);
std::ranges::sort(idb);
if (ida != idb) {
std::cout << "NO\n";
return;
}
for (int &x : a) {
x = std::lower_bound(ida.begin(), ida.end(), x) - ida.begin();
}
for (int &x : b) {
x = std::lower_bound(idb.begin(), idb.end(), x) - idb.begin();
}
if (parity(a) == parity(b)) {
std::cout << "YES\n";
} else {
std::cout << "NO\n";
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
#ifdef DEBUG
int START = clock();
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t = 1;
std::cin >> t;
while (t --) {
solve();
}
#ifdef DEBUG
std::cerr << "run-time: " << clock() - START << '\n';
#endif
return 0;
}
原文地址:https://blog.csdn.net/EQUINOX1/article/details/143313944
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/369712.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/369712.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!