#PQJ3493x17302. QOJ 3493_17302
QOJ 3493_17302
2026 联合省选 第一试摩卡串(string) 摩卡串(string) 【题目背景】 小摩卡是个天才,尤其在字符串理论方面有着异于常人的天赋。为了赞颂她的才华, 人们常常将那些满足特定优美性质的字符串命名为“摩卡串”。 【题目描述】 小H 有一个长度为n 的01 串s 和一个正整数k。他定义一个长度为m 的01 串 t = t1 . . . tm 为.摩.卡.串,当且仅当t 满足以下两个条件: • s 是t 的子串,即存在1 ≤l ≤r ≤m 使得s = tl . . . tr; • t 中.恰.好有k 个子串的字典序.严.格.小.于s。两个子串不同当且仅当两个子串的.长 .度不同或.位.置不同。形式化地,存在.恰.好k 对(l, r) 满足1 ≤l ≤r ≤m 且tl . . . tr 的字典序.严.格.小.于s。 由于符合条件的摩卡串可能有很多,小H 希望从中找出一个.长.度.最.短的摩卡串。你 需要帮助他找出其中任意一个。 【输入格式】 从文件string.in 中读入数据。 .本.题.包.含.多.组.测.试.数.据。 输入的第一行包含两个非负整数c, t,分别表示测试点编号与测试数据组数。c = 0 表示该测试点为样例。 接下来依次输入每组测试数据,对于每组测试数据: • 第一行包含两个正整数n, k。 • 第二行包含一个长度为n 的01 字符串s。 【输出格式】 输出到文件string.out 中。 对于每组数据,输出一行一个01 字符串,表示任意一个.长.度.最.短的摩卡串。特别 地,若不存在摩卡串,则输出Impossible。 【样例1 输入】 1 0 5 2 1 1 3 1 4 1 1 第6 页 共13 页
2026 联合省选 第一试摩卡串(string) 5 0 6 3 9 7 101 8 4 17 9 1100 10 4 20 11 1100 【样例1 输出】 1 10 2 Impossible 3 0101 4 011100 5 001100 【样例2】 见选手目录下的string/string2.in 与string/string2.ans。 该样例满足测试点4 ∼6 的约束条件。 【样例3】 见选手目录下的string/string3.in 与string/string3.ans。 该样例满足测试点7 ∼9 的约束条件。 【样例4】 见选手目录下的string/string4.in 与string/string4.ans。 该样例满足测试点10 ∼12 的约束条件。 【样例5】 见选手目录下的string/string5.in 与string/string5.ans。 该样例满足测试点13 ∼15 的约束条件。 第7 页 共13 页
2026 联合省选 第一试摩卡串(string) 【样例6】 见选手目录下的string/string6.in 与string/string6.ans。 该样例满足测试点16 ∼18 的约束条件。 【样例7】 见选手目录下的string/string7.in 与string/string7.ans。 该样例满足测试点19, 20 的约束条件。 【数据范围】 对于所有测试数据,均有: • 1 ≤t ≤5; • 1 ≤n ≤200,1 ≤k ≤3, 000; • 对于所有1 ≤i ≤n,均有si ∈{0, 1}。 测试点编号 n ≤ k ≤ 特殊性质 1 ∼3 15 200 A 4 ∼6 50 2, 000 B 7 ∼9 C 10 ∼12 D 13 ∼15 500 无 16 ∼18 150 2, 000 19, 20 200 3, 000 特殊性质A:若存在摩卡串,则存在长度不超过15 的摩卡串。 特殊性质B:对于所有1 ≤i ≤n,均有si = 0。 特殊性质C:对于所有1 ≤i ≤n,均有si = 1。 特殊性质D:存在正整数p ∈[1, n] 满足s1 = · · · = sp = 0 且sp+1 = · · · = sn = 1。 第8 页 共13 页