UOJ238 【IOI2016】paint 题解

题目链接：#238. 【IOI2016】paint

题意：

按数目填色是个有名的智力游戏。我们现在考虑的是这个游戏的一维版本。在这个游戏中，玩家会有一行个方格。这些方格从左到右分别编号为至。玩家必须要为这些方格填上黑色或白色，我们用 X 代表填上黑色的方格并用 _ 来代表填上白色的方格。

系统将会给玩家一个提示，这个提示是一个含有个正整数的序列。而玩家必须要根据提示为方格填色，填色的要求是在这行上，填上黑色的方格必须组成个连续的区间，而且，在由左开始的第 (由开始) 个区间上必须含有个黑色方格。例如，若提示为，则该游戏的正确填色方法是必须含有两个由连续黑色格位组成的区间，这两个区间的长度分别是和。因此，若且的话，则满足提示的一个正确的填色方法是 _XXX__XXXX。要注意的是 XXXX_XXX__ 并不满足提示，因为黑色的区间的长度顺序不正确。同时 __XXXXXXX_ 也不满足提示，因为它只含有一个黑色区间而非两个分开的黑色区间。

你将获得一个部分方格已填好颜色的游戏行格，即，你知道及的值，并且你也知道有些方格一定是黑色和有些方格一定是白色。你的工作是从中推算出更详细的方格的信息。

更加详细来说，一个正确的游戏解应该满足提示，并且和已经知道颜色的方格的颜色一致。你的程序必须找出在所有正确的游戏解中都会填上黑色的方格和在所有正确的游戏解中都会填上白色的方格。

你可以假设每个输入一定存在至少一个正确的游戏解。

实现细节：

你必须编写程序以实现以下的函数（或方法）：

std::string solve_puzzle(std::string s, std::vector<int> c)，

s: 一个含有个字符的字符串。而对于每个 ()，字符将会是以下其中一个：

X, 表示方格必须要填上黑色，

_, 表示方格必须要填上白色，

., 表示方格没有任何信息。

c: 是一个长度为的数组，它的内容是上面叙述中所讲的提示，

这函数必须要返回一个长度为的数组。对于每个 () 而言，输出字符串的第个字符应该是以下其中一个：

X, 表示在所有游戏解中，第个方格都是填上黑色，

_, 表示在所有游戏解中，第个方格都是填上白色，

?, 表示其他情况（即该游戏中存在两个正确的游戏解，且其中一个解该方格是填上黑色，但在另一个解中该方格是填上白色）。

数据范围：

$1\le n \le 2\times 10^5,1 \le k \le 100$ 。

设 $f(i,j)$ 表示方格 $i$ 为白色且后缀 $[i+1,n]$ 满足 $c_j,c_{j+1},\cdots,c_{k-1}$ 是否可能。

记 $t$ 为答案串，当 $s_i \ne \mathtt{X}$ 时

若 $t_{i+1}$ 为白，则 $f(i,j) \gets f(i+1,j)$ 。
若 $t_{i+1}$ 不为白，此时 $[i+1,i+c_j]$ 即为 $c_j$ 对应的段，显然 $t_{i+c_j+1}$ 为白，则
$f(i,j) \gets f(i + c_j + 1, j + 1)$

（第二行这个东西的判断可以通过对字符串的黑白做前缀和。）

接着设 $g(i,j)$ 表示 $i$ 为白色，前缀 $[1,i-1]$ 满足 $c_0,\cdots,c_{j-1}$ ，后缀 $[i+1,n]$ 满足 $c_j,\cdots,c_{k-1}$ 是否可能。

当 $s_i \ne \mathtt{X}$ 且 $f(i,j)=\mathrm{True}$ 时

若 $t_{i-1}$ 为白，则 $g(i,j) \gets g(i-1,j)$ 。
若 $t_{i-1}$ 不为白，即 $[i-c_j,i-1]$ 不为白且 $t_{i-c_j-1}$ 为白，则
$g(i,j) \gets g(i - c_j-1, j-1)$

不过到目前为止我们只dp了为白的情况，还没有考虑黑的情况。

黑的情况其实很简单，我们只要把 $g$ 的第二种转移中黑的地方标记出来即可（区间加用差分）

时间复杂度 $\mathcal{O}(nk)$

代码：

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))
#define M ((int)(115))

const char ch[] = {'X', '!', '?', '_'};

char S[N];
int b[N], can_fill[N];
bool pre[N][M], suf[N][M], can_blank[N];

void Modify(int l, int r) { ++can_fill[l]; --can_fill[r]; }

string solve_puzzle(string s, vector<int> c)
{
    int n = s.size(), m = c.size(); memcpy(S + 1, s.c_str(), n);
    for(int i = 1; i <= n; i++) b[i] = b[i - 1] + (S[i] == '_');
    pre[0][0] = suf[n + 1][m] = true;
    for(int i = n, j; ~i; i--)if(S[i] != 'X')
        for(memcpy(suf[i], suf[i + 1], m + 1), j = 0; j < m; j++)
            suf[i][j] |= i + c[j] <= n && suf[i + c[j] + 1][j + 1] && b[i] == b[i + c[j]];
    for(int i = 1; i <= n + 1; i++) if(S[i] != 'X')
        for(int j = 0, k; j <= m; j++) if(suf[i][j])
        {
            if(pre[i - 1][j]) can_blank[i] = pre[i][j] = true;
            if(j && (k = i - c[j - 1]) > 0 && pre[k - 1][j - 1] && b[i - 1] == b[k - 1]) {
                can_blank[i] = pre[i][j] = true, Modify(k, i);
            }
        }
    string res;
    for(int i = 1; i <= n; i++) can_fill[i] += can_fill[i - 1];
    for(int i = 1; i <= n; i++) 
        res.push_back(ch[(can_blank[i] << 1) | !can_fill[i]]);
    return res;
}