f508 - 12041 - BFS (Binary Fibonacci String)
題目描述
題目定義了一個二進位制的費波那契字串 BFS，其中 BFS(0) = "0"，BFS(1) = "1"，BFS(n) = BFS(n-2) + BFS(n-1)。題目要求輸出 BFS(N) 字串中從第 L 個字元到第 R 個字元（包含 L 和 R）的子字串。
解題思路
這題的核心在於高效地計算 BFS(N) 的第 k 個字元，而不需要實際生成整個字串。程式碼使用遞迴的方式來模擬 BFS 的生成過程，並根據 k 的值來決定遞迴到哪一個子問題。
首先，預先計算出費波那契數列，用於確定每個 BFS(n) 的長度。在 dp 函數中，如果 n 大於 69，則使用 n = 68 - n % 2 來避免整數溢位，因為 BFS(n) 的長度會快速增長。
遞迴過程中，根據 k 的大小，判斷它落在 BFS(n-2) 還是 BFS(n-1) 中。如果 k 小於或等於 BFS(n-2) 的長度，則遞迴計算 BFS(n-2) 的第 k 個字元。否則，遞迴計算 BFS(n-1) 的第 (k - BFS(n-2)) 個字元。
在主函數中，對於每個測試案例，程式碼遍歷從 L 到 R 的每個位置 i，並使用 dp 函數計算 BFS(N) 的第 i+1 個字元，然後輸出該字元。
複雜度分析
- 時間複雜度: O(R-L+1) * O(N)，其中 N 是輸入的數字，R 和 L 是查詢的範圍。每次查詢需要遞迴調用 dp 函數，最壞情況下遞迴深度為 N。
- 空間複雜度: O(N)，主要用於儲存費波那契數列和遞迴調用堆疊。
程式碼
#include <iostream>
using namespace std;
long long int fib[70]={0,1},ac,g;
void dp(long long int n,long long int k){
if(n==1&&k==1){
cout << "0";
g=1;
return;
}
else if(n==2&&k==1){
cout << "1";
return;
}
if(n>69)n=68-n%2;
long long int size=fib[n];
if(k>size){
ac=0;
return;
}
if(n%2){
long long int xs=fib[n-2];
if(k<=xs){
dp(n-2,k);
}
else{
dp(n-1,k-xs);
}
}
else{
long long int y1s=fib[n-2],xs=fib[n-3];
if(k<=y1s){
dp(n-2,k);
}
else if(k<=y1s+xs){
dp(n-3,k-y1s);
}
else{
dp(n-2,k-y1s-xs);
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
for(int i=2;i<70;++i){
fib[i]=fib[i-1]+fib[i-2];
}
long long int m,n,l,r;
cin >> m;
while(m--){
ac=1;
cin >> n >> l >> r;
++n;
g=0;
for(int i=l;i<=r&∾++i){
if(g==1){
cout << '1';
g=0;
}
else{
dp(n,i+1);
}
}
cout << "\n";
}
}