seuOJ366 - 覆盖

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：512 MiB
• 题目标签：冬季, 校赛, 初赛, 2021

题目描述

你有一个01串，你可以选择 $m$ 个长度为 $k$ 的区间进行覆盖，并且要求每一个这样的区间中出现了至少 $p$ 个 1 。

你选择的两个区间可以重叠。如果可供选择的区间不足 $m$ 个，那么这些区间都会被选择；如果可供选择的区间大于等于 $m$ 个，那么 一定 要选择 $m$ 个区间。

求在所有可能的选择情况中，哪些点一定被覆盖，哪些点不一定被覆盖。

输入格式

第一行一个正整数 $T$ 表示数据组数。

每组数据有两行：

第一行三个正整数 $n,m,k,p$，其中 $n$ 为字符串长度，$m,k,p$ 意义如题目描述。

然后一行一个长度为 $n$ 的01串。

输出格式

每组数据输出一行一个长度为 $n$ 的字符串，仅由 ?,-,+ 组成，表示

1. - 这个位置一定不被覆盖。
2. + 这个位置一定被覆盖。
3. ? 无法确定。

样例

样例输入

3
8 100 2 1
00011000
8 2 3 2
10100110
12 3 4 3
011101011000

样例输出

--++++--
???-?++?
?+++++???---

样例解释

对于第一个样例，包含 1 的数量大于等于 p=1 的长度为 k=2 区间有 [3,4],[4,5],[5,6] ,共 3 个，远不足 m=100 个。
所以这 3 个区间都会被选择，从而覆盖了 [3,6] 内所有的点，其余点都不会被覆盖。

数据范围与提示

$T\leq 100,1\leq n\leq 1000,m,k,p\leq n$。

赛后补充：@josh00 注意到，样例中第一条数据不满足 $m\leq n$，这是一个错误；但测试数据中不存在这样的数据。