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

laoliu12345 · 2024-09-04 20:35:55 · 题解

P6342

解法说明

首先我们考虑一个点数为 n 的环会产生多少价值，首先共有 n \times (n-1) / 2 个，又由于是在环中，故对于每一个点对都可以找到两条不重合路径，所以环的价值就是上式。

而后我们考虑为了保持联通，相邻两个环间必须建一条边，但是由于左环到右环和右环到左环必须经过两次中间这条边，所以这条边不产生价值。

那么思路就很清晰了，每次找出小于等于 k 的最大 n \times (n-1) / 2 即可。

那就可以愉快的写代码了。

题目代码

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
const int N=1e4,M=1e6+10;
int n,m,k;
struct node{
    int l,r;
}e[M];
int idx;
int lb(int k)
{
    int l=0,r=N,mid,ans=0;
    while(l<=r) 
    {
        int mid=(l+r)>>1;
        if(k>=mid*(mid-1)/2) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>k;
    while(k)
    {
        n++,idx++;
        int t=lb(k);
        k-=t*(t-1)/2;
        e[idx].l=n,e[idx].r=n+t-1;
        n=n+t-1;
    }
    cout<<n<<" "<<n+idx-1<<endl;
    for(int i=1;i<=idx;i++)
    {
        for(int j=e[i].l;j<e[i].r;j++)
            cout<<j<<" "<<j+1<<endl;
        cout<<e[i].r<<" "<<e[i].l<<endl;
        if(i>1) cout<<e[i].l<<" "<<e[i-1].r<<endl;
    }
    return 0;
}