「ROI 2021 Day1」复兴家园

ID: 2242

传统题

1000ms

256MiB

难度: (无)

上传者:

标签>

ROI

2021

题目描述

译自 ROI 2021 Day1 T2. Родные просторы

你正在玩一款叫做《复兴家园》的手机游戏，游戏中管家奥斯塔普帮助地主修复祖宅。游戏的玩法如下：

给定一列长度为 $n$ 的水晶，从左到右排列。每个水晶属于 $k$ 种类型之一，用前 $k$ 个英文字母表示。因此，水晶序列可以表示为一个由英文字母组成的字符串。

每次游戏操作可以删除序列中的一个水晶。玩家的目标是通过合法的删除操作，得到字典序最小的字符串。

合法的删除操作由一个大小为 $k \times k$ 的矩阵 $A$ 给出，矩阵中的元素为 $0$ 或 $1$ 。如果 $A_{ij} = 1$ ，则可以删除类型为 $j$ 的水晶，前提是它左边紧挨着一个类型为 $i$ 的水晶。这些操作可以按任意顺序执行。

第一行包含两个整数 $k,n\ (1 \le k \le 26, 1 \le n \le 5\cdot 10^5)$ ，分别表示水晶的种类数和初始序列的长度。

接下来的 $k$ 行中，每行包含 $k$ 个字符 $0$ 或 $1$ ，表示矩阵 $A$ 。第 $i$ 行第 $j$ 列的字符表示 $A_{ij}$ 。

最后一行包含一个长度为 $n$ 的字符串，表示初始的水晶序列。保证字符串中只包含前 $k$ 个英文字母。

输出通过合法的删除操作可以得到的字典序最小的字符串。

3 7
010
001
100
abacaba

aac

在样例中，合法的删除操作如下（删除的字符用删除线表示，前一个字符用下划线表示）：

第一个样例中的可能删除顺序：

3 5
010
001
100
bcacb

bacb

第二个样例中的可能删除顺序：

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

子任务	分值	$n$ 的限制	$k$ 的限制	子任务依赖
$1$	$10$	$n \le 20$	$k \le 26$	$0$
$2$	$12$	$n \le 50$	$k \le 5$	$0$
$3$	$16$	$n \le 300$	$k \le 5$	$0, 2$
$4$	$17$	$n \le 500$	$k \le 26$	$0, 1\sim 3$
$5$	$10$	$n \le 2000$		$0, 1\sim 4$
$6$	$9$	$n \le 10^4$		$0, 1\sim 5$
$7$	$8$	$n \le 10^5$		$0, 1\sim 6$
$8$	$11$	$n \le 5\cdot 10^5$	$k \le 2$
$9$	$7$	$n \le 5\cdot 10^5$	$k \le 26$	$0, 1\sim 8$