题解：P14145 荒谬

题意：

构造一个图，使距离为 2 的点对尽量多，不少于

\frac{n(n - 1)}{2} - n \lceil{\log_2 n}\rceil

。

思路：

我们尽量多的构造距离为 2 的点对，则当有一个点为中转点，中转点的入度和出度相近（不等式和定积最大）时，符合要求的点对数量最多，如图，5 为中转点，易证当仅考虑仅进行一次“二分”图中情况即为最优解。

然而我们会发现当

n

小时上图情况合适，但当

n

大时，

\left\lceil\log_2n\right\rceil

相对较小，无法满足题目要求，那么我们可以在原图的基础上对已经分为一组的再次二分，考虑用递归实现，如图。

我们在实现时通过递归左右边界来分情况，特判

n<3

时返回零。

Code：

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7+5,mod=376544743;
inline void read(int &a){
	char ch;int f=1,k=0;ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
	a=k*f;
}
struct edge{
	int u,v;
}e[N];
int n,m,cnt;
void dfs(int st,int end){
	if(end-st<2) return ;
	int tmp=st+end>>1;
	for(int i=st;i<tmp;i++) e[++cnt].u=i,e[cnt].v=tmp;
	for(int i=tmp+1;i<=end;i++) e[++cnt].u=tmp,e[cnt].v=i;
	dfs(st,tmp-1);dfs(tmp+1,end);
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	read(n);
	if(n<3) cout<<0;
	else{
		dfs(1,n);
		cout<<cnt<<"\n";
		for(int i=1;i<=cnt;i++){
			cout<<e[i].u<<" "<<e[i].v<<"\n";
		}
	}
	return 0;
}

文章操作

题意：

思路：

Code：

相关推荐

评论

题解：P14145 荒谬