题解：CF288C Polo the Penguin and XOR operation

wyc0607 · 2025-08-27 16:27:59 · 题解

思路：

有点小暴力，从大到小循环每个数 i，求出他和 1 到 n 中的数的最大异或结果。再加上异或结果，把两个数打上标记就可以了。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int x[1000005];
main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=0; i<=n; i++) x[i]=-1;
    int ans=0;
    int lft=n+1;//剩余几个节点 
    for(int i=n; i>=0; i--) {
        if(x[i]!=-1) continue;
        if((n+1)%2==1&&lft==1){
            x[i]=i;
//          cout<<i<<' '<<x[i]<<'\n';
            break;
        }
        int sl=log2(i)+1;
        int j=i^(int)(pow(2,sl)-1);
        ans+=(i^j)*2;
        x[j]=i;
        x[i]=j;
//      cout<<i<<' '<<j<<'\n';
        lft-=2;
//      cout<<i<<' '<<lft<<'\n';
    }
    cout<<ans<<'\n';
    for(int i=0;i<=n;i++) cout<<x[i]<<' ';
}