题解：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} 连边。

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';
}