P14145 荒谬

声明感谢同校大佬 zwm ，没有他的点拨就没有这篇题解

~~有够荒谬的，黄题就一个递归没想到，导致4个要打noip的人原地爆炸~~

题目描述

给定

n

，构造一张

n

个点的简单有向无环图，使得距离为

2

的点对的个数不少于

\dfrac{n(n-1)}2-n\left\lceil\log_2n\right\rceil

。

点对

(u,v)

之间的距离指

u

到

v

的最短路长度。若

u

无法到达

v

，则距离为

100^{100}

。

输入格式

一行一个正整数

n

。

输出格式

第一行一个整数

m(0\le m\le \frac{n(n-1)}{2})

，表示你构造的图的边数。

之后

m

行，每行两个数

u,v

，表示你的构造的图中的一条边。你需要保证你构造的图是一张简单有向无环图，即没有重边也没有环。

输入输出样例 #1

输入 #1

CPP

输出 #1

CPP

2
1 2
2 3

说明/提示

样例解释

样例中唯一距离为

2

的点对是

(1,3)

，容易证明不存在满足条件的点对个数比

1

大的方案。

数据范围

1\le n\le 2000

。

很明显里面有一个很哈人的东西:

\dfrac{n(n-1)}2-n\left\lceil\log_2n\right\rceil

这个很明显是一个很好的提示，提示了这个图的形状 ~~当然，我数学注意力不强~~

或我们可以自行举例构造

STEP 1

题目要求我们尽可能多的找距离为二的点对，这时候我们很容易想到菊花图可以出现很多距离为一的点对进一步想，把它对半分不就可以得到很多点对满足要求了吗？如图所示:

好丑

预计得分 : 20

STEP 2

其实不用交代码，不用仔细想就会发现我们的算法增长的速度有亿点慢，这要如何解决呢？

我们容易想到，再加几个类似的结构就好了!

so ……

对题目使用递归吧！(

运用递归我们就可以得到这么一个东西，其中红的框框住的点和红点连接，其中黄的框框住的点和黄点连接

特别注意，红黄的箭头的意思是与红黄点有边，并不是说边的方向是这么连的，方向和其他的方向相一致，具体方向和细节处理请读者自行思考

最后你就会发现，这个构图法和那个神秘的公式有千丝万缕的联系，大家可以计算一下！

~~并不是因为我没算出来~~

代码时间

CPP

#include<bits/stdc++.h>

using namespace std;

vector<pair<int,int>> G;

void solve(int l, int r){
	if(l >= r) return;
	int mid = l + r >> 1;
	for(int i = l; i < mid; ++i) G.push_back({i, mid});
	for(int i = mid + 1; i <= r; ++i) G.push_back({mid, i});
	solve(l, mid-1);
	solve(mid+1, r);
}

int main(){
	int n;
    cin >> n;
	solve(1, n);
	cout << G.size() << endl;
	for(auto e: G) printf("%d %d\n", e.first, e.second);
	return 0;
//这是那个同校大佬的代码，本蒟蒻马蜂有点丑陋
}

各位大佬喜欢记得点个赞！题解新手，有错请指出！

题解：P14145 荒谬

文章操作