[Paken Camp 2023 Day 1] + and Xor 题解

FFTotoro · 2024-03-29 17:09:50 · 题解

题意简述

题目来源：Paken Camp 2023 Day 1: SpeedRun

构造一个长度为 N 的排列 p，最大化 \mathrm{xor}_{i=1}^N(p_i+i)。

解法

令 X=\mathrm{xor}_{i=1}^N(p_i+i)。

首先观察到对于任何一个序列，\sum_{i=1}^Na_i\equiv\mathrm{xor}_{i=1}^Na_i\pmod 2，因为异或就是二进制下的不进位加法，对最后一位没有影响。所以 \mathrm{xor}_{i=1}^N(p_i+i)\equiv\sum_{i=1}^N(p_i+i)\equiv\left(\sum_{i=1}^Np_i\right)+\left(\sum_{i=1}^Ni\right)\equiv 2\sum_{i=1}^Ni\equiv 0\pmod 2，即 X 只能为偶数。

那么考虑能不能把 X 除了最后一位的其他位都填上 1（这里的位指二进制下的位）。有一个比较简单的想法，把位置 i\in\{x|x=2^k(k\ge 0),x\le N\} 的 p_i\leftarrow i，这样能暂时把 X 除了最后一位的所有位都填上 1。对于其他位置考虑如何不对 X 造成影响，使用对消：观察到如果使 p_i\leftarrow j，p_j\leftarrow i，有 p_i+j=p_j+i，又 a\ \mathrm{xor}\ a=0，所以把剩下的位置两两配对即可。如果剩下的 i 有奇数个，令 p_3\leftarrow 3，p_5\leftarrow 5，p_6\leftarrow 6（6\ \mathrm{xor}\ 10\ \mathrm{xor}\ 12=0），剩下的位置再配对即可。

注意这种做法在 n=3,4 时会出错（因为在两两配对的环节没法考虑 3,5,6）。特判即可。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  vector<int> p(n+1),x;
  if(n==3)cout<<"2 1 3\n",exit(0);
  if(n==4)cout<<"2 1 3 4\n",exit(0);
  for(int i=1;i<=n;i++)
    if(__builtin_popcount(i)==1)p[i]=i;
    else x.emplace_back(i);
  if(x.size()&1){
    p[3]=3,p[5]=5,p[6]=6;
    for(int i=3;i<x.size();i+=2)
      p[x[i]]=x[i+1],p[x[i+1]]=x[i];
  }
  else{
    for(int i=0;i<x.size();i+=2)
      p[x[i]]=x[i+1],p[x[i+1]]=x[i];
  }
  for(int i=1;i<=n;i++)
    cout<<p[i]<<' ';
  cout<<endl;
  return 0;
}