题解 | #和谐之树#

D.和谐之树

思路：

披着线段树外皮的二分。 把区间逐层二分。 注：要统计能到达的深度，深度相同时优先走右边 由构造规则可知，这是一个完全二叉树，易得n的左子节点编号为n2，右子节点编号为n2 + 1

代码

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
int t;
ll n, num, ans;

ll count (ll x) {
    ll tt = 1;  //统计该区间可划分的最大深度
    while (x > 1) {
        x = (x + 1) / 2;
        tt ++;
    }
    return tt;
}

void dfs (ll l, ll r, ll num) {
    ans = max (ans, num);
    
    if (l == r)
        return ;
    ll mid = l + r  >> 1;
    
    if (count(mid - l + 1) > count(r - mid )) //左边的区间能走得更深
        dfs (l, mid, num << 1);
    
    else 
        dfs (mid + 1, r, num << 1 | 1);

}


int main () {
    cin >> t;
    
    while (t --) {
        cin >> n;
        ans = 0;
        dfs (1, n, 1);  //[1, n]，编号从1开始
        cout << ans << endl;

    }
      
}