题干：
 

妞妞听说Nowcoder Girl女生编程挑战赛要开始了, 但是她没有足够的勇气报名参加, 牛牛为了帮助妞妞,给她准备一台勇气获得机。初始的时候妞妞的勇气值是0, 勇气获得机有两个按钮:

1、N按钮: 如果当期拥有的勇气值为x, 按下之后勇气值将变为2*x+1，

2、G按钮: 如果当前拥有的勇气值为x, 按下之后勇气值将变为2*x+2，

勇气值过高也会膨胀,所以妞妞需要将自己的勇气值恰好变为n, 请你帮助她设计一个勇气获得机的按键方案使妞妞的勇气值恰好变为n。

输入描述:

输入包括一行, 包括一个正整数n(1 <= n <= 10^9), 表示妞妞最后需要的勇气值。

输出描述:

输出一行字符串, 每个字符表示该次妞妞选择按动的按钮,'N'表示该次按动N按钮,'G'表示该次按动G按钮。

示例1

输入

复制

20

输出

复制

NGNG

解题报告：

    这题运用到的二叉树的性质去构造一个数字，又因为二叉树的唯一性，所以构造出的这棵树一定是唯一的。

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以内才可以。。这套代码过了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开始构造这个二进制数，因为你如果刚开始都是0，那一直左移也没啥用（并且dfs中还要判断当前位是不是0，如果不是第0次进入才需要左移一位，，总之很麻烦），，所以需要先设置一个1，然后让他移位二进制记录就可以了，，最后输出的时候不要最高位就行了。