P6342 [CCO2017] Vera 与道路建设 题解

题目大意

对于一个图 w 一共有 v 个点点的编号为 1 , 2 , ... , v ，对于点 a 与点 b 如果满足 $ a \to b $ 且 $ b \to a $ 使得每一条道路都只走过一次，那么我们称 $ a,b $ 为完美点对，当一个联通图只有 $ k $ 个完美点对时，称这个联通图为美丽公路网，要求求出一个美丽公路网。

思路

首先我们画一个有 $ n $ 个点的圆，假设 $ n = 4 $，那么我们可以得到此图：

在此图中我们可以得知：

对 $ 1 $ 来说他跟 $ 4 - 1 $ 个有没有被统计点有完美点对，对 $ 2 $ 来说他跟 $ 4 - 2 $ 个有没有被统计点有完美点对，对于 $ 3 $ 来说他跟 $ 4 - 3 $ 个点有没有被统计过的被统计点有完美点对，对于 $ 4 $ 来说跟他有关的完美点对已经统计完了，二完美点对的数量为 $ 6 $，根据统计的过程我们得知一个圆的完美点对为 $ \frac{(n - 1) \times n}{2} $ 这个弄懂了相当于弄懂了代码的 $ 80% $ 了。

接下来我们只需要写一个二分函数 check 来计算，我们将 $ l \gets 2,r \gets \sqrt{n} + 1 $ 一直二分下去找到圆最多的点数找到了之后，写一个函数标记一下就行了。二分一次就把 $ k - (l-1) \times (l-2) $ 直至 $ k $ 为零。

执行一次的时间复杂度为 $ \Omicron(\sqrt{n}) $ 所以最坏的时间复杂度为 $ \Omicron(n \times \sqrt{n}) $ 这个时间复杂度对于这道题来说完全够 AC 了。

Code：

#include <algorithm>
#include <iostream>
#include <math.h>
#include <string.h>
#include <queue>
#include <set>
#include <stdio.h>
#define ll long long
#define prt printf
#define sc(ppt) scanf("%d" , &ppt)
using namespace std;

int k , cnt = 0; 
set<pair<int , int > > ans;

int check(int n){
	int l = 2 , r = (int)sqrt(n * 2) + 1; // 圆至少有两个点 ， 至于后面那个 +1 是为了避免卡二分循环  
	while(l <= r){
		int mid = (l + r) >> 1;
		if(mid * (mid - 1) <= n * 2) l = mid + 1;
		else r = mid - 1;
	}
	return l - 1;
}

void Lable(int num){
	for(int i=cnt+1 ; i<cnt+num ; i++) ans.insert(pair<int , int >(i , i + 1)); // 造圆  
	ans.insert(pair<int , int >(cnt + num , cnt + 1)) ; // 连接两个圆
	if(cnt) ans.insert(pair<int , int >(1 , cnt + 1)) ; // 保证连通性避免偶然错误 
}

signed main(){
	sc(k) ;
	while(k){
		int now = check(k) ; Lable(now) ; cnt += now; // now 为这个圆，点的数量 
		k -= (now * (now - 1) / 2); 
	}
	prt("%d %d\n" , cnt , (int)ans.size());
	for(auto v : ans){
		prt("%d %d\n" , v.first , v.second);
	}
	return 0;
}
// 对于我这种小蒟蒻一次 AC 哈哈哈哈哈哈，太高兴了