F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
大视野在线测评-欢迎您
[ New Thread ]
Problem 4650 >> 题面有误
Monster__Yi @ 2017-04-01 21:47:20
[ Quote ] [ Edit ] [ Delete ] 1#
建议去http://uoj.ac/problem/219查看原题
lavendir @ 2017-04-02 12:21:19
[ Quote ] [ Edit ] [ Delete ] 2#
已修正
stl @ 2017-04-02 21:16:54
[ Quote ] [ Edit ] [ Delete ] 3#
如果一个字符串可以被拆分为 AABB 的形式,其中 A 和 B 是任意非空字符串,则我们称该字符串的这种拆分是优秀的。
例如,对于字符串 aabaabaa,如果令 A=aab,B=a,我们就找到了这个字符串拆分成 AABB 的一种方式。
一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。比如我们令 A=a,B=baa,也可以用 AABB 表示出上述字符串;但是,字符串 abaabaa 就没有优秀的拆分。
现在给出一个长度为 n 的字符串 S,我们需要求出,在它所有子串的所有拆分方式中,优秀拆分的总个数。这里的子串是指字符串中连续的一段。
以下事项需要注意:
出现在不同位置的相同子串,我们认为是不同的子串,它们的优秀拆分均会被记入答案。
在一个拆分中,允许出现 A=B。例如 cccc 存在拆分 A=B=c。
字符串本身也是它的一个子串。

Input
每个输入文件包含多组数据。输入文件的第一行只有一个整数 T,表示数据的组数。保证 1≤T≤10。
接下来 T 行,每行包含一个仅由英文小写字母构成的字符串 S,意义如题所述。

Output
输出 T 行,每行包含一个整数,表示字符串 S 所有子串的所有拆分中,总共有多少个是优秀的拆分。

Hint
我们用 S[i,j] 表示字符串 S 第 i 个字符到第 j 个字符的子串(从 1 开始计数)。
第一组数据中,共有 3 个子串存在优秀的拆分:
S[1,4]=aabb,优秀的拆分为 A=a,B=b;
S[3,6]=bbbb,优秀的拆分为 A=b,B=b;
S[1,6]=aabbbb,优秀的拆分为 A=a,B=bb。
而剩下的子串不存在优秀的拆分,所以第一组数据的答案是 3。
第二组数据中,有两类,总共 4 个子串存在优秀的拆分:
对于子串 S[1,4]=S[2,5]=S[3,6]=cccc,它们优秀的拆分相同,均为 A=c,B=c,但由于这些子串位置不同,因此要计算 3 次;
对于子串 S[1,6]=cccccc,它优秀的拆分有 2 种:A=c,B=cc 和 A=cc,B=c,它们是相同子串的不同拆分,也都要计入答案。
所以第二组数据的答案是 3+2=5。
第三组数据中,S[1,8] 和 S[4,11] 各有 2 种优秀的拆分,其中 S[1,8] 是问题描述中的例子,所以答案是 2+2=4。
第四组数据中,S[1,4],S[6,11],S[7,12],S[2,11],S[1,8] 各有 1 种优秀的拆分,S[3,14] 有 2 种优秀的拆分,所以答案是 5+2=7。
1≤T≤10,1≤n≤30000。
nzhtl1477 @ 2017-04-02 22:46:17
[ Quote ] [ Edit ] [ Delete ] 4#
大头日
ZYQN @ 2017-04-12 08:16:42
[ Quote ] [ Edit ] [ Delete ] 5#
题面还是有问题,什么"AABBAABB" ,一看就是复制mathjax渲染的东西时出了偏差
还是去UOJ看吧,BZOJ这个格式吃枣药丸
zhouzhendong @ 2018-05-10 19:43:12
[ Quote ] [ Edit ] [ Delete ] 6#
希望修正题面
Stargazer @ 2019-07-14 18:41:32
[ Quote ] [ Edit ] [ Delete ] 7#
贴的毫不用心呵呵呵
[Top] [Previous Page] [Next Page]

HOME Back