CF 1591D - Yet Another Sorting Problem
2022/1/13 23:03:50
本文主要是介绍CF 1591D - Yet Another Sorting Problem,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接:
https://codeforces.com/problemset/problem/1591/D
题目大意:
给定一个长度为 \(n\) 的序列,可以选择其中的一个三元组 \((i, j, k)\),按顺序移动 \(i -> j -> k -> i\),可以进行任意次该操作,判断是否能使该序列变成非递减序列。
思路:
从序列逆序对改变的性质去考虑。
三个元素顺序移动之后,
若三个元素都不相同,那么移动后序列的逆序对的数量改变偶数个,+2 或者 -2。而非递减的序列的逆序对的数量是 0,所以我们只需要计算当前序列的逆序对的数量是否为偶数个就可以了,偶数个的序列的逆序对经变化一定可以变为 0。
若有两个元素相同,那么序列的逆序对的数量可能变化奇数个,也可能变化偶数个,所以不管原序列的逆序对数量是奇数还是偶数,一定可以形成一个非递减的序列。
通过归并法计算逆序对:
#include <bits/stdc++.h> using namespace std; const int N = 5e5 + 10; int T, n, a[N], tmp[N], sum; void mergeSort(int l, int r){ if (l >= r) return; int mid = (l + r) >> 1, i = l, j = mid + 1, cnt = 0; mergeSort(l, mid); mergeSort(mid + 1, r); while (i <= mid || j <= r) if (j > r || (i <= mid && a[i] <= a[j])) tmp[cnt++] = a[i++]; else tmp[cnt++] = a[j++], sum += mid - i + 1; for (int k = 0; k < r - l + 1; k++) a[l + k] = tmp[k]; } void solve(){ bool f = false; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); sum = 0; mergeSort(1, n); if (sum % 2 == 0) cout << "YES\n"; else{ for (int i = 2; i <= n; i++) if (a[i] == a[i - 1]){ cout << "YES\n"; return; } cout << "NO\n"; } } int main(){ cin >> T; while (T--) solve(); return 0; }
树状数组计算逆序对
#include <bits/stdc++.h> using namespace std; #define LL long long const int N = 5e5 + 10; LL ans; int T, n, tree[N], p[N]; struct node{ int num, index; }nd[N]; bool cmp(node a, node b){ if (a.num == b.num) return a.index < b.index; return a.num < b.num; } int lowbit(int k){ return k & -k; } void update(int x, int k){ while (x <= n){ tree[x] += k; x += lowbit(x); } } int query(int x){ int t = 0; while (x != 0){ t += tree[x]; x -= lowbit(x); } return t; } void solve(){ scanf("%d", &n); ans = 0; for (int i = 1; i <= n; i++){ scanf("%d", &nd[i].num); nd[i].index = i; tree[i] = 0; //初始化,慎用 memset } sort(nd + 1, nd + n + 1, cmp); for (int i = 2; i <= n; i++) if (nd[i].num == nd[i - 1].num){ cout << "YES\n"; return; } for (int i = 1; i <= n; i++) p[nd[i].index] = i; for (int i = 1; i <= n; i++){ update(p[i], 1); ans += (i - query(p[i])); } if (ans % 2 == 0) cout << "YES\n"; else cout << "NO\n"; } int main(){ cin >> T; while (T--) solve(); return 0; }
这篇关于CF 1591D - Yet Another Sorting Problem的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升