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

23 LCA模拟赛2T2 异或排列 题解

Fast XORting

题面

给定一个 \(2\) 的整数次幂 \(n\) 以及一个 \(0 \sim n - 1\) 的排列 \(a_1, a_2, \cdots a_n\)

在一次运算中,你可以进行以下两种操作之一:

  • 交换两个相邻元素
  • 选择任意整数 \(0 \le x \le n - 1\) ,将每个 \(a_i\) 都替换为 \(a_i \oplus x\)

求将该排列从小到大进行排序的最小运算次数。

\(1 \le n \le 2^{18}\)

题解

首先观察题目操作的性质,不难发现,第一个操作相当于在求逆序对数,第二个操作至多只会进行一次。

朴素的想法是枚举每个 \(x\) ,异或后跑一遍归并排序,时间复杂度 \(O(n^2 \log n)\)

我们要求逆序数实际上就是要比较两个数的大小关系。那么对于任意的两个数,它们的大小关系只会由从高到低第一个不同的二进制位决定,所以我们可以分开考虑每个二进制位。

对于每个二进制位,我们尝试异或后的逆序数少还是异或前的逆序数少,从而得到一个最优的 \(x\) 使得逆序数最少。

时间复杂度 \(O(n \log^2 n)\)

code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;namespace michaele {typedef long long ll;const int N = 262200;int n, m;int a[N], b[N], c[N];ll res;// 归并排序求逆序对数void work (int l, int r) {if (l == r) return;int mid = (l + r) >> 1;work (l, mid);work (mid + 1, r);{int i = l, j = mid + 1, k = l;while (i <= mid && j <= r) {if (b[j] < b[i]) {res += mid - i + 1;c[k ++ ] = b[j ++];} else {c[k ++ ] = b[i ++];}}while (i <= mid) c[k ++] = b[i ++];while (j <= r) c[k ++] = b[j ++];}for (int i = l; i <= r; i ++) {b[i] = c[i];}}void solve () {cin >> m;n = __lg(m);for (int i = 0; i < m; i ++) {cin >> a[i];}res = 0;memcpy (b, a, sizeof a);work (0, m - 1);ll ans = res;int x = 0;for (int i = 0; i < n; i ++) {memcpy (b, a, sizeof a);for (int j = 0; j < m; j ++) {b[j] ^= (1 << i);}res = 0;work (0, m - 1);if (res < ans) x ^= (1 << i);}memcpy (b, a, sizeof a);for (int j = 0; j < m; j ++) {b[j] ^= x;}res = 0;work (0, m - 1);ans = min (ans, res + 1);cout << ans << endl;}
}int main () {ios :: sync_with_stdio (0);cin.tie (0);cout.tie (0);michaele :: solve ();return 0;
}
http://www.hskmm.com/?act=detail&tid=27561

相关文章:

  • Bugkuctf的哥哥的秘密
  • 国庆做题记录(基础算法)
  • fp16训练神经网络时出现nan问题
  • 第十篇
  • 504 品酒大会!!!!!!
  • 整体理解pai0-具身智能-01 - jack
  • 【数据结构】可撤销并查集 - Slayer
  • 皮卡鱼源码导读
  • 高斯消元学习笔记
  • newDay07
  • 10月9日
  • 从开放重定向到XSS:漏洞升级实战
  • 余弦日记
  • 【题解】P11459 [USACO24DEC] Its Mooin Time P
  • 创建一个springboot项目,mybatis连接嵌入式数据库H2,实现增删改查功能
  • 基于众包的产品质量比较与推荐算法研究
  • 10/9
  • 2025.10.9
  • 线程池总结
  • 合并两个有序链表
  • 深入解析:一款相机是只有桶形畸变 和 枕形畸变的一种,还是两个都有?
  • 数据结构-链表
  • 重组抗体技术:从原理到应用,解锁高效可控的新一代抗体研发
  • P13690 [CEOI 2025] boardgames
  • CSS
  • 关于jinja2的ssti模版注入的学习+过滤
  • WPF Epplus export 10M+ items in excel with multiple sheets batch by batch
  • [EGOI 2023] Guessing Game
  • CF2152G Query Jungle
  • [ROI 2018] Addition without carry