題干：
?

妞妞聽說Nowcoder Girl女生編程挑戰(zhàn)賽要開始了, 但是她沒有足夠的勇氣報名參加, 牛牛為了幫助妞妞,給她準(zhǔn)備一臺勇氣獲得機。初始的時候妞妞的勇氣值是0, 勇氣獲得機有兩個按鈕:

1、N按鈕: 如果當(dāng)期擁有的勇氣值為x, 按下之后勇氣值將變?yōu)?*x+1，

2、G按鈕: 如果當(dāng)前擁有的勇氣值為x, 按下之后勇氣值將變?yōu)?*x+2，

勇氣值過高也會膨脹,所以妞妞需要將自己的勇氣值恰好變?yōu)閚, 請你幫助她設(shè)計一個勇氣獲得機的按鍵方案使妞妞的勇氣值恰好變?yōu)閚。

輸入描述:

輸入包括一行, 包括一個正整數(shù)n(1 <= n <= 10^9), 表示妞妞最后需要的勇氣值。

輸出描述:

輸出一行字符串, 每個字符表示該次妞妞選擇按動的按鈕,'N'表示該次按動N按鈕,'G'表示該次按動G按鈕。

示例1

輸入

復(fù)制

20

輸出

復(fù)制

NGNG

解題報告：

? ? 這題運用到的二叉樹的性質(zhì)去構(gòu)造一個數(shù)字，又因為二叉樹的唯一性，所以構(gòu)造出的這棵樹一定是唯一的。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<stack> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; ll n; stack<char> sk; int main() {cin>>n;while(n) {if(n&1) {sk.push('N');n=(n-1)/2;}else {sk.push('G');n=(n-2)/2;}}while(sk.size()) putchar(sk.top()),sk.pop();return 0 ;}

?

TLE代碼：（搜索要1e8以內(nèi)才可以。。這套代碼過了70%的樣例）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; int tot; char s[55]; ll n; int dep; ll dfs(ll cur,ll ans,int step) {if(cur > n) return 0 ;if(cur == n) {dep=step;return ans;}/*if(step!=0) */ans<<=1;ll res = dfs(cur*2+1,ans,step+1);if(res) return res;else return dfs(cur*2+2,ans+1,step+1); } int main() {cin>>n;ll qq = dfs(0,1,0); // printf("%lld\n",dfs(0,0,0));//printf("%lld\n",qq);while(qq) {if(qq&1) s[++tot] = 'G';else s[++tot] = 'N';qq>>=1;}ll tmp = 0;for(int i = tot-1; i>=1; i--) putchar(s[i]),tmp = tmp*2+s[i]=='N'?2:1;return 0 ;}

這個搜索里面也有很多技巧在里面的。。比如不能直接從0開始構(gòu)造這個二進制數(shù)，因為你如果剛開始都是0，那一直左移也沒啥用（并且dfs中還要判斷當(dāng)前位是不是0，如果不是第0次進入才需要左移一位，，總之很麻煩），，所以需要先設(shè)置一個1，然后讓他移位二進制記錄就可以了，，最后輸出的時候不要最高位就行了。

總結(jié)

以上是生活随笔為你收集整理的【牛客 - 315B】 勇气获得机（二叉树性质，思维，知识点，tricks）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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