B
题目大意：Monocarp 有一副从 $1$ 到 $n$ 编号的牌。起初，这些牌按照从小到大的顺序排列，$1$ 在顶部，$n$ 在底部。Monocarp 对这副牌进行了 $k$ 次操作。每次操作类型有三种： - 移除顶部的牌； - 移除底部的牌； - 移除顶部或底部的任意一张牌。需要判断每张牌的状态：它现在是否仍在牌堆中，已经被移除，还是可能两种情况都有可能。
数据范围：$1 \le t \le 10^4$，$1 \le k \le n \le 2 \cdot 10^5$，$\sum n \le 2 \cdot 10^5$。
思路：
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
| void solve() {
ll n, k;
cin >> n >> k;
string s;
cin >> s;
vl a(n + 1, 1);
int tem = 0;
int l = 1, r = n;
rep(i, 0, k - 1) {
if (s[i] == '0') {
a[l] = 0;
l++;
} else if (s[i] == '1') {
a[r] = 0;
r--;
} else
tem++;
}
if (r - l + 1 <= tem) {
rep(i, 0, n - 1) cout << '-';
cout << endl;
return ;
}
rep(i, l, l + tem - 1) {
if (a[i] == 0)
continue;
else
a[i] = 2;
}
frep(i, r, r - tem + 1) {
if (a[i] == 0)
continue;
else
a[i] = 2;
}
rep(i, 1, n) {
if (a[i] == 0)
cout << '-';
else if (a[i] == 1)
cout << '+';
else
cout << '?';
}
cout << endl;
return;
}
|
C
题目大意：Monocarp 有一个长度为 $n$ 的字符串 $s$，只包含字母 ‘a’ 和 ‘b’。他想从字符串 $s$ 中删除一些（可能为零）连续的字母，使得剩余字符串中 ‘a’ 和 ‘b’ 的个数相等。Monocarp 可以从字符串 $s$ 的任意位置开始删除连续的字母。Monocarp 非常喜欢他的字符串 $s$，因此他希望删除的连续字母数量尽可能少。需要确定，Monocarp 需要从字符串 $s$ 中删除的连续字母的最小数量，使得剩余字符串中 ‘a’ 和 ‘b’ 的数量相等。
数据范围：$1 \le t \le 10^4$，$2 \le n \le 2 \times 10^5$，$\sum n \le 2 \times 10^5$。
思路：
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
| void solve() {
ll n;
cin >> n;
string s;
cin >> s;
int tot0 = 0, tot1 = 0;
rep(i, 0, n - 1) {
if (s[i] == 'a')
tot0++;
else
tot1++;
}
map<ll, ll> ma;
ma[0] = -1;
ll tem = tot0 - tot1;
if (tem == 0) {
cout << 0 << endl;
return;
}
ll tem2 = 0;
ll ans = LLONG_MAX;
rep(i, 0, n - 1) {
tem2 += (s[i] == 'a' ? 1 : -1);
if (ma.find(tem2 - tem) != ma.end()) ans = min(ans, i - ma[tem2 - tem]);
ma[tem2] = i;
}
cout << (ans == n ? -1 : ans) << endl;
return;
}
|
