P15274 [IOI 2016] Paint By Numbers 按数目填色

**仅支持 C++ 交互。** 你不需要引入额外的头文件，但请在代码头部加入如下内容（也可将其前两行换成其他包含 `std::string` 和 `std::vector` 的头文件）： ```cpp #include #include extern "C" { std::string solve_puzzle(std::string s, std::vector c); } ```

按数目填色是个有名的智力游戏。我们现在考虑的是这个游戏的一维版本。在这个游戏中，玩家会有一行 $n$ 个方格。这些方格从左到右分别编号为 $0$ 至 $n - 1$。玩家必须要为这些方格填上黑色或白色，我们用 `X` 代表填上黑色的方格并用 `_` 来代表填上白色的方格。 系统将会给玩家一个提示，这个提示是一个含有 $k$ 个正整数的序列 $c = [c_0, \ldots, c_{k - 1}]$。而玩家必须要根据提示为方格填色，填色的要求是在这行上，填上黑色的方格必须组成 $k$ 个连续的区间，而且，在由左开始的第 $i$ (由 $0$ 开始) 个区间上必须含有 $c_i$ 个黑色方格。例如，若提示为 $c = [3, 4]$，则该游戏的正确填色方法是必须含有两个由连续黑色格位组成的区间，这两个区间的长度分别是 $3$ 和 $4$。因此，若 $n = 10$ 且 $c = [3, 4]$ 的话，则满足提示的一个正确的填色方法是 `_XXX__XXXX`。要注意的是 `XXXX_XXX__` 并不满足提示，因为黑色的区间的长度顺序不正确。同时 `__XXXXXXX_` 也不满足提示，因为它只含有一个黑色区间而非两个分开的黑色区间。 你将获得一个部分方格已填好颜色的游戏行格，即，你知道 $n$ 及 $c$ 的值，并且你也知道有些方格一定是黑色和有些方格一定是白色。你的工作是从中推算出更详细的方格的信息。 更加详细来说，一个正确的游戏解应该满足提示，并且和已经知道颜色的方格的颜色一致。你的程序必须找出在所有正确的游戏解中都会填上黑色的方格和在所有正确的游戏解中都会填上白色的方格。 你可以假设每个输入一定存在至少一个正确的游戏解。 ### 实现细节 你必须编写程序以实现以下的函数（或方法）： - `std::string solve_puzzle(std::string s, std::vector c)` - $s$：一个含有 $n$ 个字符的字符串。而对于每 $i\ (0 \le i \le n - 1)$，字符 $i$ 将会是以下其中一个： - `X`：表示方格 $i$ 必须要填上黑色， - `_`：表示方格 $i$ 必须要填上白色， - `.`：表示方格 $i$ 没有任何信息。 - $c$：是一个长度为 $k$ 的数组，它的内容是上述的提示， - 这个函数必须返回一个长度为 $n$ 的数组。对于每个 $i\ (0 \le i \le n - 1)$ 而言，输出字符串的第 $i$ 个字符应该是以下其中一个： - `X`：表示在所有游戏解中，第 $i$ 个方格都是填上黑色， - `_`：表示在所有游戏解中，第 $i$ 个方格都是填上白色， - `?`：表示其他情况（即该游戏中存在两个正确的游戏解，且其中一个解该方格是填上黑色，但在另一个解中该方格是填上白色）。

### 样例评测程序 评测程序将会按照下列格式读取输入数据： - 第一行：字符串 $s$， - 第二行：整数 $k$，随后有 $k$ 个整数 $c_0, \ldots, c_{k - 1}$。

无

### 样例一 `solve_puzzle("..........", [3, 4])` 以下是这次游戏的所有正确的解： - `XXX_XXXX__`， - `XXX__XXXX_`， - `XXX___XXXX`， - `_XXX_XXXX_`， - `_XXX__XXXX`， - `__XXX_XXXX`。 你可以观察到下标为 $2, 6,$ 和 $7$ (从 $0$ 开始) 的方格在所有正确的解中都是黑色，而其他的所有方格可能但不一定是黑色的。所以正确的答案应该是 `??X???XX??`。 ### 样例二 `solve_puzzle("........", [3, 4])` 在这个样例中，正确的填色方法只有一种，即 `XXX_XXXX`。 ### 样例三 `solve_puzzle("..._._....", [3])` 在这个样例中，我们可以推出方格 $4$ 一定是白色，为在白色的方格 $3$ 和方格 $5$ 之间根本不可能容纳 $3$ 个连续的方格，因此正确的答案应该是 `???___????`。 ### 样例四 `solve_puzzle(".X........", [3])` 只有两个正确解符合上述描述： - `XXX_______`， - `_XXX______`。 因此正确的答案应该是 `?XX?______`。 ### 子任务 在所有的子任务中，$1 \le k \le n, 1 \le c_i \le n$（对于每个 $0 \le i \le k - 1$）。 1. （$7$ 分）$n\le 20,k=1$，$s$ 只含有字符 `.`（即是空白的游戏行格）， 2. （$3$ 分）$n\le 20$，$s$ 只含有字符 `.`， 3. （$22$ 分）$n\le 100$，$s$ 只含有字符 `.`， 4. （$27$ 分）$n\le 20$，$s$ 只含有字符 `.` 及 `_`（只有关于填上了白色的方格信息）， 5. （$21$ 分）$n\le 100$， 6. （$10$ 分）$n\le 5\ 000,k\le 100$， 7. （$10$ 分）$n\le 200\ 000,k\le 100$，