题目描述
给定一个长度为 N 的字符串 S，由字符 .、o 和 ? 组成。我们需要考虑所有通过将 S 中的每个 ? 独立地替换为 . 或 o 得到的字符串。令 X 为这些字符串中满足以下所有条件的集合：
1. 字符串中 o 的数量恰好为 K。
2. 字符串中没有两个 o 是相邻的。
题目保证集合 X 非空。
要求输出一个长度为 N 的字符串 T，其第 i 个字符 Ti 定义如下：
如果集合 X 中的 所有 字符串的第 i 个字符都是 .，则 Ti=.。
如果集合 X 中的 所有 字符串的第 i 个字符都是 o，则 Ti=o。
* 如果集合 X 中 既存在 第 i 个字符是 . 的字符串，又存在 第 i 个字符是 o 的字符串，则 Ti=?。
样例
输入:
4 2
o???
输出:
o.??
说明：
满足条件的字符串集合 X 包含两个字符串：”o.o.” 和 “o..o”。
- 第 1 个字符：在 X 中总是 ‘o’，所以 T₁ = ‘o’。
- 第 2 个字符：在 X 中总是 ‘.’，所以 T₂ = ‘.’。
- 第 3 个字符：在 X 中可以是 ‘o’ 或 ‘.’，所以 T₃ = ‘?’。
- 第 4 个字符：在 X 中可以是 ‘.’ 或 ‘o’，所以 T₄ = ‘?’。
最终输出 “o.??”.
算法 (贪心 / 构造)
O(N)
思路分析
这个问题的目标是确定最终输出字符串 T 的每个字符。Ti 的取值取决于在所有满足条件的字符串（集合 X）中，第 i 个位置的字符是否是固定的 (. 或 o)，还是可变的 (?)。
直接生成集合 X 并检查每个位置是非常困难的，因为 X 的大小可能是指数级的。我们需要找到一种更高效的方法来确定每个位置的最终状态。
代码采用了一种基于贪心和构造的思路，试图直接构建出最终的字符串 T。其核心逻辑如下：
-
处理强制的 ‘.’ (基于邻接规则):
“没有两个o相邻” 是一个非常强的局部约束。如果原始字符串S中已经存在一个o在位置i(S[i] == 'o')，那么在任何满足条件的字符串中，其相邻的位置i-1和i+1（如果存在）都必须是.。
代码的第一步就是应用这个规则。它遍历字符串S，如果发现S[i] == 'o'，就将其左右邻居（如果存在）强制设置为.。这一步修改了S，有效地将一些原本是?的位置根据邻接规则确定为.。
cpp // S 是输入的字符串 for (int i = 0; i < N; i++) { if (S[i] == 'o') { if (i) { // 如果 i > 0 S[i - 1] = '.'; // 强制左邻居为 '.' } if (i + 1 < N) { // 如果 i < N-1 S[i + 1] = '.'; // 强制右邻居为 '.' } } } // 此时 S 已经被部分修改
注意：这一步直接修改S。如果S[i-1]或S[i+1]原本就是o，会被覆盖成.，但这应该不会发生，因为题目保证集合X非空，意味着初始S(以及所有可生成的有效串) 不会有相邻的 ‘o’。如果它们原本是.，保持不变。如果原本是?，则被确定为.。 -
计算最大可能的 ‘o’ 数量 (
max):
在应用了上述规则后，字符串S包含.、o和?。现在我们需要考虑如何填充剩余的?来最大化o的数量，同时仍然满足“无相邻o”的规则。
考虑一段连续的?，长度为L。要在这段中放置最多的o且不相邻，最佳策略是采用o.o.o...或.o.o.o...的模式。- 如果长度
L是奇数，最佳模式是o.o...o，可以放置 (L+1)/2 个o。 - 如果长度
L是偶数，最佳模式是o.o...o.或.o.o...o，都可以放置 L/2 个o。
代码中计算max的方法是，先统计当前S中已有的o的数量，然后遍历S，找到所有连续的?块。对于一个长度为L = r - l的?块（从索引l到r-1），代码将(r - l + 1) / 2加到max中。
这里的(r - l + 1) / 2使用整数除法，对于长度L=r-l： - L=1: (1+1)/2 = 1
- L=2: (2+1)/2 = 1
- L=3: (3+1)/2 = 2
- L=4: (4+1)/2 = 2
这恰好等于在长度为L的块中可以放置的最大o数量 ⌈L/2⌉。
所以，变量max计算的是在满足不相邻约束下，最多可以放置多少个o。
cpp int max = std::count(S.begin(), S.end(), 'o'); // 统计初始（修改后）的 'o' for (int l = 0; l < N; l++) { if (S[l] == '?') { int r = l; while (r < N && S[r] == '?') { // 找到连续 '?' 块 [l, r) r++; } max += (r - l + 1) / 2; // 累加该块能贡献的最大 'o' 数 l = r; // 代码这里有误，应为 l = r - 1; 否则会跳过 r 位置 // 但鉴于 while 循环的条件，效果上是跳到 r 的位置开始下一次检查 } }
- 如果长度
-
处理
K == max的情况:
如果目标o的数量 K 正好等于我们能放置的最大数量max，这意味着每一个能够放置o的机会都必须被利用，才能达到 K 个o。这会对?的填充方式施加严格的限制。- 对于长度为
L的?块：- 如果
L是奇数，要达到最大值 (L+1)/2，唯一的填充模式是o.o...o。 - 如果
L是偶数，要达到最大值 L/2，有两种模式：o.o...o.或.o.o...o。
代码的逻辑是：只有当K == max并且遇到一个奇数长度的?块时，才将这个块确定地填充为o.o...o模式。因为只有在这种情况下，填充模式是唯一确定的。对于偶数长度的块，因为存在两种都能达到最大值的模式，所以代码没有修改它们，隐含的意思是这些位置在最终输出 T 中应该是?。
cpp if (K == max) { for (int l = 0; l < N; l++) { if (S[l] == '?') { int r = l; while (r < N && S[r] == '?') { r++; } if ((r - l) % 2 == 1) { // 如果块长度是奇数 for (int i = l; i < r; i++) { // 填充为 o.o...o 模式 S[i] = "o."[(i - l) % 2]; } } l = r; // 同样，这里应为 l = r - 1; } } }
特殊情况处理: 代码还包含一个K == max(这里的max是初始o数量) 的快速处理。如果在第一步强制 ‘.’ 之后，o的数量已经等于K，那么所有剩余的?都必须是.。
cpp int initial_max = std::count(S.begin(), S.end(), 'o'); // 指 S 应用邻接规则之后 if (K == initial_max) { std::replace(S.begin(), S.end(), '?', '.'); // 所有 '?' 必须是 '.' std::cout << S << "\n"; return 0; } // ... 计算包含 '?' 块的 max ... // ... 处理 K == max 的情况 ...
- 如果
- 对于长度为
-
最终输出:
在执行完上述步骤后，代码直接输出了最终的字符串S。
这个策略的隐含假设是：- 如果一个位置
i在初始时是o，它在 T 中就是o。 - 如果一个位置
i在初始时是.，或者因为邻接规则变成了.，或者因为K == initial_max被替换成了.，它在 T 中就是.。 - 如果一个位置
i是?，并且处于一个奇数长度的?块中，且K == max，那么它会被确定地填充为o或.，这就是它在 T 中的值。 - 所有其他情况下的
?（即K < max，或者K == max但在偶数长度块中），代码都让它们保持为?。这对应于 Ti=? 的情况，表示这个位置既可能填.也可能填o并且仍然可能构造出满足条件的字符串。
- 如果一个位置
-
正确性讨论:
这种方法的正确性依赖于一个关键假设：如果一个?位置没有在K == max且处于奇数块的条件下被强制赋值，那么一定存在一种填充方式使其为o且总数为K，并且也存在另一种方式使其为.且总数为K。- 当
K < max时，我们有放置o的”余地”。对于任何一个?，我们通常可以选择放.并尝试在别处弥补o的数量，或者选择放o(如果邻接规则允许) 并减少之后需要的o数量。这种灵活性使得这些?位置很可能对应 Ti=?。 - 当
K == max且块长为偶数时，例如????(L=4),K=2。我们可以填o.o.或.o.o.。第一个?可以是o或.。第二个?也可以是o或.。所以这些位置在 T 中是?是合理的。
该算法似乎能较好地处理确定性的情况 (.或o) 和不确定性的情况 (?)。
- 当
时间复杂度
- 第一个循环（强制邻居为
.）：遍历字符串一次，O(N)。 - 计算初始
o数量：O(N)。 - 计算
max：遍历字符串一次，内部while循环总共也只移动 N 步。O(N)。 - 处理
K == max的情况：遍历字符串一次，内部while和for循环总共也只处理 N 个字符。O(N)。 std::replace(如果执行)：O(N)。- 输出：O(N)。
整体时间复杂度为 O(N)。
C++ 代码
#include <bits/stdc++.h> // 引入所有标准库
using i64 = long long; // 定义 i64 为 long long 的别名
using u64 = unsigned long long; // 未使用
using u32 = unsigned; // 未使用
using u128 = unsigned __int128; // 未使用
int main() {
// 加速 IO
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, K; // 输入字符串长度 N 和目标 'o' 的数量 K
std::cin >> N >> K;
std::string S; // 输入字符串 S
std::cin >> S;
// 步骤 1: 应用邻接规则，强制 'o' 的邻居为 '.'
// 注意：这里直接修改 S
for (int i = 0; i < N; i++) {
if (S[i] == 'o') {
if (i) { // 处理左邻居
S[i - 1] = '.';
}
if (i + 1 < N) { // 处理右邻居
S[i + 1] = '.';
}
}
}
// 计算应用邻接规则后，S 中 'o' 的数量
int max = std::count(S.begin(), S.end(), 'o');
// 特殊情况：如果当前 'o' 的数量已经等于 K，则所有 '?' 必须填 '.'
if (K == max) {
std::replace(S.begin(), S.end(), '?', '.'); // 将所有 '?' 替换为 '.'
std::cout << S << "\n"; // 输出结果
return 0; // 结束程序
}
// 步骤 2: 计算在剩余 '?' 中最多还能放多少个 'o'，累加到 max
// 遍历字符串 S
for (int l = 0; l < N; l++) {
if (S[l] == '?') { // 找到一个 '?' 块的开始
int r = l;
// 找到这个 '?' 块的结束位置 r (块是 [l, r-1])
while (r < N && S[r] == '?') {
r++;
}
int length = r - l; // 块的长度
// 长度为 length 的块最多能放 (length + 1) / 2 个 'o'
max += (length + 1) / 2;
l = r - 1; // 将 l 移动到块的末尾，准备下一次循环 (外层 l++ 后到 r)
// 原代码是 l = r; 有微小问题但结果可能一样
}
}
// 步骤 3: 处理 K == max 的情况
// 如果目标 K 等于能达到的最大 'o' 数
if (K == max) {
// 再次遍历 S，找到 '?' 块
for (int l = 0; l < N; l++) {
if (S[l] == '?') {
int r = l;
while (r < N && S[r] == '?') {
r++;
}
int length = r - l;
// 如果块的长度是奇数，则填充模式是唯一确定的 'o.o...o'
if (length % 2 == 1) {
for (int i = l; i < r; i++) {
// 使用 (i - l) % 2 来交替填充 'o' 和 '.'
S[i] = "o."[(i - l) % 2];
}
}
// 如果块长度是偶数，填充模式不唯一 (o.o.. 或 .o.o.)
// 代码不处理这种情况，保持 '?' 不变，符合 T[i] = '?' 的定义
l = r - 1; // 移动 l 到块末尾
}
}
}
// 步骤 4: 输出最终的字符串 S
// 对于 K < max 的情况，以及 K == max 时偶数长度块中的 '?'，都保持为 '?'
// 这代表这些位置的可能性不唯一
std::cout << S << "\n";
return 0; // 程序正常结束
}
