CF909F 题解
zyh_helen
·
·
题解
考虑 p 的构造。
若 n 为奇数，那么二进制表示下末位为 1 的数的个数将会比末位为 0 的多一个，那么将会有两个末位为 1 的匹配在一起，显然无解。
为了让 {p_i}\&{i}=0，我们不能使 p_i 的二进制表示与 i 的有交集；贪心的去考虑，肯定某个数的二进制表示中 0 的个数越多这个数就越好对付，所以 p_i 的二进制表示与 i 的并集应该尽可能大。
我们倒序考虑（先对付不好对付的数），直接令 p_i 为 i 的补集，这样就符合我们的贪心，但是如果 p_i>n 或者这个 p_i 已经出现过，我们就不得不退一步，将 p_i 当前最高位改为 0。
若 $n=2^k$，那么 $n$ 这个数必然无人匹配，不可能构造出来，无解。
若 $n\le5$，手推就能发现一定无解。
由于 $n\ne2^k$，所以在二进制下，第 $j(j>1)$ 位必然至少有两个连续的该位为 1 的数。
接着我们手推出 $i\le7$ 的情况；$i>8$ 时，枚举 $j$ 让二进制下最高位是第 $j$ 位的所有数（显然是连续的）全部加一，再把最大的数改为最高位是第 $j$ 位的所有数中最小的（相当于整体向右平移一位）即可。
---
```cpp
#include<bits/stdc++.h>
#define int long long
//#define double long double
#define y1 yyyyyyyyyyyyyyyy1
using namespace std;
const int N = 1e6 + 10, M = 7001, inf = 2e9, mod = 1e9 + 7;
mt19937 rnd(time(0) ^ clock());
int random(int l, int r){
return rnd() % (r - l + 1) + l;
}
//const double eps = 1e-12, pi = 3.1415926;
/*
_ _ _
____ _| |_ | |_ ___| |___ _ _
|_ / || | ' \ | ' \/ -_) / -_) ' \
/__|\_, |_||_|_|_||_\___|_\___|_||_|
|__/ |___|
*/
//int head[N], tot;
//struct edge{
// int t, f;
// int d;
// int next;
//}e[N << 1];
//void edge_add(int u, int v, int w){
// e[++tot].next = head[u];
// e[tot].t = v;
// e[tot].d = w;
// e[tot].f = u;
// head[u] = tot;
//}
//int qmr(int x, int a){
// x %= mod;
// int ret = 1, p = x;
// while(a){
// if(a & 1)ret = ret * p % mod;
// p = p * p % mod;
// a >>= 1;
// }
// return ret;
//}
int n, vis[N], a[N];
signed main(){
cin >> n;
if(n & 1)cout << "NO" << endl;
else {
cout << "YES" << endl;
int x = 1 << (int)log2(n), y = x * 2 - 1, cnt = 0;
for(int i = n;i;i--){
int lsj = i ^ y;
for(int j = x;lsj > n || vis[lsj];j >>= 1)lsj -= j;
vis[lsj] = 1;
a[++cnt] = lsj;
}
for(int i = n;i;i--)printf("%lld ", a[i]);
cout << endl;
}
if(n <= 5 || (1 << (int)(log2(n))) == n)cout << "NO" << endl;
else {
cout << "YES" << endl;
if(n == 6){
cout << "3 6 2 5 1 4" << endl;
return 0;
}
cout << "3 6 2 5 7 4 1 ";
for(int i = 8;i <= n;i += i){
int x = min(i + i - 1, n);
for(int j = i + 1;j <= x;j++)printf("%lld ", j);
printf("%lld ", i);
}
}
return 0;
}