2022京东春招笔试4-2

T1：树上走路

第一题开unsigned long long也会超时，因此用数组模拟位运算，

当发生 $*2$ 操作的时候，尾部插入0
发生 $*2+1$ 操作的时候，尾部插入1
当发生 $/2$ 操作的时候，删除尾部元素
最后结果，构造答案即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s,val) memset(s, val, sizeof(s))
const int inf = INT_MAX;

int T;
int main(int argc, char * argv[]){
	long long n, x;
	string s;
	cin >> n >> x;
	cin >> s;
	vector<int> v;
	while(x){
		v.push_back(x & 1);
		x = x >> 1;
	}
	reverse(v.begin(), v.end());
	for(auto &ch : s){
		if(ch == 'U') v.pop_back();
		if(ch == 'L') v.push_back(0);
		if(ch == 'R') v.push_back(1);
	}
	reverse(v.begin(), v.end());
	unsigned long long power = 1, ans = 0;
	for(auto bit : v){
		ans += power * bit;
		power = power * 2; 
	}
	cout << ans;

    return 0;
}