2019.8.3 [HZOI]NOIP模拟测试12 A. 斐波那契(fibonacci)

全场比赛题解：https://pan.baidu.com/s/1eSAMuXk

找规律

找两个节点的lca，需要能快速根据编号求出父亲的编号。

斐波那契数列：1、2、3、5、8、13、21...

第10对兔子的父节点：斐波那契数列中小于10的最大项为8，所以第10对兔子的父节点为10-8=2。

很容易理解：第5个月时，共有8对兔子（斐波那契第5项），到了第6个月时，共13对兔子。多出的5对兔子，一定是已经成熟的5对兔子（斐波那契第4项）生下的。所以对应下来：9号兔子是1号兔子生的、10号兔子是2号兔子生的...

可以先打表打出斐波那契数列，然后每次二分查找。

复杂度？打表发现斐波那契60项就已经到\(10^{12}\)了，所以树高最多60层，经计算发现能过。

Code：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int m;

ll table[100]={0ll,1ll,2ll,3ll,5ll,8ll,13ll,21ll,34ll,55ll,89ll,144ll,233ll,377ll,610ll,987ll,1597ll,2584ll,4181ll,6765ll,10946ll,17711ll,28657ll,46368ll,75025ll,121393ll,196418ll,317811ll,514229ll,832040ll,1346269ll,2178309ll,3524578ll,5702887ll,9227465ll,14930352ll,24157817ll,39088169ll,63245986ll,102334155ll,165580141ll,267914296ll,433494437ll,701408733ll,1134903170ll,1836311903ll,2971215073ll,4807526976ll,7778742049ll,12586269025ll,20365011074ll,32951280099ll,53316291173ll,86267571272ll,139583862445ll,225851433717ll,365435296162ll,591286729879ll,956722026041ll,1548008755920ll,2504730781961ll};

inline ll Find(ll x){

	if(x==1) return 0;

	int l=0,r=60,ans=0;

	while(l<=r){

		int mid=(l+r)>>1;

		if(table[mid]<x) ans=max(ans,mid),l=mid+1;

		else r=mid-1;

	}

	return table[ans];

}

int main(){

	scanf("%d",&m);

	for(ll i=1,a,b;i<=m;++i){

		scanf("%lld%lld",&a,&b);

		while(a!=b){

			if(a<b) swap(a,b);

			a-=Find(a);

		}

		printf("%lld\n",a);

	}

	return 0;

}

巴特西

2019.8.3 [HZOI]NOIP模拟测试12 A. 斐波那契(fibonacci)

2019.8.3 [HZOI]NOIP模拟测试12 A. 斐波那契(fibonacci)

Code：

最新文章

热门文章