TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P5572
  • 問題
  • P5572「十二省联考 2019」字符串问题
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    問題説明

    题目背景

    Yazid 和 Tiffany 喜欢字符串问题。在这里,我们将给你介绍一些关于字符串的基本概念。

    对于一个字符串 \(S\), 我们定义 \(\lvert S\rvert\) 表示 \(S\) 的长度。

    接着,我们定义该串的子串 \(S\left( {L,R}\right)\) 表示由 \(S\) 中从左往右数,第 \(L\) 个字符到第 \(R\) 个字符依次连接形成的字符串,特别地,如果 \(L < 1\)\(R > \lvert S\rvert\)\(L > R\),则 \(S\left( {L,R}\right)\) 表示空串。

    我们说两个字符串相等,当且仅当它们的长度相等,且从左至右各位上的字符依次相同。

    我们说一个字符串 \(T\)\(S\)前缀,当且仅当 \(S\left( 1,\lvert T\rvert\right)=T\)

    两个字符串 \(S,T\) 相加 \(S+T\) 表示的是在 \(S\) 后紧挨着写下 \(T\) 得到的长度为 \(\lvert S\rvert+\lvert T\rvert\) 的字符串。

    题目描述

    现有一个字符串 \(S\)

    Tiffany 将从中划出 \(n_a\) 个子串作为 A 类串,第 \(i\) 个($1\leq i\leq n_a$)为 \(A_i = S\left( la_i, ra_i\right)\)

    类似地,Yazid 将划出 \(n_b\) 个子串作为 B 类串,第 \(i\) 个($1\leq i\leq n_b$)为 \(B_i = S\left( lb_i, rb_i\right)\)

    现额外给定 \(m\) 组支配关系,每组支配关系 \(\left( x,y\right)\) 描述了第 \(x\) 个 A 类串支配\(y\) 个 B 类串。

    求一个长度最大的目标串 \(T\),使得存在一个串 \(T\) 的分割 \(T=t_1 + t_2 +\dots +t_k\)\(k\geq 0\))满足:

    • 分割中的每个串 \(t_i\) 均为 A 类串:即存在一个与其相等的 A 类串,不妨假设其为 \(t_i = A_{id_i}\)
    • 对于分割中所有相邻的串 \(t_i , t_{i+1}\)($1\leq i < k$),都有存在一个 \(A_{id_i}\) 支配的 B 类串,使得该 B 类串为 \(t_{i+1}\) 的前缀。

    方便起见,你只需要输出这个最大的长度即可。

    特别地,如果存在无限长的目标串(即对于任意一个正整数 \(n\),都存在一个满足限制的长度超过 \(n\) 的串),请输出 \(-1\)

    入力形式

    从标准输入读入数据。

    单个测试点中包含多组数据,输入的第一行包含一个非负整数 \(T\) 表示数据组数。接下来依次描述每组数据,对于每组数据:

    • 第 $1$ 行一个只包含小写字母的字符串 \(S\)
    • 第 $2$ 行一个非负整数 \(n_a\),表示 A 类串的数目。接下来 \(n_a\) 行,每行 $2$ 个用空格隔开的整数。
      • 这部分中第 \(i\) 行的两个数分别为 \(la_i,ra_i\),描述第 \(i\) 个 A 类串。
      • 保证 $1\leq la_i\leq ra_i\leq \lvert S\rvert$。
    • 接下来一行一个非负整数 \(n_b\),表示 B 类串的数目。接下来 \(n_b\) 行,每行 $2$ 个用空格隔开的整数。
      • 这部分中第 \(i\) 行的两个数分别为 \(lb_i,rb_i\),描述第 \(i\) 个 B 类串。
      • 保证 $1\leq lb_i\leq rb_i\leq \lvert S\rvert$。
    • 接下来一行一个非负整数 \(m\),表示支配关系的组数。接下来 \(m\) 行,每行 $2$ 个用空格隔开的整数。
      • 这部分中每行的两个整数 \(x,y\),描述一对 \(\left( x,y\right)\) 的支配关系,具体意义见「题目描述」。
      • 保证 $1\leq x\leq n_a$,$1\leq y\leq n_b$。保证所有支配关系两两不同,即不存在两组支配关系的 \(x,y\) 相同。
    出力形式

    输出到标准输出。

    依次输出每组数据的答案,对于每组数据:

    • 一行一个整数表示最大串长。特别地,如果满足限制的串可以是无限长的,则请输出 \(-1\)
    サンプル入力

    3
    abaaaba
    2
    4 7
    1 3
    1
    3 4
    1
    2 1
    abaaaba
    2
    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

    サンプル出力

    7
    -1
    13

    ヒント
    \(n_a\) \(n_b\) \(\lvert S\rvert\) 测试点 \(m\) \(\lvert A_i\rvert \geq \lvert B_j\rvert\) 其他限制
    \(\leq 100\) \(\leq 100\) \(\leq 10^4\) $1$ \(\leq 10^4\) 保证 保证所有 \(\lvert A_i\rvert,\lvert B_j\rvert\leq 100\)
    \(\leq 1000\) \(\leq 1000\) \(\leq 2\times 10^5\) $2\sim 3$ \(\leq 2\times 10^5\) 保证
    \(=1\) \(\leq 2\times 10^5\) \(\leq 2\times 10^5\) $4$ \(=n_b\) 保证
    \(\leq 2\times 10^5\) \(\leq 2\times 10^5\) \(\leq 2\times 10^5\) $5\sim 6$ \(\leq 2\times 10^5\) 保证 保证所有 \(ra_i +1=la_{i+1}\)
    \(\leq 2\times 10^5\) \(\leq 2\times 10^5\) \(\leq 2\times 10^5\) $7\sim 8$ \(\leq 2\times 10^5\) 保证
    \(\leq 2\times 10^5\) \(\leq 2\times 10^5\) \(\leq 2\times 10^5\) $9\sim 10$ \(\leq 2\times 10^5\) 不保证

    为了方便你的阅读,我们把测试点编号放在了表格的中间,请你注意这一点。

    表格中的 \(\lvert A_i\rvert \ge \lvert B_j\rvert\) 指的是任意 B 类串的长度不超过任意 A 类串的长度。

    对于所有测试点,保证:\(T\leq 100\),且对于测试点内所有数据,\(\lvert S\rvert,n_a,n_b,m\)总和分别不会超过该测试点中对应单组数据的限制的 $10$ 倍。比如,对于第 1 组测试点,就有 \(\sum n_a\leq 10\times 100=1000\) 等。特别地,我们规定对于测试点 4,有 \(T\leq 10\)

    对于所有测试点中的每一组数据,保证:$1\leq \lvert S\rvert\leq 2\times 10^5$,\(n_a , n_b\leq 2\times 10^5\)\(m\leq 2\times 10^5\)

    提示

    十二省联考命题组温馨提醒您:

    数据千万条,清空第一条。

    多测不清空,爆零两行泪。