ABC 243 D - Moves on Binary Tree（树+字符串）

https://atcoder.jp/contests/abc243/tasks/abc243_d

题目大意：

给定一颗完全二叉树，他总共可以有(2^10^100)-1个节点，节点下标为1,2,...,(2^10^100)-1。

给我们一个长度为n的字符串s，给定当前位于的节点位置

为我们经过这个字符串的操作后，我最后站在了哪个位置上？

字符串S包含三种字符：U退回当前子节点，L去当前左孩子处，R去当前右孩子处。

这道题目其实思维并不难，但是难点就是在于他的节点数量特别的大
考我们如何优化
你可以试一试常规的写法，能ac的点特别少，大多都wa了，hh（我一开始天真的以为就是这么简单）

• 首先我们可以想，一个节点要走到左孩子，那只能2，要想走到右孩子，那只能2+1

• 但是如果我们先去了左孩子，再返回根节点，其实没什么必要，可以在此优化步骤；

• 然后如果我们先去了右孩子，再返回根节点，其实也是没必要，直接优化，而且更可能的是，精度丢失，影响操作

• 直接把这两步从S中优化掉即可

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1000020;
const LL N=500200,M=2002;
#define l first
#define r second
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        LL n,k;
        cin>>n>>k;
        string s;
        cin>>s;
        deque<char> st;
        for(LL i=0;i<s.size();i++)
        {
            if(st.empty()||st.back()=='U') st.push_back(s[i]);
            else if(s[i]=='U') st.pop_back();
            else st.push_back(s[i]);
        }
        for(LL i=0;i<st.size();i++)
        {
            if(st[i]=='U') k/=2;
            else if(st[i]=='L') k*=2;
            else if(st[i]=='R') k=k*2+1;
        }
        cout<<k<<endl;
    }
    return 0;
}