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

Sunrise_up · 2026-05-09 10:42:02 · 题解

赛时想的 45 分，后面才想到正解，就差一点啊。

求点赞 qwq！

思路

以下所有数字的二进制位从第 0 位开始标号。

条件的式子有些难搞，于是考虑变换一下式子，将 x\oplus y>|x-y| 化简一下。

若假定 x\ge y，则：

\begin{align*} x\oplus y &> |x-y|\\ x+y-2(x\ \&\ y) &>x-y\\ 2y&>2(x\ \&\ y)\\ y&>x\ \&\ y \end{align*}

同理若 x<y 得 x>x\ \&\ y。

所以条件变为 \min(p_i,p_{i+1})>p_i\ \&\ p_{i+1}。

研究这个条件，发现满足这个条件需要相邻两数中较小的数二进制下某一位是 1 而较大数的这一位是 0。

所以当 n=2^k-1(k>1) 直接无解，因为 n 二进制下全是 1，在任何一个 <n 的数的旁边都不满足条件。

首先考虑构造 1,2,3,4,\dots，不满足条件。

考虑二进制后两位的排布规律，尝试每 4 个数为一组利用 01,10,11,00 的位差构造。

容易想到将奇偶数交替，即 2,1,4,3,6,5,\dots，它们的二进制后两位情况为 10,01,00,10,10,01,\dots，这样子相邻两数都满足条件。

同理可以想到 1,2,4,3,5,6,8,7,\dots 等构造。

我们使用将奇偶数交替的构造，发现这样放的话后面还有 n\bmod 4 个数留下来，需要考虑：

当 n\bmod 4=0 时，不管，已经放完。
当 n\bmod 4=1 时，留下一个 n，直接放在序列末端即可，前一个数是 n-2，后两位为 11，n 的后两位为 01，n 较大，它们的第 1 位满足。
当 n\bmod 4=2 时，留下 n-1 和 n，随便你怎么放，前面一个数是 n-3，证明同理。
当 n\bmod 4=3 时，留下三个数 n-2,n-1 和 n，不好搞，可以在后面随便放 n-2 和 n-1，但是 n 要找另外的地方放，直接枚举。或者不枚举，我们可以找到 n 二进制下最小的为 0 的位数，假设是第 m 位，那么直接插在 2^m+2 后面即可，即 2^m+2 和 2^m+1 之间。此时 2^m+2 一定存在，下面给出证明。

:::info[证明：当 n\bmod 4=3 时 2^m+2 一定存在]

$$2^m \ge 2^2 = 4$$ 立刻得到： $$2^m \ge 4 \implies 2^m + 2 \ge 6$$ --- 假设结论不成立，即： $$2^m + 2 > n$$ 由 $m$ 的定义：$m$ 是 $n$ 最低的 $0$ 位，**所有低于 $m$ 的二进制位全为 $1$**。低于 $m$ 位全 $1$ 的数值为：$2^m - 1$。因此 $n$ 一定可以写成： $$n = t\cdot 2^{m+1} + (2^m - 1),\quad t\ge 0$$ 1. 若 $t\ge 1$： $n \ge 2^{m+1} + 2^m-1 = 3\cdot 2^m -1

显然 3\cdot 2^m-1 > 2^m+2，与假设 2^m+2>n 矛盾。

若 t=0：则 n = 2^m - 1。这是二进制全 1 的形式，属于 n=2^k-1 无解情况，早已提前输出 -1，不会进入构造环节。

综上，假设不成立。故必有：

\boldsymbol{2^m + 2 \le n}

当 n\bmod 4=3 且题目有解时：

6\le 2^m+2 \le n

所以 2^m+2 一定落在 1\sim n 中，必然存在合法插入位置。

:::

代码

时间复杂度 O(n)。

代码中 (~n)&-(~n) 其实就是用 lowbit 的技巧来求最低位的 0 的位置。

#include<bits/stdc++.h>
using namespace std;
int T,n;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        if(!(n&(n+1))&&n>=3){
            cout<<"-1\n";
            continue;
        }
        for(int i=1;i<=n-(n&1);i+=2){
            if(n%4==3&&((~n)&-(~n))==i-1)cout<<i+1<<' '<<n<<' '<<i<<' ';
            else cout<<i+1<<' '<<i<<' ';
        }
        if(n%4==1)cout<<n<<' ';
        cout<<'\n';
    }
}