https://codeforces.com/contest/792/problem/D
题目大意
给出一棵 $n \ (\le 10^{18})$ 个节点的完全二叉树（$n + 1$ 保证为 $2^k$）。节点标号按照前序遍历顺序。给出 $q$ 个询问，每次询问为起点 $u_i$ 和操作序列 $s_i$，其中 $s_i$ 由 U, L, R 组成，分别表示走到父节点，走进左子树，走进右子树。如果操作不合法就跳过，问执行完 $s_i$ 后 $u_i$ 会移动到的节点编号。$(\sum s_i \le 10^5)$
简要题解
1000
0100 1100
0010 0110 1010 1110
0001 0011 0101 0111 1001 1011 1101 1111
容易得出，每层的二进制最低位是相同的。记这个最低位为 $2^i$
进入左右子树的下标是好算的，只需要加减 $2^{i - 1}$ 即可。
回到父节点则需要知道，当前位置是在左子树还是右子树，观察易发现，可以通过 $2^{i + 1}$ 位来判断。至此这个题就做完了。
复杂度
$T$：$O(\sum s_i)$
$S$：$O(\max(s_i))$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
inline LL lowbit(LL x) {
return x & (-x);
}
void solve() {
LL n;
int q;
cin >> n >> q;
LL rt = (n + 1) >> 1;
LL u;
string s;
for (int ii = 0; ii < q; ii++) {
cin >> u >> s;
for (char c : s) {
LL lb = lowbit(u);
if (c == 'L') {
if (lb == 1) continue;
u -= (lb >> 1);
} else if (c == 'R') {
if (lb == 1) continue;
u += (lb >> 1);
} else {
if (u == rt) continue;
if (u & (lb << 1)) {
u -= lb;
} else {
u += lb;
}
}
// cerr << u << ' ';
}
cout << u << '\n';
}
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: C. Divide by Three - Educational Codeforces Round 18