题解：AT_arc207_b [ARC207B] Balanced Neighbors 2

你好吗？这题需要你用忍者的态度来观察呦。

首先你需要用手写的从前，来跨时代的发现

< 6

的情况不可能存在。

接着你看甜甜的样例，当

n\le 12

，

1

只不能到

12

，

2

只不能到

11

，

3

只不能到

10

，ok 以此类推。

然后我们猜测对于

n

是偶数的时候肯定有答案，答案应该是对于每个

i

，都有

i\to n+1-i

（但是它给我们玩了个黑色幽默，这只是特殊解）。

怎么了，这个样例明明就只有一点点，然后你从样例里啥也看不出了。。。（傻笑）

通过刚刚的猜测，我们可以注意到偶数当我们构造一个循环，对于

i\to n-i+1

之间的有着开不了口的距离

3

，其他点之间的距离为

1

或

2

。

因此，

n

为偶数的构造方法即为：

对于点

i\in[1,\frac{n}{2}],j\in[\frac{n}{2}+1,n]

，将点

i

与

j

连边，当

i+j\ne n+1

我们将点

i\to j

。

如果你现在就交的话，你会发现说好的幸福呢？对不起，它给了让你安静的 Wa，你还是挂了恰好一半的点。

胡扯，我们追求完美主义，给我一首歌的时间，你就会想起其实还是有奇数解的，构造出

n'=n-1

的偶数情况下的图，并将

n

与

1\sim \frac{n}{2}

连边。

CPP

cin>>n;
if(n<6) cout<<"-1",exit(0);
int t=n>>1;
cout<<t*(t-1)+(n&1)*t<<'\n';
rep(i,1,t){
    rep(j,t+1,t+t){
        if(i+j!=t+t+1) cout<<i<<' '<<j<<'\n';
    }
    if(n&1) cout<<i<<' '<<n<<'\n';
}

题解：AT_arc207_b [ARC207B] Balanced Neighbors 2

文章操作

相关推荐

评论

题解：AT_arc207_b [ARC207B] Balanced Neighbors 2