[AGC035C] Skolem XOR Tree

zztqwq · 2023-01-29 23:48:41 · 题解

想不到高妙构造，写一个十分常规的做法，适合我这种无脑选手

首先一个观察就是当 n=2^k 的时候是无解的，猜想只有这种情况无解。

建一个虚点 0。样例给出了 n=3 的构造，我们加上 0，那么事实上我们就得到了 4i,4i+1,4i+2,4i+3 的一组构造。

对于 n\bmod 4=1/2/3，可以分别构造出 n=5/6/3 的解，然后往上四个四个跳。具体构造详见代码。

对于 n\bmod 4=0，我们可以把所有 4 的倍数都拎出来，然后往下递归。

不难发现所有不是 2^k 的 n，都能构造出解。

const int N=2e5+10,M=4e5+10;
int head[N],ver[M],nxt[M],tot=0;
void Add(int x,int y)
{
    ver[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
int cnt=0;
void add(int x,int y)
{
    // printf("add(%d, %d)\n",x,y);
    Add(x,y),Add(y,x);
    cnt++;
}
int nn;
void sol(int mul,int n)
{
    // printf("mul=%d, n=%d\n",mul,n);
    if(n%4==3)
    {
        for(int i=0;i<=n;i+=4)
        {
            int a=i,b=i+1,c=i+2,d=i+3;
            if(d>n)break;
            a*=mul,b*=mul,c*=mul,d*=mul;
            if(a)add(a,b);
            add(b,c),add(c,d);
            if(a)add(d,a+nn),add(a+nn,b+nn);
            else add(d,b+nn);
            add(b+nn,c+nn),add(c+nn,d+nn);
            if(d/mul+4<=n)add(d,d+4*mul);
        }
    }
    else if(n%4==1)
    {
        for(int i=0;i<=n;i+=4)
        {
            int a=i,b=i+1,c=i+2,d=i+3;
            if(d>n)break;
            a*=mul,b*=mul,c*=mul,d*=mul;
            if(a)add(a,b);
            add(b,c),add(c,d);
            if(a)add(d,a+nn),add(a+nn,b+nn);
            else add(d,b+nn);
            add(b+nn,c+nn),add(c+nn,d+nn);
            if(d/mul+4<=n)add(d,d+4*mul);
        }
        int a=(n-1)*mul,b=n*mul;
        add(mul,a),add(a,b);
        add(mul,b+nn),add(b+nn,a+nn);
    }
    else if(n%4==2)
    {
        for(int i=0;i<=n;i+=4)
        {
            int a=i,b=i+1,c=i+2,d=i+3;
            if(d>n)break;
            a*=mul,b*=mul,c*=mul,d*=mul;
            if(a)add(a,b);
            add(b,c),add(c,d);
            if(a)add(d,a+nn),add(a+nn,b+nn);
            else add(d,b+nn);
            add(b+nn,c+nn),add(c+nn,d+nn);
            if(d/mul+4<=n)add(d,d+4*mul);
        }
        int a=(n-2)*mul,b=(n-1)*mul,c=n*mul;
        add(mul,a),add(a,b);
        add(mul,b+nn),add(b+nn,a+nn);
        add(2*mul,c),add(b+nn,c+nn);
    }
    else if(n%4==0)
    {
        for(int i=0;i<=n;i+=4)
        {
            int a=i,b=i+1,c=i+2,d=i+3;
            if(d>n)break;
            a*=mul,b*=mul,c*=mul,d*=mul;
            // if(a)add(a,b);
            add(b,c),add(c,d);
            if(a)add(d,a+nn),add(a+nn,b+nn);
            else add(d,b+nn);
            add(b+nn,c+nn),add(c+nn,d+nn);
            if(!a&&d+4<=n)add(d,d+4*mul);
        }
        sol(mul*4,n/4);
    }
}
void dfs(int x,int fa)
{
    // return;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];if(y==fa)continue;
        printf("%d %d\n",x,y);dfs(y,x);
    }
}
int main()
{
    nn=read();
    if((nn&(-nn))==nn){puts("No");return 0;}
    // assert(nn%4!=0);
    puts("Yes");
    // printf("%d\n",nn);
    sol(1,nn),dfs(1,-1);
    // printf("cnt=%d\n",cnt);
}
//zzt qwq