NOIP 模拟赛原题，赛时没切。
我们可以先考虑 \(30\) 分的部分分怎么打，\(n \le 50\)。对于每一个点去维护两个信息 \(pos\) 和 \(depth\) 分别表示当前这个点所在位置的编号是多少以及它在第几层，我们从两个点最后的状态往回考虑。然后用一个贪心的思想，深度大的点一定会先一直沿着父亲节点走，直到两个点深度相同，然后既可以选择横着直接到达也可以选择两个点一起继续往上走，把所有情况取 \(\min\) 即可。因为深度不超过 \(50\)，所以点的编号不超过 \(2^{50}\)，不会爆 long long。
（这里点的编号顺序是从上到下，从左到右依次升序编号）
维护 \(pos\) 值的方法：
-
走到左儿子：\(pos \times 2\)。
-
走到右儿子：\(pos \times 2 +1\)。
-
走到左边节点：\(pos-1\)。
-
走到右边边节点：\(pos+1\)。
-
走到父亲节点：$\left \lfloor \frac{pos}{2} \right \rfloor $。
维护 \(depth\) 值的方法：
-
走到左儿子：\(depth+1\)。
-
走到右儿子：\(depth+1\)。
-
走到左边节点：\(depth\) 不变。
-
走到右边节点：\(depth\) 不变。
-
走到父亲节点：\(depth-1\)。
然后考虑正解。我们会发现其实 \(30\) 分代码的时间复杂度是 \(O(n)\) 的，没有问题，关键的问题是存编号的 \(pos\) 会爆 long long，需要把这一部分优化。又因为这是一棵完全二叉树，操作无非就是乘二除二加一减一，所以可以想到用一个二进制串来维护操作，这个串的长度就是深度，值就是点的编号，相当于把上述两种操作合并到了一起，并且还不会爆 long long。
维护二进制串的方法：
-
走到左儿子：\(pos_{++depth} = 0\)。
-
走到右儿子：\(pos_{++depth} = 1\)。
-
走到左边节点：\(pos_{depth}--\)。
-
走到右边节点：\(pos_{depth}++\)。
-
走到父亲节点：把 \(pos\) 的最后一位删掉。
注意有可能中间会有进位的情况，可以到最后一起进位即可。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair <int,int> pii;
const int MAXN = 1e5 + 10;
char a[MAXN],b[MAXN];
int p[MAXN],q[MAXN],ans = 1e18,n,m,cnt1,cnt2,cnt,sum;
inline void solve1(int id){p[id - 1] += (p[id] - (p[id] & 1)) >> 1;p[id] &= 1;}
inline void solve2(int id){q[id - 1] += (q[id] - (q[id] & 1)) >> 1;q[id] &= 1;}
signed main()
{
scanf("%s%s",(a + 1),(b + 1));
n = strlen(a + 1),m = strlen(b + 1);
for(int i = 1;i <= n;i++)
{
if(a[i] == '1') p[++cnt1] = 0;
if(a[i] == '2') p[++cnt1] = 1;
if(a[i] == 'L') p[cnt1]--;
if(a[i] == 'R') p[cnt1]++;
if(a[i] == 'U') solve1(cnt1),cnt1--;
}
for(int i = cnt1;i > 1;i--) solve1(i);
for(int i = 1;i <= m;i++)
{
if(b[i] == '1') q[++cnt2] = 0;
if(b[i] == '2') q[++cnt2] = 1;
if(b[i] == 'L') q[cnt2]--;
if(b[i] == 'R') q[cnt2]++;
if(b[i] == 'U') solve2(cnt2),cnt2--;
}
for(int i = cnt2;i > 1;i--) solve2(i);
cnt = min(cnt1,cnt2);
for(int i = 0;i <= cnt && sum < 1e6;i++) sum = sum * 2 + (p[i] - q[i]),ans = min(ans,abs(sum) + 2 * (cnt - i));
printf("%lld",ans + abs(cnt1 - cnt2));
return 0;
}