4334. [省选联考 2026] 摩卡串

【题目背景】

小摩卡是个天才，尤其在字符串理论方面有着异于常人的天赋。为了赞颂她的才华，人们常常将那些满足特定优美性质的字符串命名为“摩卡串”。

【题目描述】

小 H 有一个长度为 $n$ 的 01 串 $s$ 和一个正整数 $k$。他定义一个长度为 $m$ 的 01 串 $t = t_1 \dots t_m$ 为摩卡串，当且仅当 $t$ 满足以下两个条件：

• $s$ 是 $t$ 的子串，即存在 $1 \le l \le r \le m$ 使得 $s = t_l \dots t_r$；
• $t$ 中恰好有 $k$ 个子串的字典序严格小于 $s$。两个子串不同当且仅当两个子串的长度不同或位置不同。形式化地，存在恰好 $k$ 对 $(l, r)$ 满足 $1 \le l \le r \le m$ 且 $t_l \dots t_r$ 的字典序严格小于 $s$。

【输入格式】

本题包含多组测试数据。
输入的第一行包含两个非负整数 $c, t$，分别表示测试点编号与测试数据组数。$c = 0$ 表示该测试点为样例。
接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含两个正整数 $n, k$。
• 第二行包含一个长度为 $n$ 的 01 字符串 $s$。

【输出格式】

对于每组数据，输出一行一个 01 字符串，表示任意一个长度最短的摩卡串。特别地，若不存在摩卡串，则输出 `Impossible`。

【样例输入】

0 5
1 1
1
1 1
0
3 9
101
4 17
1100
4 20
1100

【样例输出】

10
Impossible
0101
011100
001100

【样例说明】

【样例 2】
见选手目录下的 string/string2.in 与 string/string2.ans。
该样例满足测试点 $4 \sim 6$ 的约束条件。
【样例 3】
见选手目录下的 string/string3.in 与 string/string3.ans。
该样例满足测试点 $7 \sim 9$ 的约束条件。
【样例 4】
见选手目录下的 string/string4.in 与 string/string4.ans。
该样例满足测试点 $10 \sim 12$ 的约束条件。
【样例 5】
见选手目录下的 string/string5.in 与 string/string5.ans。
该样例满足测试点 $13 \sim 15$ 的约束条件。
【样例 6】
见选手目录下的 string/string6.in 与 string/string6.ans。
该样例满足测试点 $16 \sim 18$ 的约束条件。
【样例 7】
见选手目录下的 string/string7.in 与 string/string7.ans。
该样例满足测试点 $19, 20$ 的约束条件。

【数据规模与约定】

对于所有测试数据，均有：

• $1 \le t \le 5$；
• $1 \le n \le 200$，$1 \le k \le 3,000$；
• 对于所有 $1 \le i \le n$，均有 $s_i \in \{0, 1\}$。

【来源】

省选联考 2026 Day1 T2

样例下载