AtCoder

Luogu

分析

可以发现 $(2i)\oplus (2i+1)=1$,因此可以想到大致的构造方法:连 $(1,2i)$、$(1,2i+1)$、$(2i+1+n,2i)$、$(2i+n,2i+1)$。这样子就满足了 $2i$ 和 $2i+1$。

然而有一些问题。一个问题是 $1$ 如何处理。可以仿照样例,使 $2$ 和 $3$ 不按上面的方式连边,而是连 $(1,2)$、$(2,3)$、$(3,n+1)$、$(n+1,n+2)$、$(n+2,n+3)$。这样子解决了 $1$ 的问题且其它数仍然满足。

还有一个问题是 $n$ 为偶数时没有一个 $n+1$ 与它匹配。可以证明,如果 $n$ 不为 $2$ 的幂,则一定存在 $(x,y)$ 使得 $x<n,y<n$ 且 $x\oplus y\oplus 1=n$。我们只需要找到一组 $x,y$,然后连 $(n,x)$ 和 $(2n,y)$ 即可。需要注意的因为我们对 $1,2,3$ 特殊操作了,所以这里的 $x$ 和 $y$ 不能为 $3$。

当 $n$ 为 $2$ 的幂时最高位显然无法消掉,因此无解。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int main() {
    int n=read();
    if (__builtin_popcount(n)==1) { puts("No"); return 0; }
    puts("Yes");
    printf("1 2\n2 3\n3 %d\n%d %d\n%d %d\n",1+n,1+n,2+n,2+n,3+n);
    for (int i=4;i+1<=n;i+=2)
        printf("1 %d\n1 %d\n%d %d\n%d %d\n",i,i+1,i,i+1+n,i+1,i+n);
    if ((n&1)==0) {
        for (int i=2;i<n;++i) {
            if (i==3) continue;
            int j=n^i^1;
            if (j!=3&&j<n) { printf("%d %d\n%d %d\n",i,n,j,n+n); break; }
        }
    }
    return 0;
}
最后修改:2020 年 04 月 16 日 09 : 55 PM