CF507C Guess Your Way Out! 题解
算法
模拟
思路
按照左右左右的方式先往下找,每次找到一个子节点时就看此节点为根的子树是否包含目标节点,如果包含就继续往下走,不包含说明目标叶子节点在另一边的子树上,那么肯定是先需要把这边的子树遍历完才能换到另一边,所以答案直接加上这个子树的大小。
代码中 \(cz\) 代表操作是左还是右,通过亦或实现取反的操作。注意要开 long long
。本题主要需要掌握二叉树的各种性质,基本不需要算法。
示例代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
namespace Ryan
{
int h, n;
signed work()
{
cin >> h >> n;
int cz = 0;
int end = pow(2, h - 1);
int ans = 0;
for (int i = h - 1; i >= 0; i--)
{
ans++;
if (!cz)
{
if (n > end)
{
ans += (pow(2, i + 1) - 1);
if (i)
end += pow(2, i - 1);
cz ^= 1;
}
else if (i)
end -= pow(2, i - 1);
}
else
{
if (n <= end)
{
ans += (pow(2, i + 1) - 1);
if (i)
end -= pow(2, i - 1);
cz ^= 1;
}
else if (i)
end += pow(2, i - 1);
}
cz ^= 1;
}
cout << ans << endl;
return 0;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
return Ryan::work();
}
标签:Guess,end,int,题解,long,cz,Way,pow
From: https://www.cnblogs.com/RyanAdam/p/18338489