题解：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：

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