P9101 [PA2020] Skierowany graf acykliczny

mayike · 2023-12-15 23:21:57 · 题解

题目传送门

一道思维题。

思路

由于每个点只能连两条出边，而不同路径数又是从前面累加的(这里规定编号从小到大，更方便，毕竟谁也不喜欢乱编号吧)，k \le 10^9。

我突发奇想可以用二进制来累加成 k，具体如图：

一个点有且至少一条，至多两条入边，即为路径数的累加。以此，对于节点 i 为奇数，i,i+1 的路径数皆为 2^{(i+1)/2-1}，那么，对于前 2 \times i 个数，可以让第 2 \times i + 1 个数至多累加成 2^i-1 条不同路径数，那么也就可以累加成 1 到 2^i-1 之间的所有数(知道 2^0 + 2^1 + 2^2 + \dots + 2^n 与 1 到 2^n 之间的关系的应该明白)。所以，即使当 k=10^9 时，i=31 也能使路径条数累加到 k，此时 \min(n)=62 \le 100 显然是满足的。并且连边的规律我们自然也懂了。

点个赞再走啊

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll k,sum[101],cnt,num,n,ab,a[101]; 
int main(){
//  freopen("s.in","r",stdin);
//  freopen("s.out","w",stdout);
    scanf("%lld",&k);
    if(k==1){
        cout<<2<<'\n'<<2<<' '<<-1<<'\n'<<-1<<' '<<-1;
        exit(0);
    }sum[1]=1;
    num=cnt=1;
    while(num*2-1<k){
        num*=2;
        sum[++cnt]=num;
    }ab=k,n=cnt*2+1;
    for(int i=cnt;i;i--)
        if(ab>=sum[i])ab-=sum[i],a[i*2]=1;
    cout<<n<<'\n';
    for(int i=1;i<=n;i++)
        if(i==n)
            cout<<-1<<' '<<-1;
        else if(i==n-2||i==n-1)
            cout<<i+1<<' '<<-1<<'\n';
        else
            if(i%2==0)
                if(!a[i])cout<<i+1<<' '<<-1<<'\n';
                else cout<<i+1<<' '<<n<<'\n';
            else cout<<i+1<<' '<<i+2<<'\n';
    return 0;
}