A16641. Deck of Cards
编程题
普及-
知识点
题目描述
Monocarp 有一副从 $1$ 到 $n$ 编号的牌。起初，这些牌按照从小到大的顺序排列，$1$ 在顶部，$n$ 在底部。
Monocarp 对这副牌进行了 $k$ 次操作。每次操作类型有三种：
- 移除顶部的牌；
- 移除底部的牌；
- 移除顶部或底部的任意一张牌。
你的任务是判断每张牌的状态：它现在是否仍在牌堆中，已经被移除，还是可能两种情况都有可能。
Monocarp 对这副牌进行了 $k$ 次操作。每次操作类型有三种：
- 移除顶部的牌；
- 移除底部的牌；
- 移除顶部或底部的任意一张牌。
你的任务是判断每张牌的状态：它现在是否仍在牌堆中，已经被移除，还是可能两种情况都有可能。
输入格式
第一行为一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2 \cdot 10^5$）。
第二行是一个长度为 $k$ 的字符串 $s$，由字符 $0$、$1$ 和/或 $2$ 组成。字符串 $s$ 描述了 Monocarp 的操作。如果第 $i$ 个字符是 $0$，第 $i$ 次操作移除顶部牌；如果是 $1$，则移除底部牌；如果是 $2$，可以移除顶部或底部的任意一张牌。
输入还保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。
每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2 \cdot 10^5$）。
第二行是一个长度为 $k$ 的字符串 $s$，由字符 $0$、$1$ 和/或 $2$ 组成。字符串 $s$ 描述了 Monocarp 的操作。如果第 $i$ 个字符是 $0$，第 $i$ 次操作移除顶部牌；如果是 $1$，则移除底部牌；如果是 $2$，可以移除顶部或底部的任意一张牌。
输入还保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。
输出格式
对于每个测试用例，输出一个长度为 $n$ 的字符串。第 $i$ 个字符如果该牌仍在牌堆中则为加号（+），如果已被移除则为减号（-），如果状态不确定则为问号（?）。
输入输出样例
输入 #1
4 4 2 01 3 2 22 1 1 2 7 5 01201
输出 #1
-++- ??? - --?+?--