CF1416C XOR Inverse 题解

_ldyex_ · 2023-09-27 16:44:06 · 题解

题目

戳这里

解决方法

这道题有异或和逆序对，我们一个一个地解决。

逆序对

逆序对要用分治的方法，和归并排序很像（解析在模板中），看模板：

#include<bits/stdc++.h>

using namespace std;

const int maxn = 3e5 + 1;

int n, q[maxn], tmp[maxn];
long long res;       

void qsort(int q[], int l, int r){
  if(r <= l) return ;
  int k = 0, mid = (l + r) >> 1, i = l, j = mid + 1;
  qsort(q, l, mid), qsort(q, mid + 1, r);        //分
  while(i <= mid && j <= r){                        
    if(q[i] <= q[j]){                    //治
      tmp[++k] = q[i++];
    }
    else{
      tmp[++k] = q[j++];
      res += mid - i + 1;                //如果这两个数为逆序对，
    }                                    //则其q[i]至q[mid]都会与其组成逆序对，
  }                                      //共有mid - i + 1个
  while(i <= mid) tmp[++k] = q[i++];     //将未处理的数加入数组
  while(j <= r) tmp[++k] = q[j++];
  for(int i = l; i <= r; i++){
    q[i] = tmp[i - l + 1];
  }
}

异或

异或的解决方法很简单，因为它是逐位异或，所以只要枚举 30 次，看看如果将第 i 位与 1 异或后能使结果变得更优，便将其加入答案。

注意事项：

如果数组中的数以降序排列，则逆序对数量会爆 int，要开 long long!

Code

#include<bits/stdc++.h>

using namespace std;

const int maxn = 3e5 + 1;

int n, a[maxn], q[maxn], tmp[maxn], ans;
long long res, cnt = LLONG_MAX; //不开longlong见祖宗

void qsort(int q[], int l, int r){
  if(r <= l) return ;
  int k = 0, mid = (l + r) >> 1, i = l, j = mid + 1;
  qsort(q, l, mid), qsort(q, mid + 1, r);
  while(i <= mid && j <= r){
    if(q[i] <= q[j]){
      tmp[++k] = q[i++];
    }
    else{
      tmp[++k] = q[j++];
      res += mid - i + 1;
    }
  }
  while(i <= mid) tmp[++k] = q[i++];
  while(j <= r) tmp[++k] = q[j++];
  for(int i = l; i <= r; i++){
    q[i] = tmp[i - l + 1];
  }
}

long long sum(int q[], int x){
  res = 0;
  qsort(q, 1, x);
  return res;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    q[i] = a[i];
  }
  cnt = sum(q, n);
  for(int i = 0; i <= 30; i++){  //枚举每一位，并将其与1异或
    int x = (1 << i);           
    for(int j = 1; j <= n; j++){
      q[j] = a[j] ^ x;
    }
    if(sum(q, n) < cnt){
      ans += x;    
    }
  }
  for(int j = 1; j <= n; j++){
    q[j] = a[j] ^ ans;
  }
  cout << sum(q, n) << ' ' << ans;
  return 0;
}