AT_abc401_d [ABC401D] Logical Filling 题解

题目传送门

解题思路

首先分析题意。

1. 容易发现类似 ?o，o? 的问号其实是“假问号”，因为 o 不能连续出现，所以只能是 .。

2. 其次就是当 $k$ 为字符串 $s$ 最多能包含 o 的数量时才可能会有 ? 变成 o。否则判完第 $1$ 条直接输出就行了。

那我们现在就来看看如何统计 $s$ 所能包含 o 的最大数量。

这里我们可以把 $s$ 拆分成若干个只含 ? 最长连续子串 $t_i$。

由于我们先处理了第 $1$ 种情况，所以 $t_i$ 会类似 .|????|.，其中 | 之间的字符串就是 $t_i$。我们手动模拟一下：

定义 $|s|$ 为字符串 $s$ 的长度。

• 当 $|t_i|$ 为奇数时，类似 o.o.o 时所包含 o 的数量最多。最多可以贡献 $\lceil \frac{|t_i|}{2}\rceil$ 个 o，在 C++ 中表示为 len / 2 + 1。

• 当 $|t_i|$ 为偶数时，类似 o.o.o.，.o.o.o 时所包含 o 的数量都是最多的，最多可以贡献 $\frac{|t_i|}{2}$ 个 o。

最后我们将所有贡献统计起来再加上原有的 o 的数量，如果为 $k$，那么长度为奇数的 $t_i$ 就可以确定，长度为偶数的 $t_i$ 就还是全是 ?。

至于为什么只有贡献为 $k$ 时才能确定，比如 $s$ 为 o.??.o.???，$k=4$，符合条件的字符串有 o.o..o.o..，o..o.o.o..，o.o..o..o.，o.o..o...o……你会发现每个 ? 都有多种可能。

CODE：

/*
15 7
????.?????.????5 3
?????4 2
?..?
*/
/*
15 7
????.?????.????5 3
?????4 2
?..?
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {ios::sync_with_stdio(false);ios_base::sync_with_stdio(false);cin.tie(0), cout.tie(0);int n, k, cnt = 0;cin >> n >> k;string a;cin >> a;cnt = (a[0] == 'o' ? 1 : 0);for (int i = 1; i < n; i++) {if (a[i] == '?' && (a[i - 1] == 'o' || i < n - 1 && a[i + 1] == 'o')) {a[i] = '.';}if (a[i] == 'o') {cnt++;}}if (cnt == k) {for (int i = 0; i < n; i++) {if (a[i] == '?') {a[i] = '.';}}cout << a;return 0;}if (a[0] == '?') {if (a[1] == 'o') {a[0] = '.';}}for (int i = 0; i < n; i++) {if (a[i] == '?') {//前后面一定是 .int j = i;while (a[i] == '?' && i < n) {i++;}//o.????.ocnt += (i - j + 1) / 2;  //（区间长度 + 1） / 2，算的只是 ？ 最多可以替换成多少个 o，懒得用 ceil//不用 i--，因为 a[i] 一定为 . }}if (cnt == k) {for (int i = 0; i < n; i++) {if (a[i] == '?') {//前后面一定是 .int j = i;while (a[i] == '?' && i < n) {i++;}if ((i - j) & 1) {for (int k = j; k < i; k++) {if ((k - j) % 2 == 0) {a[k] = 'o';} else {a[k] = '.';}}}}}}cout << a;return 0;
}