题解：AT_arc207_b Balanced Neighbors 2

· · 题解

题意

构造一个 n 个点的简单连通无向图，使得每个顶点能在两步之内到达的顶点编号（不包含自己）之和均相等。

思路

本题充分考察了瞪眼法的解题方法。

首先通过跑一遍样例输出可以发现对于 n=12，点 1 可以到达除了 12 的所有点，点 2 可以到达除了 11 的所有点，点 3 可以到达除了 10 的所有点，以此类推。

于是我们猜测，对于 n 为偶数，我们构造的方案应该是能让点 i 能到达除了点 (n+1-i) 的所有点，这样可以保证每个点的编号和都为 \frac{n(n+1)}{2}-(n+1)。

如果你尝试从样例观察出更多性质（如观察出构造方法），那么恭喜你，样例确实有一定的构造方法，但是是有关 n=\frac{k(k+1)}{2} \pod{k\ge 3} 的特殊解法，而通过提交后 WA 了我们可以知道对于大于一定范围的偶数 n 应该是都有解的。我们需要考虑去构造通解。

首先我们需要求出有解的范围。通过朴素暴力（复杂度为 2^{\frac{n(n+1)}{2}}，可以跑到 n=7）或者手模可以发现对于 n<6 都是无解的，而对于 n=6 存在以下解：

对于 n=7 存在以下解：

其实通过这两个图已经可以观察出正解了。

先不考虑 n 为奇数的情况。可以发现在 n=6 中，点 1 和 6 可以看作中间隔了两层点，因此不能在两步以内到达。而 2 和 5，3 和 4 之间没有连边，因此点 i 最多只能通过两步到达本层的点或者另一边除了 (n+i-1) 的点。

如果你还没有发现，可以再手模一个 n=8 的情况：

发现了吧。同样的，点 1 和 8 之间隔了两层顶点，两层之间的点 2,3,4 和 5,6,7 之间没有 i 和 (n+1-i) 的连边。

因此，n 为偶数的构造方法即为：

取出点 1 和点 n，将点 1 与 2,3,\cdots,\frac{n}{2} 连边，将点 n 与 \frac{n}{2}+1,\frac{n}{2}+2,\cdots,n-1 连边，对于 2,3,\cdots,\frac{n}{2} 和 \frac{n}{2}+1,\frac{n}{2}+2,\cdots,n-1 之间将所有和不为 n+1 的点连边。

如果你现在就交的话，你会发现你还是挂了恰好一半的点。通过以上构造我们可以发现奇数应该也是有通解的。接下来考虑 n 为奇数的构造方法。

再来看这张 n=7 的图：

令 n'=n-1。可以发现，这种连边方式可以使得 7 能到达所有点，并且不会改变原来不可达的关系。因此 7 能到达的编号之和为 \frac{n(n+1)}{2}-(n'+1)（n'+1 为 7 自己的编号），而对于其他点，由于它们都能到达 7，所以它们不能到达的点仍然为 n'+1-i，即能到达的编号之和也为 \frac{n(n+1)}{2}-(n'+1)。

同样的，对于 n=9：

因此，n 为奇数的构造方法即为：

构造出 n'=n-1 的偶数情况下的图，并将 n 与 1 和 \frac{n'}{2}+1,\frac{n'}{2}+2,\cdots,n'-1 连边。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
vector<pair<int,int>> a;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(),cout.tie();
    cin>>n;
    if(n<6){
        cout<<-1;
        return 0;
    }
    if(n%2==1){
        a.push_back({n,1});
        for(int i=n/2+1;i<=n-2;i++)
            a.push_back({n,i});
        n--;
    }
    for(int i=2;i<=n/2;i++)
        a.push_back({1,i});
    for(int i=n/2+1;i<=n-1;i++)
        a.push_back({i,n});
    for(int i=2;i<=n/2;i++)
        for(int j=n/2+1;j<=n-1;j++)
            if(i+j!=n+1) a.push_back({i,j});
    cout<<a.size()<<endl;
    for(pair<int,int> v:a) cout<<v.first<<" "<<v.second<<endl;
    return 0;
}