自动搬运

查看原文

来自洛谷，原作者为

	mayike Let's go back to the place

搬运于2025-08-24 22:45:22，当前版本为作者最后更新于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;
}