#PQJ401x2996. QOJ 401_2996
QOJ 401_2996
2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第一试字符串问题(string) 字符串问题(string) 【题目背景】 Yazid 和Tiffany 喜欢字符串问题。在这里,我们将给你介绍一些关于字符串的基 本概念。 对于一个字符串S ,我们定义|S | 表示S 的长度。 接着,我们定义该串的子串S (L, R) 表示由S 中从左往右数,第L 个字符到第R 个字符依次连接形成的字符串,特别地,如果L < 1 或R > |S | 或L > R,则S (L, R) 表 示空串。 我们说两个字符串相等,当且仅当它们的长度相等,且从左至右各位上的字符依次 相同。 我们说一个字符串T 是S 的.前.缀,当且仅当S (1, |T|) = T。 两个字符串S, T 相加S + T 表示的是在S 后紧挨着写下T 得到的长度为|S | + |T| 的字符串。 【题目描述】 现有一个字符串S 。 Tiffany 将从中划出na 个子串作为A 类串,第i 个(1 ≤i ≤na)为Ai = S (lai, rai)。 类似地,Yazid 将划出nb 个子串作为B 类串,第i 个(1 ≤i ≤nb)为Bi = S (lbi, rbi)。 现额外给定m 组支配关系,每组支配关系(x, y) 描述了第x 个A 类串.支.配第y 个 B 类串。 求一个.长.度.最.大的目标串T,使得存在一个串T 的分割T = t1 +t2 +· · ·+tk(k ≥0) 满足: • 分割中的每个串ti 均为A 类串:即存在一个与其相等的A 类串,不妨假设其为 ti = Aidi。 • 对于分割中所有相邻的串ti, ti+1(1 ≤i < k),都有存在一个Aidi 支配的B 类串, 使得该B 类串为ti+1 的前缀。 方便起见,你只需要输出这个最大的长度即可。 特别地,如果存在无限长的目标串(即对于任意一个正整数n,都存在一个满足限 制的长度超过n 的串),请输出−1。 【输入格式】 从文件string.in 中读入数据。 单个测试点中包含多组数据,输入的第一行包含一个非负整数T 表示数据组数。 接下来依次描述每组数据,对于每组数据: 第4 页 共9 页
2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第一试字符串问题(string) • 第1 行一个只包含小写字母的字符串S 。 • 第2 行一个非负整数na,表示A 类串的数目。接下来na 行,每行2 个用空格 隔开的整数。 – 这部分中第i 行的两个数分别为lai, rai,描述第i 个A 类串。 – 保证1 ≤lai ≤rai ≤|S |。 • 接下来一行一个非负整数nb,表示B 类串的数目。接下来nb 行,每行2 个用空 格隔开的整数。 – 这部分中第i 行的两个数分别为lbi, rbi,描述第i 个B 类串。 – 保证1 ≤lbi ≤rbi ≤|S |。 • 接下来一行一个非负整数m,表示支配关系的组数。接下来m 行,每行2 个用 空格隔开的整数。 – 这部分中每行的两个整数x, y,描述一对(x, y) 的支配关系,具体意义见 【题目描述】。 – 保证1 ≤x ≤na,1 ≤y ≤nb。保证所有支配关系两两不同,即不存在两组支 配关系的x, y .均相同。 【输出格式】 输出到文件string.out 中。 依次输出每组数据的答案,对于每组数据: • 一行一个整数表示最大串长。特别地,如果满足限制的串可以是无限长的,则请 输出−1。 【样例1 输入】 3 abaaaba 2 4 7 1 3 1 3 4 1 2 1 abaaaba 2 第5 页 共9 页
2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第一试字符串问题(string) 4 7 1 3 1 7 7 1 2 1 abbaabbaab 4 1 5 4 7 6 9 8 10 3 1 6 10 10 4 6 5 1 2 1 3 2 1 3 3 4 1 【样例1 输出】 7 -1 13 【样例1 解释】 对于第1 组数据,A 类串有aaba 与aba,B 类串有aa,且A2 支配B1。我们可 以找到串abaaaba,它可以拆分成A2 + A1,且A1 包含由A2 所支配的B1 作为前缀。 可以证明不存在长度更大的满足限制的串。 对于第2 组数据,与第1 组数据唯一不同的是,唯一的B 类串为a。容易证明存 在无限长的满足限制的串。 对于第3 组数据,容易证明abbaabbaaaabb 是最长的满足限制的串。 第6 页 共9 页
2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第一试字符串问题(string) 【样例2】 见选手目录下的string/string2.in 与string/string2.ans。 【样例3】 见选手目录下的string/string3.in 与string/string3.ans。 【样例3 解释】 这个测试点满足【子任务】中提到的|Ai| ≥|Bj| 的限制。 【子任务】 na nb |S | 测试点 m |Ai| ≥|Bj| 其他限制 ≤100 ≤100 ≤104 1 ≤104 保证 保证所有|Ai|, |Bj| ≤100 ≤1000 ≤1000 ≤2 × 105 2∼3 ≤2 × 105 无 = 1 ≤2 × 105 4 = nb ≤2 × 105 5∼6 ≤2 × 105 保证所有rai + 1 = lai+1 7∼8 无 9∼10 不保证 为了方便你的阅读,我们把.测.试.点.编.号放在了表格的中间,请你注意这一点。 表格中的|Ai| ≥|Bj| 指的是.任.意B 类串的长度不超过.任.意A 类串的长度。 对于所有测试点,保证:T ≤100,且对于测试点内所有数据,|S |, na, nb, m 的.总.和 分别不会超过.该.测.试.点.中.对.应的.单.组.数.据.的.限.制的10 倍。比如,对于第1 组测试点, 就有∑na ≤10 × 100 = 1000 等。特别地,我们规定对于测试点4,有T ≤10。 对于所有测试点中的每一组数据,保证:1 ≤|S | ≤2×105,na, nb ≤2×105,m ≤2×105 【提示】 十二省联考命题组温馨提醒您: .数.据.千.万.条,.清.空.第.一.条。 .多.测.不.清.空,.爆.零.两.行.泪。 第7 页 共9 页