10. Bob and a Binary tree

╮ 潜心 ╰

来自蒟蒻的提示:
找出从节点1到节点n的路径走法就行了
因为每次移动到左儿子改分母 移动到右儿子走改分子
所以求出从1计算到n什么时候×2(就是移动到左儿子) 什么时候 ×2+1(移动到右儿子)就可以了
然后开个栈每次除以2记录余数就行了啊?

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
*/
datastream

定义不了那么大的数组,大家都是怎么解决的呀。

zerol

因为根本就不需要定义数组。

你当前正在回复 博客/题目
存在问题!