题目链接：http://hihocoder.com/contest/icpcbeijing2018/problem/4
题意：青蛙可以从p跳到 p+1,p+2,现在青蛙要从0跳到200，你可以安传送门ai-aj 青蛙一到ai就会跳到aj ，可能形成死循环，每个传送门ai不同，
求安传送门后，使青蛙跳到200的方案数正好为m的安放方法
题解：
没做出来。。看的大家的题解，感觉太巧妙了
plana：
任何正整数都可以分解为若干不同斐波那契数之和
f[48]就已经大于1<<32 了，可以从从大到小减去斐波那契数，连得时候倒着连，比如从199-200=1,198-200=2，197-200=3……，然后1连197,3连198,5连197,结束的结点连自己结束6-6
前面隔一个连一个到后面，这样前面每一种方案为1，连到后面后对后面不造成影响。
如先连了1-195 ，又连了3-198，那相当于在198加了1方案，199也加了1方案，200加了2方案，又是一个重新开始的斐波那契，叠加在前一个连得上。
如图
planb：如果我们位于x，方案为m，m为偶数：连接x+1~x+3,x+2~x+3,这样到x+3 方案有2种，变为问题从x+3到200，方案为m/2，
m为奇数，连x+1~200,变为问题从x+2到200 方案为m-1 方案数
特判0,1情况
AC代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 int const maxn=210; 4 typedef long long ll; 5 long long f[maxn],m,tot,ans[maxn]; 6 void getfi(){ 7 f[200]=1;f[199]=1; 8 for(int i=198;i>=150;i--)f[i]=f[i+1]+f[i+2]; 9 } 10 void work(){ 11 if(m==0){ 12 printf("2\n1 1\n2 1\n");return ; 13 } 14 if(m==1){ 15 printf("2\n1 199\n2 2\n");return ; 16 } 17 if(m==2){printf("2\n1 2\n2 199\n");return ;} 18 for(ll i=150;i<=199;i++){ 19 if(m==0)break; 20 if(m-f[i]>=0){ 21 ans[++tot]=i; 22 m-=f[i]; 23 } 24 } 25 printf("%lld\n",tot+1); 26 for(int i=1;i<=tot;i++)printf("%d %lld\n",i*2-1,ans[i]); 27 printf("%lld %lld\n",tot*2,tot*2); 28 } 29 int main(){ 30 getfi(); 31 while(scanf("%lld",&m)!=EOF){ 32 tot=0; 33 work(); 34 } 35 return 0; 36 }
2018北京ICPC D. Frog and Portal 斐波那契数 构造
原文：https://www.cnblogs.com/conver/p/11291000.html