B
题目大意：有一个长度为 $n$ 的字符串 $T$，满足所有奇数位置 $T_i$ 都为 ‘a’，所有偶数位置 $T_i$ 都为 ‘b’。有一天，Bob 用如下算法生成了一个字符串 $S$： 1. 令 $S$ 为空字符串。2. 从 $T$ 的首字母或尾字母中任选其一，取走并追加到 $S$ 的末尾。3. 若 $T$ 为空，则结束并返回字符串 $S$。否则，返回步骤 2。之后，Bob 将生成的字符串 $S$ 写在纸条上，若干年后他发现这张纸条已经磨损，甚至可能有人偷偷改动过其中一些字母。现在，Bob 想知道字符串是否被改动过！你得到一个长度为 $n$ 的字符串 $X$，$X$ 只包含 ‘a’、‘b’ 和 ‘?’。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 200\,000$，$\sum n \le 200\,000$。
思路：
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
| void solve() {
int n;
cin >> n;
string s;
cin >> s;
string t;
if (n % 2 == 1) {
if (s[0] == 'b') {
cout << "NO" << endl;
return;
}
for (int i = 2; i <= n - 1; i += 2) {
if (s[i] == 'a' && s[i - 1] == 'a' || s[i] == 'b' && s[i - 1] == 'b') {
cout << "NO" << endl;
return;
}
}
} else {
for (int i = 1; i <= n - 1; i += 2) {
if (s[i] == 'a' && s[i - 1] == 'a' || s[i] == 'b' && s[i - 1] == 'b') {
cout << "NO" << endl;
return;
}
}
}
cout << "YES" << endl;
return;
}
|
C1
题目大意：这是本题的简单版本。不同版本的区别在于，在本题中你只需要为一个序列计算一个值。只有在你解决了所有版本的问题后，你才能对其进行 hack。我们定义一种生成包含 $m+k$ 个整数的算法如下： 1. 首先，输入一个长度为 $m$ 的整数序列 $x$。如果 $k=0$，则直接终止并返回序列 $x$。2. 然后，选择任意一个下标 $1 \le i \le |x|$，并在元素 $x_i$ 之后插入一个数 $(x_i+1)$。3. 如果 $x$ 的长度恰好等于 $m+k$，则终止并返回序列 $x$。否则，返回第二步继续操作。Alice 知道古代文明曾经使用这个算法来安全地隐藏他们的秘密。Alice 想要了解他们所隐藏的知识，但要从算法的输出反推输入并不容易。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 300\,000$，$1 \le a_i \le 10^9$，$\sum n \le 300\,000$。
思路：
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
| void solve() {
int n;
cin >> n;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
int las = -1;
int ans = 0;
int i = 0;
while (i <= n - 1) {
int j = i + 1;
map<int, int> ma;
ma[a[i]]++;
while (j <= n - 1) {
if (a[j] <= a[j - 1] + 1 && a[j] > a[i]) {
j++;
}
else {
break;
}
}
ans++;
i = j;
}
cout << ans << endl;
return;
}
|
C2
题目大意：这是本题的困难版本。不同之处在于，在这个版本中，你必须计算所有子区间的值的总和。只有当你解决了本题的所有版本时才可以进行 Hack。我们定义生成 $m+k$ 个整数序列的算法如下： 1. 首先，输入一个长度为 $m$ 的整数序列 $x$。如果 $k=0$，立即终止并返回序列 $x$。2. 然后，选择任意一个下标 $1 \le i \le |x|$，并在 $x_i$ 之后插入一个值为 $x_i+1$ 的元素。3. 如果 $x$ 恰好包含 $m+k$ 个整数，终止并返回序列 $x$。否则，返回执行第二步。Alice 知道远古文明曾用这种算法来安全地隐藏他们的秘密。Alice 很想知道他们藏的知识，但根据输出推测输入并不容易。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 300\,000$，$1 \le a_i \le 10^9$，$\sum n \le 300\,000$。
思路：
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() {
int n;
cin >> n;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
ll ans = 1LL * n * (n + 1) / 2;
ll tem = 0;
vi l(n, -1);
stack<int> s;
rep(i, 0, n - 1) {
while (!s.empty() && a[s.top()] >= a[i]) s.pop();
if (!s.empty()) l[i] = s.top();
s.push(i);
}
int las = 0;
vi l2(n, 0);
rep(i, 1, n - 1) {
if (a[i] > a[i - 1] + 1) {
las = i;
}
l2[i] = las;
}
rep(i, 1, n - 1) {
int tem = (l2[i] > l[i]) ? i : (i - l[i] - 1);
ans += 1LL * tem * (n - i);
}
cout << ans << endl;
return;
}
|
D
题目大意：有 $2n$ 张牌，每张牌上写有编号 $1, 1, 2, 2, \ldots, n, n$。也就是说，对所有 $j=1,2,\ldots,n$，恰好有 $2$ 张编号为 $j$ 的牌。每张牌的正面只写有一个数字。你要玩一个翻牌游戏。初始时，全部 $2n$ 张牌都是牌背朝上（不显示数字的一面）。每回合，你要翻开恰好两张牌。如果这两张牌的数字相同，你就将它们从场上移除。否则，需要把它们重新扣回原来的位置。你在所有 $2n$ 张牌都被移除时获胜。注意，你不需要同时翻两张牌，因此你可以先看到第一张牌的数字后，再决定翻哪一张作为第二张。考虑如下贪心算法来玩这个游戏。起始时，$2n$ 张牌被按某个顺序一排放好。
数据范围：$1 \le t \le 10^3$，$1 \le n \le 300\,000$，$1 \le k \le 1\,000\,000$，$\sum n \le 300\,000$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| void solve() {
int n, k;
cin >> n >> k;
if (k > 2 * n - 1 || k < n) {
cout << "NO" << endl;
return;
}
cout << "YES" << endl;
if (k == n) {
rep(i, 1, n) cout << i << ' ' << i << ' ';
cout << endl;
return;
}
int tem = k - n;
int res = k + 1 - n;
cout << "1 2 ";
rep(i, 3, res) cout << i << ' ' << i - 2 << ' ';
cout << res - 1 << ' ' << res << ' ';
rep(i, res + 1, n) cout << i << ' ' << i << ' ';
cout << endl;
return;
}
|
E
题目大意：一个“正规括号序列”是仅由 “(” 和 “)” 组成的序列，可以通过在该序列中随意插入 $1$ 和 $+$ 变成合法的数学表达式。现在给你一个正规括号序列 $S$。我们定义右移一个子序列。具体地，若将子序列 $S_{i_1} S_{i_2} \ldots S_{i_k}$ 右移，则这些被选中位置上的字符会被同时重新赋值如下： - $S_{i_1} \leftarrow S_{i_k}$； - $S_{i_2} \leftarrow S_{i_1}$； - $S_{i_3} \leftarrow S_{i_2}$； - $\ldots$ - $S_{i_k} \leftarrow S_{i_{k-1}}$。
数据范围：$1 \le t \le 10^4$，$2 \le n \le 300\,000$，$\sum n \le 300\,000$。
思路：
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
| const int MOD = 998244353;
const int MX = 3e5 + 1;
int cnt[MX];
auto init = [] {
cnt[0] = 1;
rep(i, 1, MX - 1) { cnt[i] = cnt[i - 1] * 2 % MOD; }
return 0;
}();
void solve() {
int n;
cin >> n;
string s;
cin >> s;
ll ans = 0;
ll f = 0, g = 0;
ll pre = 0;
rep(i, 0, n - 1) {
if (s[i] == '(') {
ans += cnt[i];
ans %= MOD;
pre++;
f = (2 * f + g + 1) % MOD;
} else {
pre--;
ans += (f + g + 1) % MOD;
ans %= MOD;
g = (2 * g + f + 1) % MOD;
}
if (pre < 2) f = 0;
}
cout << ans << endl;
return;
}
|
