题解 AT5140 【[AGC035C] Skolem XOR Tree】

FjswYuzu · 2021-01-13 21:22:00 · 题解

下面的 x' 皆表示 x 的另外一个结点。

首先考虑无解情况。显然，当 \operatorname{lowbit}(n)=n 的时候无解。

因为这样的话会存在 n 与 n'，除了这两个数以外找不到其他的数的异或和为 n。因此无法匹配。

考虑其他的情况。分奇数和偶数考虑。有一个比较好用的性质：

因此，如果我们假设 1 节点为根，就可以发现，将所有的数对 (x,x+1)（其中 x 为偶数并且 x+1 \leq n）匹配到一起就会比较好处理。我们可以找到路径 x \to x+1 \to 1 \to x',x+1 \to 1 \to x' \to (x+1)' 满足条件。

现在还有两个遗留的问题没有处理：

• 作为根的 1 没有匹配，如何添加 1'？

假设 1 为根，随便找一个叶子结点接上 1'，找到路径 1 \to x \to (x \operatorname{xor} 1) \to 1'。

• 如果 n 是偶数，那么 n,n' 就会遗留，如何处理？

考虑还是在根上处理。因为无解情况排除以后可以满足 n 在转化成二进制之后有两个 1，于是找到一条路径 n \to \operatorname{lowbit}(n) \to 1 \to (n - \operatorname{lowbit}(n) + 1)' \to n' 满足条件。

至此，我们在修修补补中完成了构造方法。

#include<cstdio>
using namespace std;
int lowbit(int x){return x&(-x);}
int main(){
    int n;
    scanf("%d",&n);
    if(lowbit(n)==n)    return puts("No")&0;
    puts("Yes");
    for(int i=2;i<=n-1;i+=2)
    {
        printf("1 %d\n",i);
        printf("1 %d\n",i+n+1);
        printf("%d %d\n",i,i+1);
        printf("%d %d\n",i+n,i+n+1);
    }
    printf("%d 3\n",n+1);
    if(n%2==0)
    {
        printf("%d %d\n",n+lowbit(n)+1,n);
        printf("%d %d\n",n+n,n-lowbit(n));
    }
    return 0;
}