P16414 【MX-X28-T3】「FAOI-R12」寄清梦

Genius_Star · 2026-11-12 14:31:02 · 题解

宝宝题，场切了。

思路：

首先因为 x \oplus y \ge |x - y|，所以要满足 x \oplus y > |x - y| 只需要满足 x \oplus y \ne |x - y| 即可，而这个显然可以刻画成二进制下 x, y 分别不是另外一个的子集。

于是显然 n = 2^k - 1 时无解，它和任何元素挨着都不合法；否则找到最大的 k 满足 2^k \le n，然后根据 n 的奇偶性构造：

• 当 n 为偶数时，构造 2^k - 1, 2^k, 2, 1, 4, 3, \cdots, 2^k - 2, 2^k - 3, 2^k + 2, 2^k + 1, 2^k + 4, 2^k + 3, \cdots, n，显然是正确的，依据是 2i 与 2i - 1 与 2i + 2 一定不可能是包含包含，这是显然的。

• 当 n 为奇数时，构造 n, 2^k - 1, 2^k, 2, 1, 4, 3, \cdots, 2^k - 2, 2^k - 3, 2^k + 2, 2^k + 1, 2^k + 4, 2^k + 3, \cdots, n - 1 即可。

时间复杂度为 O(n)。

完整代码：

#include<bits/stdc++.h>
#define fi first

#define se second

#define lowbit(x) ((x) & (-(x)))

using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
int T, n;
int p[N];
bool chk(int n,int *p){
    for(int i=1;i<n;++i){
        if(!((p[i]^p[i+1])>abs(p[i]-p[i+1]))){
            // cerr << i << ' ' << p[i] << ' ' << p[i + 1] << '\n';
            return false;
        }
    }
    return true;
}
inline void solve(){
    n = read();
    // cerr << n << '\n';
    if(n == 1){
        puts("1");
        return ;
    }
    int k = 1;
    while((k << 1) <= n)
      k <<= 1;
    if((k << 1) - 1 == n){
        puts("-1");
        return ;
    }
    p[1] = k - 1, p[2] = k;
    for(int i = 1; i <= ((k - 2) >> 1); ++i){
        p[2 * i + 1] = 2 * i;
        p[2 * i + 2] = 2 * i - 1;
    }
    for(int i = k + 2; i <= n; i += 2){
        p[i] = k + (i - k) - 1;
        p[i - 1] = k + (i - k);
    }
    if(n & 1){
        for(int i = n; i >= 2; --i)
          p[i] = p[i - 1];
        p[1] = n;
    }
    for(int i = 1; i <= n; ++i){
        write(p[i]);
        putchar(' ');
    } 
    putchar('\n');
    assert(chk(n, p));
}
int main(){
    T = read();
    while(T--)
      solve();
    return 0;
}