【題目描述】

奧丁殺死的巨人伊米爾后，從伊米爾的尸體上生長出來一株巨大的梣樹，它是整個(gè)宇宙的核心，被稱為世界之樹，這個(gè)巨木的枝干構(gòu)成了整個(gè)世界，它被神秘的奧術(shù)力量所守護(hù)。

奧丁發(fā)現(xiàn)，世界樹的每個(gè)節(jié)點(diǎn)至多有兩棵子樹，其蘊(yùn)含的奧術(shù)力量是子樹奧術(shù)力量的最大值+1，如果一個(gè)節(jié)點(diǎn)沒有子樹，其奧術(shù)力量為1，這些節(jié)點(diǎn)被稱為“源”。

世界樹在悠長的歲月里形成了奇妙的魔法平衡，具體來說，它的左子樹與右子樹的奧術(shù)力量的差的絕對值不會超過1。若一個(gè)節(jié)點(diǎn)只有一棵子樹（不妨設(shè)為左子樹），則右子樹的奧術(shù)力量視為0。

現(xiàn)在奧丁想知道，在n個(gè)節(jié)點(diǎn)的世界樹中，最高和最低的兩個(gè)“源”的深度差最大是多少？

【輸入格式】

第一行一個(gè)整數(shù)T，表示數(shù)據(jù)組數(shù)。

以下T行，每行一個(gè)整數(shù)n表示世界樹的節(jié)點(diǎn)數(shù)。

【輸出格式】

T行，每行一個(gè)整數(shù)表示任意兩個(gè)“源”的奧術(shù)力量的差的最大值。

【樣例輸入】

2

5

12345

【樣例輸出】

1

9

【數(shù)據(jù)范圍】

對于10%的數(shù)據(jù)，n <= 10

對于40%的數(shù)據(jù)，n <= 2^31 – 1

對于60%的數(shù)據(jù)，n <= 10^100

對于80%的數(shù)據(jù)，n <= 10^1000

對于100%的數(shù)據(jù)，1 <= n <= 10^10000, T <= 50

前八個(gè)點(diǎn)時(shí)間限制2000ms，最后兩個(gè)數(shù)據(jù)點(diǎn)時(shí)間限制6000ms

構(gòu)造題

來來來我們來找規(guī)律

數(shù)學(xué)歸納法

height為k的樹可以由height為k-1和height為k-2的樹構(gòu)出 ? ?遞推式包含斐波拉契數(shù)列。高度為h的世界樹，至少包含S(h) = fib(h+3) – 1個(gè)節(jié)點(diǎn)。

然后

左為height，右為最小和最大高度

1　　1 1

2　　2 2

3　　2 3

4　　3 4

5　　3 5

6　　4 6

7　　4 7

8　　5 8

聰明的你一定已經(jīng)發(fā)現(xiàn)ans=(height-1)/2

?

矩陣乘法快速冪

判斷n處在哪兩個(gè)Fibonacci數(shù)之間，更準(zhǔn)確地說是找到最大的h，滿足fib(h+3) – 1 <= n，本題答案即為[h/2]

轉(zhuǎn)載于:https://www.cnblogs.com/awipppp/p/5971350.html

總結(jié)

以上是生活随笔為你收集整理的【fjwc2015】世界树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。