d544 - 1. 海藻（algae）
題目描述
題目描述了一種特殊海藻的生長規則，要求計算第 N 天時，由左邊數來第 K 個分枝的顏色（0 代表綠色，1 代表黃色）。如果第 N 天時，海藻的分枝數少於 K，則輸出 -1。
解題思路
這道題的核心在於理解海藻的生長模式，並將其與斐波那契數列聯繫起來。第 n 天海藻的分枝數等於斐波那契數列的第 n+1 項。
程式碼使用遞迴和動態規劃（memoization）來計算第 n 天第 k 個分枝的顏色。dp(n, k) 函數遞迴地計算顏色。
如果 n 為奇數，則將問題分解為 dp(n-2, k) (如果 k 小於等於第 n-2 天的分枝數) 或 dp(n-1, k - fib[n-2]) (如果 k 大於第 n-2 天的分枝數)。
如果 n 為偶數，則將問題分解為 dp(n-2, k)、dp(n-3, k - fib[n-2]) 或 dp(n-2, k - fib[n-2] - fib[n-3])。
fib 陣列預先計算了斐波那契數列的值，用於快速查找第 n 天的分枝數。
複雜度分析
- 時間複雜度: O(N)
- 空間複雜度: O(N)
程式碼
#include <iostream>
using namespace std;
long long int fib[49]={0,1};
long long int dp(long long int n,long long int k){
if(n==1&&k==1)return 0;
else if(n==2&&k==1)return 1;
while(n>48)n-=2;
long long int size=fib[n];
if(k>size)return -1;
if(n%2){
long long int xs=fib[n-2],ys=fib[n-1];
if(k<=xs){
return dp(n-2,k);
}
else{
return dp(n-1,k-xs);
}
}
else{
long long int y1s=fib[n-2],xs=fib[n-3],y2s=fib[n-2];
if(k<=y1s){
return dp(n-2,k);
}
else if(k<=y1s+xs){
return dp(n-3,k-y1s);
}
else{
return dp(n-2,k-y1s-xs);
}
}
}
int main(){
for(int i=2;i<49;++i){
fib[i]=fib[i-1]+fib[i-2];
}
long long int m,n,k;
cin >> m;
while(m--){
cin >> n >> k;
cout << dp(n,k) << "\n";
}
}