前言

這次的 D 題出得很好，不僅融合了數學邏輯推理的知識，還有很多細節值得反復思考。雖然通過人數遠高于 E，但是通過率甚至不到 60%，可見這些細節正是出題人的側重點。

題目大意

給定一個長度為 $N$ 的字符串 $S$，由 o 和 . 組成。現在一些位置的字符不明確，用 ? 表示，可以替換成 o 和 . 中的任意一個。要求目標串（所有位置都被替換之后）同時滿足以下兩個條件：

• $S$ 中有恰好 $K$ 個 o。
• 任意兩個 o 不相鄰。

現在要填這個串，但是因為條件有限，只能完成部分內容。輸出所有答案唯一（可以確定）的位置的字符，其他位置仍用 ? 表示。

思路

為了簡化問題，我們要先從最簡單的位置入手，再解決其他位置。讓我們來分析一下都有哪些情況是確定的：

描述	結果	備注
一個問號與 o 相鄰	這里填 .	無
o 的數量已經達到 $K$	所有問號處填 .	無
o 的數量與問號的數量之和恰好為 $K$	所有問號處填 o	無
出現連著 $2?M+1$ 個問號，且這段里必須填 $M+1$ 個 o 1	這段形如 o.o.o.···.o	本人賽時曾忽略

然后我們執行這些操作無限次，直到無法更新任何地方（執行了之后該輪沒有任何格子被更新）為止。

代碼

賽時 AC 提交記錄：Submission #64790876。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;int n, k;
string s;
int t[200010];int main()
{cin >> n >> k >> s;s = " " + s + " ";int upd = 0;do{upd = 0;for (int i = 1; i <= n; i++)if (s[i] == '?'){if (i != 1 && s[i - 1] == 'o')s[i] = '.', upd++;if (i != n && s[i + 1] == 'o')s[i] = '.', upd++;}int cnt1 = 0, cnt2 = 0;for (int i = 1; i <= n; i++){if (s[i] == 'o') cnt1++;if (s[i] == '?') cnt2++;}if (cnt1 + cnt2 == k){for (int i = 1; i <= n; i++)if (s[i] == '?')s[i] = 'o', upd++;
//			break;}else if (cnt1 == k){for (int i = 1; i <= n; i++)if (s[i] == '?')s[i] = '.';
//			break;}for (int i = 1; i <= n; i++)if (s[i] == '?'){if (s[i - 1] == 'o')s[i] = '.', upd++;if (s[i + 1] == 'o')s[i] = '.', upd++;}int cnt = 0, c = 0, flag = 1;for (int i = 1; i <= n; i++)t[i] = 0;for (int i = 1; i <= n; i++){if (s[i] == '?')t[i] = t[i - 1] + 1;else{cnt += (t[i - 1] + 1) / 2;t[i] = 0;}}cnt += (t[n] + 1) / 2;for (int i = n; i >= 1; i--)if (t[i] && t[i + 1])t[i] = t[i + 1];if (cnt + cnt1 == k){for (int i = 1; i <= n; i++){
//				cout << t[i] << " " << i << endl;if (t[i] % 2 == 0) continue;if (s[i] == '?' && s[i - 1] != 'o')s[i] = 'o', upd++;else if (s[i] == '?')s[i] = '.', upd++;}
//			break;}} while (upd != 0);for (int i = 1; i <= n; i++)cout << s[i];return 0;
}
/*
7 3
?o????.
---
10 5
?????.????
*/

---

1. 如何判定這種情況？當前僅當數組中每一段連續的問號（長度為 $L$）都填 $?\frac{L}{2}?$ 個 o 時 o 的數量恰好為 $K$。 ??