#1850. 研心
研心
研心
题目描述
标题: 研心 - Problem - QOJ.ac
#9514. 研心
The problem was used in the following contests:
题目背景
当你看向镜子时,是否会注意到自己背后的事物?我相信大部分人的关注点应该在自己的虚像上。
现在想象一面镜子,你能在镜子中看到自己所有可能的现状或未来,也许某个自己和你的朋友过着差不多的生活。你会在镜子中找到一个向往的自我,也许那是现在的自己,或者是更好的自己。但就如镜中的背景,也有很多的可能性是,其他的自我没有那么幸运,过的更普通,更辛苦。但不变的是,所有的可能性就是你自己。你从最开始便有着一双将可能性化为现实的翅膀。
不要忽略镜中的每一处细节,当你打碎这面镜子时,你会得到一双完整的翅膀。解开一切的束缚,蹬离地面,展翅高飞吧。
题目描述
给定大小为 n 的字符串序列 S 和大小为 m 的字符串序列 T,其中 S 的第 i 个字符串为 Si,T 的第 j 个字符串为 Tj。
定义一个字符串的权值 f(s) 为 s 中最长奇回文子串的半径长度。例如 aba 的半径长度为 2,ababa 的半径长度为 3。
定义两个字符串的加法 s+t 为把两个字符串拼接起来得到的新字符串。
求 ∑i=1n∑j=1mf(Si+Tj)。
样例输入输出
样例输入
3 3
a
aba
aaba
b
ba
ab
样例输出
19
样例解释
回文半径长度 T1 T2 T3 S1 1 2 1 S2 2 3 2 S3 2 3 3
数据范围
令 s=max(∑|Si|,∑|Ti|)。
本题共有 4 个子任务,只有通过子任务中所有数据才能获得所有分数。
子任务编号 分数 特殊条件 1 20 s≤5000 2 30 n=1 3 20 保证所有字符在 {a,b} 中随机 4 30 依赖子任务 1, 2, 3
对于 100% 的数据,满足 1≤n,m,s≤4×105,保证输入的字符串只包含小写字母。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
300 300
ccc
bbbcacabbcba
aaabaccb
aaabccbccbaaabbc
cabbaccabcbab
acaacbab
babaccacabbccb
bbbcbccbaacacbbaa
abcc
baabbacbacbbcacc
abbbbaccc
bcabbcbbababbccbaacaabcbababbbabba
cbbcaac
abcabbcbcbcabcaaa
bacc
bbcabbabbcaacacbbbcbbacbbb
aacbbabcabcbbbaacbbbbababaaccbacaccccac
aaaacababcc
ccbbbacbcbcbccccc
cacbbacbacbbbbab
abbcc
bbabccaaccc
bbaca
b
bbbc
b
aaa
c
ccaba
ab
bbaca
cccab
caaaaacbcbcaccbccbaba
accaacacaaccccbccccc
bcbcabccacbab
c
aacacbabcc
bcb
cbaaba
ab
bccbcbab
abcabcacc
cbcc
aa
acabcacbbbacabcabccbbcbab
cbbcccacaccca
abb
acacacacccacaaaaabcbbcbbcbcabacbc
acababcababbabcbbaabccbacaacbccb
ccbabbabbbcbbabaabccabcb
accccacaaccaa
cb
ccaccababbaaacbcbacbcba
acbccbacab
bbcaccaacbcacac
cbcbccbcacb
bbacc
bbbbba
b
bbcbbbbbacbca
aacaccbbba
accc
bcabcbbacabaaabbccc
acbaccaccb
babcbbb
bbabba
bcabcabaccbcbba
babcbbaabb
cbbbbca
aabcabba
c
caacacacbaabbabbaababccacaa
aacbbcbbbbbbc
cbaaaacaaaaaaccbaacccbaccaaabcaccabcacccb
bcaacbabcacaacbbcbbacaacbccbbaaccabccb
cacaacbabccaccca
cccccbccba
bacccbabcccaacaaba
aaaab
bacaacbb
cc
aaa
caabcbbca
acbcaccb
acccabaabbbccaaaacbaacbcaabb
baacc
c
aaab
bcaccabccaaabaaaabcc
ab
bbabcacbbac
ccaaaaa
abac
ccbaac
bcbccbabbbcbbcbbabaaaaacaaccabc
ba
bbabc
bcbaabbbcabcaaabbcbbccababcbc
bccabaccbabacbabcbbcabaa
caacbcbacaaabaaccabcababbcabaabccabaa
bcacbcbcabaccac
ca
ba
caacbba
cbb
cbabacbcaacaabaaabababccbbcac
b
bacaabcabbb
ccabaaabaccaca
abbcbcabcabca
cbaccabc
baacabbabb
ccbb
a
b
abbbcbc
bcbcaaaaaabbabbcbbbcaaaccabcbacbabba
baacbcbccaaabcbc
bcbc
abbacbcbbacbcccccaca
ccabbccbbaa
a
acbcaab
bcbcaaaabca
acacbccaccc
cbcaacca
cacaacbccab
b
ccabbbbcabbcaaba
ccaacaaaabacaacbb
a
cabcbcbaabaabcaccacc
bbbc
baccbcbbacccaacccccccccac
bcbcbabcb
aabab
c
abbcba
bcbcb
aacb
b
cccc
ccaaabbbacaaaabbabab
bcabbbca
cababcccccaccbbacccaaac
cba
bcbcaccbbabbbbabbbaacbaccc
baacacaaacbbcbc
ccaca
cacacb
cbab
ccaaba
abcb
abbccbc
baaacaabaac
bbbaccabaaabb
ccaaccbca
cacbcacbccac
cbbacbaacbcaababcbca
caabcaba
cacccabbaac
baaabbcbabbcaabaaacbcab
babcbcabccaccbab
aacccbbacacccccbcacaa
c
b
aabc
cbababccacccbb
acaccbbaccaaca
bcabcabacbacaa
bc
cbccbaaabcbabba
ba
abb
bbabaaa
ab
ac
acaaa
baba
abaaccaccbaccbbcc
cb
bbcbc
ab
abccbaacc
bb
abab
baabcbacabbb
bcaccc
cccbaccbb
baaacabbcbaaabbabccbbbcbbbacaa
caaacc
bbcabababbacbcabacbbbb
cab
cbaca
caccac
ccabbaccaccaa
accbaacbbbacac
abc
cc
bc
bbaccaaccabaacacbbabaccabb
b
a
c
aabcc
cba
cbacccaaabaabbacaaaabbbaabbccbabbbba
bcccabacbacabbbccb
bc
b
bbbbccbbcacbb
aabaabccacbacbbb
bacacccaccbbcacabcccacccc
bbca
acaaabbaabab
cacbcabbbb
aa
cb
bbcaaaaacabbabbbba
acbcbbbcbbaccaababcabaaccaacccc
abcc
bac
acccca
bbabbacbc
acacaabaaa
c
abcbacccbcabbcbacbbacac
c
aacaba
abcc
accacabbbbaaacaaaa
acb
aacccbacbbbc
bbcabbbcb
cc
cbbbacabaaabababbcabccaabbbbaabccc
aaaccbcaa
cba
cacacbccbb
bbcaccaabba
bcbac
bacccc
abbcbababcbbbbacacb
bccabbbb
bcaccabc
bccc
aaaacccabcaaacacbabcaa
babaabacbbcababcccccaa
bacaabaccacbcbabacbbbcabcbac
ccaaacbbacbcaaabbcbccacbacca
cbcbababbbacbbcabccc
bbb
babca
ababaccaab
cab
cbbaaabaacacabbc
bacba
aaacaaccbc
cbcbcbca
ca
ccb
bbcababbbcba
c
bbabbbcababbbaacbabbba
bcbaaa
a
aabaacababbaa
aaaccbaa
cbacbaabbb
bcb
cb
ca
b
bcca
c
ac
cbbbcaccaaacbcacbbcaaaacabbbbc
aa
caccbbbccccbbaabccbbbc
accbbcac
cbabbcaaa
bcba
bb
aca
abcacacbbaacbcab
cb
bac
babaaacbbcbabcccab
ac
ab
b
aaca
bcaacacbaacbbbbba
aabca
ba
acbacca
baab
bcc
acccb
accbb
baa
baabccbabcab
cabbbacb
caaacaabababaaaa
abbbbcabbcbca
cccaccaa
acbbbababaaacc
ccbacbcacbccbaaac
caca
cacaabcabccbcabb
cccbccaac
baacbcabacabccccabcababaaaabcbbabb
aacabca
accabcbaacabbbbaa
abba
bccbaaabcbabccbbcbbabcabbc
bcccbcabaccbcbcbbcbcbcabcacccccbcccbabb
aaccbbbbcca
ababbbbcccabcacaa
ccbcbacbbaaacbac
cccca
aaaccbbacac
bccca
c
abab
a
ccc
c
cabbc
ca
bacba
accaa
ababbcabbccccaaaaacca
ccbaaababccabbbaabac
cacaccccbbbca
b
ccaabbaacc
acb
bbaaca
bb
cabaabca
bbbbaacba
cacc
ab
abcbabcccaacacabcacacbcac
cbcbcccbbabbc
cba
abaaacbccbcccaaababcbbbccabcbccbc
cacbbcbccbacbcacccbbbbbccaaabcac
bcbbabcabbcaccabbccbcaca
acacbccbabccb
aa
bcbbccbaaacccaaccccccac
bbaabaaacc
bbcbbaabccbbabc
cccaccbcbbb
bbbcb
bccacb
a
bbbabbbcaccab
bccbcbbbbc
cbab
bbbaabcbacbbbacbaab
caaaccbcaa
cabbaac
bbcaba
abcbabacbbbcbcb
bbaacbccbc
cbbbcca
bbbbaaaa
c
acacacbcababbaccacacaaacccb
ccbabacbbccca
ccabaabacccaaabcbcbccaccbccacbccacaccaacc
abbccbaacccbaaccabaacbaaaccbbaabcbacac
abaaacbccccbcaac
bbaabacabb
acbacabbacaababccb
cabaa
aacbccab
bb
cbc
cabacacca
bcaaacab
abcaaabcacabbbccababcacbcbbc
cabbb
b
acac
acacbcabccaabcaccbbb
cb
bcccbcbacaa
aaabacc
cbcb
ababcc
abcccbcccbcabaaaacacbcccacaabcc
ab
babbb
bbcaaabcababaacbaabccbabcbacb
bcbbbacaababacaacaccacba
aaaaacbabcbcacabccbccaabacbacabaccbca
bcccabaaabbbcca
cc
ba
ccbcabb
ccb
abcbabaaacbcacaabcbcaaacacccc
c
bbbabbabcaa
abccbbcbbababb
aaaacbaccabca
abbcaccc
bbcbbbacab
bccb
a
c
aabccbb
acabbacbcacabacacacabbaacabbcabcabcc
abbabccbbcbabccc
aabb
bbbcacccbacbbabbbcbb
bacbaabacbb
c
babcccc
abccbcaaccc
bbacbabcccb
bcaaabaa
ccabccacbac
b
ccbbbcaccbccbcca
cacbccacbabccbacb
a
cabbccbccbbbbcbaabcb
bbca
bcbbcbabacbcbaccacbccbaba
bacbbbbbc
abcaa
b
accccc
bcbba
caac
a
cbaa
cabaaabcccaabccbcbac
acacccbb
cacacacabcbcbacbcbbabbc
abb
cabbabbaabaabccbbabbbcbaab
aabaaacbaacaabc
cccbb
bbaaca
abcc
cbcaab
abaa
aacabcc
abbbbbabbbc
ccbacaccabcac
ababbccab
bccbcababbcc
bccacabbbbbbacacbacb
cccbabcb
acaaaaacbba
ccacccaacbacbaccbabbabc
acccabbcccbacbbb
abaabacabaccaaccbccac
b
c
bcab
caabacbcbbaccc
baccbbbacbcbab
bccbbacaabbbbb
aa
cbccaacabbbaaaa
ca
caa
aaabbbb
cc
ca
abcba
acaa
cbbcccacbbbaabbbb
ab
cabcb
ca
bccacccac
bb
bccc
ccbbaccbcbcc
cbbaca
abcacabbc
cabcbacaabacaaabbaaabaccabbbbb
bbcbac
acbcaacbabbacbcacabcbb
bcc
baabb
bbcaac
baccbacccabba
baccbccababcca
ccb
aa
aa
bcabbacaacbbababcaaaaabbac
a
a
a
aaacb
cba
cbbbcbaaaabccccbcabcaabccacbbccbaaca
ccacbcbcccbabbbcab
bc
c
bcbcccbcbacba
cbbabcaaabbabcbb
bbcbaccabcabbcabaacaacccb
ccbb
baccbaccacba
bababbbaab
ac
ac
bcaaaaabaacabbbccc
ccccaaaacbcabcccaabccbbbabbcabb
cccc
bcc
ccaacb
babcbbbaa
bacbabbbcb
c
cbbbbbccacaacabbbababba
a
cbbbca
bcbb
cccbabcabaccacccba
acc
bbacbbcaacac
aaabaabcc
ab
bbbababbbaaccabcbaabacaaababcbcabc
ccbbaacab
aac
acaaabacaa
cccacbabacc
bcbac
bbbcbc
bbccbcaaaaacbbacbaa
abbabbba
acaaabcc
cacc
cbbabcbcccbbcbcabbccbb
abcbccabbcaabcbbaacbaa
bcccaabcacccabbbbcaacaccabba
abbbaacaaaccabccccabbbcabbbc
bcbcabbaccccccacaaab
aaa
bcbca
acbabbccbb
bca
aaaacaccbcbccaba
cbbcb
accabbccbc
accaacac
bb
baa
aabcccbaabbc
a
aaaabbbcabcbaaabcacabc
babbca
c
ccbcabbcaccca
accabbba
bbaccabbab
bcb
bb
cb
a
caac
c
ac
baccaaacccbacabbaaacacbcccacbc
aa
cabaaaacbbcabbaccccccb
abacbcac
abbbacbaa
acac
cc
cbc
cbcbabaacabcbcca
ab
bbb
abaacbbbcbbcabbbcc
cb
ba
b
bbab
ccabcbaaacccccbba
acbbc
ba
bbbbcac
bbbb
cab
cbcbc
ccbbc
285987