CF1367D Task On The Board

Polycarp 在黑板上写下了一个只包含小写拉丁字母（'a'-'z'）的字符串 $s$。你已经知道了这个字符串，并且它会作为输入给出。 之后，他从字符串 $s$ 中擦除了一些字母，并将剩下的字母以任意顺序重新写在黑板上。最终，他得到了一个新的字符串 $t$。你需要根据一些额外的信息来找出这个字符串。 假设字符串 $t$ 的长度为 $m$，字符从左到右编号为 $1$ 到 $m$。你会得到一个长度为 $m$ 的整数序列：$b_1, b_2, \ldots, b_m$，其中 $b_i$ 表示所有满足 $t_j > t_i$ 的下标 $j$，从下标 $i$ 到这些下标 $j$ 的距离之和，即 $|i-j|$ 的总和（这里认为 'a' < 'b' < ... < 'z'）。换句话说，为了计算 $b_i$，Polycarp 会找到所有下标 $j$，使得 $t_j$ 所在的字母在字母表中比 $t_i$ 更靠后，并将所有 $|i-j|$ 的值相加。 例如，如果 $t = $ "abzb"，那么： - 因为 $t_1 = 'a'$，其余所有下标的字母都比 'a' 靠后，所以 $b_1 = |1-2| + |1-3| + |1-4| = 1 + 2 + 3 = 6$； - 因为 $t_2 = 'b'$，只有下标 $j=3$ 的字母比 'b' 靠后，所以 $b_2 = |2-3| = 1$； - 因为 $t_3 = 'z'$，没有任何下标 $j$ 满足 $t_j > t_3$，所以 $b_3 = 0$； - 因为 $t_4 = 'b'$，只有下标 $j=3$ 的字母比 'b' 靠后，所以 $b_4 = |4-3| = 1$。 因此，如果 $t = $ "abzb"，那么 $b = [6, 1, 0, 1]$。 给定字符串 $s$ 和数组 $b$，请找出任意一个满足以下两个条件的字符串 $t$： - $t$ 是从 $s$ 中擦除若干（可能为零）个字母后，将剩余字母重新排列得到的； - 按照上述规则从 $t$ 构造出的数组等于输入中的数组 $b$。

第一行包含一个整数 $q$（$1 \leq q \leq 100$），表示测试用例的数量。接下来有 $q$ 组测试用例。 每组测试用例包含三行： - 第一行是字符串 $s$，长度为 $1$ 到 $50$，只包含小写英文字母； - 第二行是一个正整数 $m$（$1 \leq m \leq |s|$），其中 $|s|$ 表示字符串 $s$ 的长度，$m$ 是数组 $b$ 的长度； - 第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$（$0 \leq b_i \leq 1225$）。 保证每组测试用例都存在解。

输出 $q$ 行，第 $k$ 行为第 $k$ 个测试用例的答案（字符串 $t$）。保证每个测试用例都存在解。如果有多种答案，输出任意一种均可。

在第一个测试用例中，满足条件的字符串 $t$ 有："aac"、"aab"。 在第二个测试用例中，满足条件的字符串 $t$ 有："a"、"b"、"c"。 在第三个测试用例中，只有字符串 $t = $ "aba" 满足条件，但字符 'b' 可以出现在第二或第三个位置。 由 ChatGPT 4.1 翻译