来自蒟蒻的提示：
找出从节点1到节点n的路径走法就行了
因为每次移动到左儿子改分母 移动到右儿子走改分子
所以求出从1计算到n什么时候×2（就是移动到左儿子） 什么时候 ×2+1（移动到右儿子）就可以了
然后开个栈每次除以2记录余数就行了啊？
10. Bob and a Binary tree
myyurisa
我理解的蒟蒻的提示,没有用栈
include
int main() {
int i, n, a[40], num, r, p, q, j;
scanf(“%d”, &n);
for (i = 1; i <= n; i++) {
int l = 0;
scanf(“%d”, &num);
while (num > 0) {
r = num % 2;
num /= 2;
a[l++] = r;
}
p = 1;
q = 1;
if (l > 1) {
for (j = l - 2; j >= 0; j–) {
if (a[j] == 0) {
q = p + q;
} else {
p = p + q;
}
}
}
printf(“Case %d: %d/%d\n”, i, p, q);
}
return 0;
}
10175102262 LarsPendragon
没有看懂自称巨弱的大佬的提示
思路：先判断哪一层，然后判断在哪棵子树（自底向顶）
因为我菜，所以代码写的很丑。
#include <bits/stdc++.h>
using namespace std;
long long n, p, q;//p分母，q分子
void F(long long low, long long high)
{
if(low>=high) return;
double mid=double(low+high)/2;
if(n>mid)
{
long long hmid=(long long)mid+1;
q+=p;
F(hmid, high);
}
else
{
long long lmid=(long long)mid;
p+=q;
F(low, lmid);
}
return;
}
int main()
{
long long n2[33]={1};
for(int i=1; i<33; i++) n2[i]=2*n2[i-1];
int T;
cin>>T;
for(int I=0; I<T; I++)
{
p=q=1;
int pos;
cin>>n;
for(pos=0; pos<33; pos++) if(n<n2[pos]) break;
F(n2[pos-1], n2[pos]-1);
cout<<"Case "<<I+1<<": "<<q<<'/'<<p<<endl;
}
return 0;
}
徐摆渡
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define arrayDebug(a, l, r) for(int i = l; i <= r; ++i) printf("%f%c", a[i], " \n"[i == r])
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int DX[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int MOD = 1e9 + 7;
const int N = 1e3 + 7;
const double PI = acos(-1);
const double EPS = 1e-8;
using namespace std;
inline int read()
{
char c = getchar();
int ans = 0, f = 1;
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) {ans = ans * 10 + c - '0'; c = getchar();}
return ans * f;
}
pii dfs(int n)
{
if(n == 1) return pii{1, 1};
if(n % 2) {
pii ans = dfs((n - 1) / 2);
return pii{ans.fi + ans.se, ans.se};
}
else {
pii ans = dfs(n / 2);
return pii{ans.fi, ans.fi + ans.se};
}
}
int gcd(int x, int y) {return y ? gcd(y, x % y) : x;}
void trans(pii ans)
{
int x = ans.fi, y = ans.se;
int r = gcd(x, y);
printf("%d/%d\n", x / r, y / r);
}
int t, n, cnt;
int main()
{
t = read();
while(t--){
n = read();
pii ans = dfs(n);
printf("Case %d: ", ++cnt);
trans(ans);
}
return 0;
}
/*
4
4
*/
因为根本就不需要定义数组。