P16779 ⌈Xzy OI R1 T1⌋ 查查编

起晚了没参加……题目传送门核心思路观察样例解释图片我们可以发现如果以x xx为根节点的左子树不是一棵满二叉树那么它右子树的深度最多是左子树的深度减1 11如果它左子树是一棵满二叉树那么右子树的深度最多等于左子树的深度。当然啦为了使b bb尽可能的大所以右子树一定是一棵满二叉树。那么怎样求b bb呢首先求出右子树的深度用 C 表达就是log2(x-a1)因为左子树的节点编号是从a aa到x − 1 x-1x−1个数字所以其深度就是ceil(log2(x-a1))然而我们求的是右子树我们知道 C 的log2会自动向下取整所以当左子树不是满二叉树的时候log2返回的值会比左子树的深度小1 11正是右子树的深度而当左子树是满二叉树的时候log2返回的值就是左子树的深度同样也是右子树的深度。接下来我们就可以知道右子树的节点个数是1log2(x-a1)所以b bb的值就是x(1log2(x-a1))-1。好了上代码吧。AC 代码#includebits/stdc.hintt;ll a,x;intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cint;while(t--){cinax;coutx(1LLint(log2(x-a1)))-1\n;}// 注意要开 long long而且左移运算的时候 1 也要加上 LLlog2 要强转为 int 否则会编译错误的return0;}完结撒花 ✿✿ヽ(°▽°)ノ✿