[CCO2017] Vera 与道路建设 题解

· · 题解

提供一个代码短小、便于实现的做法。

看到数据范围点数的限制不难推出点数是 O(\sqrt{k}) 量级的，因为一个大小为 n 的环上完美点对数为 \dfrac{n(n-1)}{2}，于是考虑构造环。

具体地，不断构造当前可构造的最大的环，不妨设环大小为 x，去除已经构造的环的贡献的 k 为 k'，有 \dfrac{x(x-1)}{2}\le k，解得 x\le\dfrac{1+\sqrt{8k+1}}{2}，即 x_{\max}=\left\lfloor\dfrac{1+\sqrt{8k+1}}{2}\right\rfloor。

但是有个注意点：题目要求构造出的图必须连通，于是在相邻两个环之间连边即可。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int k,c=0; cin>>k;
  if(k){
    vector<pair<int,int> > e; // 存边
    while(k){
      int x=(sqrt(k<<3|1)+1)/2;
      for(int i=0;i<x;i++)
        e.emplace_back(c+i,c+(i+1)%x);
      if(c)e.emplace_back(c-1,c);
      c+=x,k-=x*(x-1)>>1; // 更新点数和 k
    } // 不断构造
    cout<<c<<' '<<e.size()<<endl;
    for(auto [u,v]:e)cout<<u+1<<' '<<v+1<<'\n';
  }
  else cout<<"2 1\n1 2\n";
  return 0;
}