題目鏈接：點擊查看

題目大意：給出 200 個石頭，有一只青蛙要從第 0 個石頭跳到第 200 個石頭，每次只能跳 1 步或 2 步，顯然可行的方案數是一個斐波那契數列，現在可以在兩個石頭上放置傳送門 x -> y ，當青蛙跳到石頭 x 上后，會立馬傳送到石頭 y 上，問如何構造傳送門，使得從 0 到 200 的方案數恰好外 m

題目分析：看到斐波那契數列，就不難想到齊肯多夫定理，考慮類比于二進制拆分那樣，用斐波那契數列將 m 進行拆分，因為 fib[ 44?] 才剛好大于 1e9，所以剩下了 150 多個位置可以用來進制拆分，首先簡單畫個圖，這個應該不難看出來，每個傳送門出去的方案數為 1 ，因為青蛙要么跳一步到達傳送門，要么跳兩步跳過傳送門，所以這樣是可行的

如上圖所示，每條紅線引出去的方案數都為 1?

這樣一來先倒著預處理一下斐波那契數列，fib[ x ] 的意義為，從第 x 個石頭到第 200 個石頭的方案數，這樣在上面理論的基礎上，相應的連邊表示拆分即可

有個小細節就是，需要特判一下 0

代碼：

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e3+100;LL fib[210];void init() {fib[200]=fib[199]=1;for(int i=198;i>=150;i--)fib[i]=fib[i+1]+fib[i+2]; }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);init();LL n;while(scanf("%lld",&n)!=EOF){if(n==0){puts("2");puts("1 1");puts("2 2");continue;}vector<int>pos;for(int i=150;i<=199;i++)if(n>=fib[i]){pos.push_back(i);n-=fib[i];}printf("%d\n",pos.size()+1);for(int i=0;i<pos.size();i++)printf("%d %d\n",2*i+1,pos[i]);printf("%d %d\n",pos.size()*2,pos.size()*2);}return 0; }

?

總結

以上是生活随笔為你收集整理的HihoCoder - 1873 Frog and Portal(构造+进制拆分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。