P11375树上游走题解

· · 题解

题目传送门

本题仅需模拟即可，不需要二叉树的数据结构。第 2 或第 3 种移动后节点的编号变化在题目中已经写得很清楚了。

接下来考虑第 1 种移动后的节点编号变化，我们可以使用倒推法。

假设当前所在节点编号为 s，它的父节点编号为 i。如果 s 是 i 的左儿子，根据题意可得 2 \times i =s，求得 i=\frac{s}{2}。

如果 s 是 i 的右儿子，可得 2 \times i + 1 = s，求得 i=\frac{s-1}{2}（因为此时 s 一定是一个奇数，所以这个式子的值其实就相当于 \lfloor \frac{s}{2} \rfloor）。

综上所述，我们只需要用 s 整除以 2 就可以求出其父节点的编号。

还有一点：题目只说最后所处的节点编号不超过 10^{12}，没说经过的节点编号不超过 10^{12}，如果直接写就会喜提 40 分的成绩（因为会爆 long long）。这是教训。

解决方案：一旦编号超过 10^{12}，就暂时不进行第 2 或第 3 种移动。记下来，等到进行第 1 种移动时抵消掉。

最后按题意模拟即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long//不开long long见祖宗
int n,s,t;
int inf=1e12;
string str;
signed main(){
    cin>>n>>s;
    cin>>str;
    for(int i=0;i<str.size();i++){
        if(str[i]=='U'){
            if(s==1)continue;//根节点没有父节点
            if(t){
                t--;//抵消
                continue;
            }
            s/=2;
        }
        if(str[i]=='L'){
            if(2*s>inf)t++;//不进行移动，记录下来。
            else s*=2;
        }
        else if(str[i]=='R'){
            if(2*s+1>inf)t++;//同上。
            else s=s*2+1;
        }
    }
    cout<<s<<endl;
    return 0;
}