当前位置: 首页 > article >正文

构造+置换环,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

相关文章:

  • 计算机网络:网络层 —— IP数据报的发送和转发过程
  • php伪协议和move_uploaded_file、rename、copy等文件操作
  • 【python】OpenCV—WaterShed Algorithm(1)
  • 控制卸载/安装应用
  • Chromium HTML5 新的 Input 类型date 对应c++
  • C++基于opencv的视频质量检测--画面冻结检测
  • Vue3中ref、toRef和toRefs之间有什么区别?
  • 基于SSM+微信小程序的快递的管理系统(快递1)
  • 基于脚手架创建前端工程
  • Linux 应用领域
  • 老电脑不能装纯净版windows
  • GEE APP:加载Landsat TOA数据可视化界面,实现点击提取ndvi值
  • 云原生后端开发教程
  • Python实现微博舆情分析的设计与实现
  • 存储服务器通常适用于哪些应用场景?
  • Spring版本有哪些
  • 回溯算法习题其二-Java【力扣】【算法学习day.16】
  • 外包功能测试就干了4周,技术退步太明显了。。。。。
  • 深入理解JavaScript:两大编程思想和ES6类以及对象概念解析
  • 100种算法【Python版】第17篇——Aho-Corasick算法