1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
| #include <bits/stdc++.h>
using namespace std;
const int MaxN = 100010, MaxT = 1 << 18;
struct Tree_node {
int lazy, sum, len;
} tree[MaxT];
int s[MaxN], t[MaxN], sn, tn;
inline void build(int l, int r, int now) {
tree[now].len = r - l + 1;
tree[now].lazy = tree[now].sum = 0;
if (l == r) return;
int mid = (l + r) >> 1;
build(l, mid, now << 1);
build(mid + 1, r, now << 1 | 1);
}
inline void addLazy(int now, int lazy) {
tree[now].lazy = lazy;
tree[now].sum = (lazy - 1) * tree[now].len;
}
inline void pushDown(int now) {
if (tree[now].lazy) {
addLazy(now << 1, tree[now].lazy);
addLazy(now << 1 | 1, tree[now].lazy);
tree[now].lazy = 0;
}
}
inline void update(int now) {
tree[now].sum = tree[now << 1].sum + tree[now << 1 | 1].sum;
}
inline void modify(int l, int r, int now, int x, int y, int z) {
if (r < x || y < l) return;
if (x <= l && r <= y) return addLazy(now, z);
int mid = (l + r) >> 1;
pushDown(now);
modify(l, mid, now << 1, x, y, z);
modify(mid + 1, r, now << 1 | 1, x, y, z);
update(now);
}
inline int queryL(int l, int r, int now, int x) {
if (x < l) return 0;
if (tree[now].sum == tree[now].len) return 0;
if (l == r) return (tree[now].sum == 0) ? l : 0;
int mid = (l + r) >> 1;
pushDown(now);
int ret = queryL(mid + 1, r, now << 1 | 1, x);
if (!ret) ret = queryL(l, mid, now << 1, x);
return ret;
}
inline int queryR(int l, int r, int now, int x) {
if (x < l) return 0;
if (tree[now].sum == 0) return 0;
if (l == r) return (tree[now].sum == 1) ? l : 0;
int mid = (l + r) >> 1;
pushDown(now);
int ret = queryR(mid + 1, r, now << 1 | 1, x);
if (!ret) ret = queryR(l, mid, now << 1, x);
return ret;
}
inline void treeExport(int l, int r, int now, int x, int *p) {
if (l > x) return;
if (l == r) {
p[l] = tree[now].sum;
return;
}
int mid = (l + r) >> 1;
pushDown(now);
treeExport(l, mid, now << 1, x, p);
treeExport(mid + 1, r, now << 1 | 1, x, p);
}
inline void init(int *p, int &n) {
static char s[MaxN];
scanf("%s", s + 1);
int max = strlen(s + 1);
build(1, max, 1);
n = 0;
for (int i = 1; i <= max; ++i) {
if (s[i] == '1') {
++n;
modify(1, max, 1, n, n, 1);
} else if (s[i] == '2') {
++n;
modify(1, max, 1, n, n, 2);
} else if (s[i] == 'U') --n;
else if (s[i] == 'L') {
int pos = queryR(1, max, 1, n);
modify(1, max, 1, pos + 1, n, 2);
modify(1, max, 1, pos, pos, 1);
} else if (s[i] == 'R') {
int pos = queryL(1, max, 1, n);
modify(1, max, 1, pos + 1, n, 1);
modify(1, max, 1, pos, pos, 2);
}
}
treeExport(1, max, 1, n, p);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("board.in", "r", stdin);
#endif
init(s, sn);
init(t, tn);
register int sum = abs(sn - tn);
register int n = min(sn, tn);
register int ans = 2 * n, dis = 0;
bool flag = 1;
for (register int i = 1; i <= n; ++i) {
if (!flag) {
dis = dis * 2;
if (s[i] == 0) ++dis;
if (t[i] == 1) ++dis;
}
if (s[i] != t[i] && flag) {
flag = 0;
if (s[i] == 1) swap(s, t);
}
if (dis > ans) break;
ans = min(ans, dis + !flag + 2 * (n - i));
}
cout << sum + ans << endl;
return 0;
}
|
