专栏文章

题解：AT_arc207_b Balanced Neighbors 2

WWuMin4
AT_arc207_b题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minojw1w
此快照首次捕获于
2025/12/02 05:47
3 个月前
此快照最后确认于
2025/12/02 05:47
3 个月前
查看原文

题意

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

思路

本题充分考察了瞪眼法的解题方法。
首先通过跑一遍样例输出可以发现对于 n=12n=12，点 11 可以到达除了 1212 的所有点，点 22 可以到达除了 1111 的所有点，点 33 可以到达除了 1010 的所有点，以此类推。
于是我们猜测，对于 nn 为偶数，我们构造的方案应该是能让点 ii 能到达除了点 (n+1−i)(n+1-i) 的所有点，这样可以保证每个点的编号和都为 n(n+1)2−(n+1)\frac{n(n+1)}{2}-(n+1)。
如果你尝试从样例观察出更多性质（如观察出构造方法），那么恭喜你，样例确实有一定的构造方法，但是是有关 n=k(k+1)2(k≥3)n=\frac{k(k+1)}{2} \pod{k\ge 3} 的特殊解法，而通过提交后 WA 了我们可以知道对于大于一定范围的偶数 nn 应该是都有解的。我们需要考虑去构造通解。
首先我们需要求出有解的范围。通过朴素暴力（复杂度为 2n(n+1)22^{\frac{n(n+1)}{2}}，可以跑到 n=7n=7）或者手模可以发现对于 n<6n<6 都是无解的，而对于 n=6n=6 存在以下解：
对于 n=7n=7 存在以下解：
其实通过这两个图已经可以观察出正解了。
先不考虑 nn 为奇数的情况。可以发现在 n=6n=6 中，点 11 和 66 可以看作中间隔了两层点，因此不能在两步以内到达。而 22 和 55，33 和 44 之间没有连边，因此点 ii 最多只能通过两步到达本层的点或者另一边除了 (n+i−1)(n+i-1) 的点。
如果你还没有发现，可以再手模一个 n=8n=8 的情况：
发现了吧。同样的，点 11 和 88 之间隔了两层顶点，两层之间的点 2,3,42,3,4 和 5,6,75,6,7 之间没有 ii 和 (n+1−i)(n+1-i) 的连边。
因此，nn 为偶数的构造方法即为：
取出点 11 和点 nn，将点 11 与 2,3,⋯ ,n22,3,\cdots,\frac{n}{2} 连边，将点 nn 与 n2+1,n2+2,⋯ ,n−1\frac{n}{2}+1,\frac{n}{2}+2,\cdots,n-1 连边，对于 2,3,⋯ ,n22,3,\cdots,\frac{n}{2} 和 n2+1,n2+2,⋯ ,n−1\frac{n}{2}+1,\frac{n}{2}+2,\cdots,n-1 之间将所有和不为 n+1n+1 的点连边。
如果你现在就交的话，你会发现你还是挂了恰好一半的点。通过以上构造我们可以发现奇数应该也是有通解的。接下来考虑 nn 为奇数的构造方法。
再来看这张 n=7n=7 的图：
令 n′=n−1n'=n-1。可以发现，这种连边方式可以使得 77 能到达所有点，并且不会改变原来不可达的关系。因此 77 能到达的编号之和为 n(n+1)2−(n′+1)\frac{n(n+1)}{2}-(n'+1)（n′+1n'+1 为 77 自己的编号），而对于其他点，由于它们都能到达 77，所以它们不能到达的点仍然为 n′+1−in'+1-i，即能到达的编号之和也为 n(n+1)2−(n′+1)\frac{n(n+1)}{2}-(n'+1)。
同样的，对于 n=9n=9：
因此，nn 为奇数的构造方法即为：
构造出 n′=n−1n'=n-1 的偶数情况下的图，并将 nn 与 11 和 n′2+1,n′2+2,⋯ ,n′−1\frac{n'}{2}+1,\frac{n'}{2}+2,\cdots,n'-1 连边。

代码

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...