#PQJ2145x12594. QOJ 2145_12594

    ID: 2778 传统题 18000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTSC 2010字符串字典树数学

QOJ 2145_12594

IOI2010 中国国家队选拔赛 第二试 2010-05-06 珠宝商 【问题描述】 Louis.PS 是一名精明的珠宝商,他出售的项链构造独特,很大程度上是因为 他的制作方法与众不同。每次Louis.PS 到达某个国家后,他会选择一条路径去 遍历该国的城市。在到达一个城市后,他会使用在这个城市流行的材料制作一颗 珠子,并按照城市被访问的顺序将珠子串联做成项链,为了使制作出来的项链不 会因为城市之间的竞争而影响销量,路径中同一个城市不会重复出现(因为如果 项链中A 城市的材料比B 城市的材料使用的多,则项链在B 城市的宣传可能会 受到影响)。经过多年对消费者的调查,Louis.PS 已经掌握了判断一条项链吸引 消费者程度的方法,具体来说,Louis.PS 经过调查得出了受消费者欢迎的项链的 特征,并基于此制作了一个长项链(Louis.PS 称之为特征项链)。对于一条待售的 项链,这条项链在特征项链里出现的次数越多,这条项链就越受消费者欢迎。 考虑到现实情况的复杂性,我们对条件做出适当的简化。对于每个国家,在 某些城市间存在道路直接相连,对于两个不同的城市,有且仅有一条路径连接 这两个城市(即国家是连通的,且不存在一个环)。对于每个城市,我们用一个 小写字母来表示在这个城市流行的材料类型。这样,我们就可以用一个仅包含小 写字母的字符串来表示一条项链,我们将特征项链所对应的字符串称作特征字符 串,设为EigenString[1..M],M 为特征项链的长度。对于一条项链,假设其对应字 符串为P[1..L],L 为这条项链的长度。如果存在一个正整数K, 使 EigenString[K..K+L-1]=P[1..L],称这条项链在特征项链中出现了一次。满足上 述条件的正整数K 的个数即为这条项链在特征项链的出现次数,记为 Popularity(P)。 Louis.PS 使用数学中的期望概念来评价一个国家是否适合珠宝的采集,对于 一个包含N 个城市的国家,令Stru,v 表示沿着从u 开始,至v 结束的路径所得到 的项链的对应字符串。(Stru,v 与Strv,u 表示的串一般不相同),则 / N2. Expectation = ∑ ࡼ࢕࢖࢛࢒ࢇ࢘࢏࢚࢟ ሺࡿ࢚࢘ ,࢜ሻ ,࢜ 对于如下的例子(图中实线表示两端点的国家有直接道路相连): N=3,所流行的材料类型分别为a,a,b。 EigenString = “abaab” Str(3,1)=ba Popularity(ba)=1 P1 Str(1,1)=a Popularity(a)=3 Str(1,2)=aa Popularity(aa)=1 a Str(1,3)=ab Popularity(ab)=2 P2 Str(2,1)=aa Popularity(aa)=1 P3 a Str(2,2)=a Popularity(a)=3 b Str(2,3)=aab Popularity(aab)=1 Str(3,1)=ba Popularity(ba)=1 Str(3,2)=baa Popularity(baa)=1 Str(3,3)=b Popularity(b)=2 第4 页 共9 页 IOI2010 中国国家队选拔赛 第二试 2010-05-06 ଷାଵାଶାଵାଷାଵାଵାଵାଶ ହ ൌ Expectation = ଷ ଽ 对于一个国家,Louis.PS 想知道其Expectation 的值,但苦于计算期望的工 作量太大。作为珠宝店的学徒,你当然不愿放过难得在老板面前展示自己的机会。 【输入文件】 输入文件jewelry.in,第一行包含两个整数N,M,表示城市个数及特征项链的 长度。 接下来的N-1 行,每行两个整数x,y,表示城市x 与城市y 有直接道路相连。 城市由1~N 进行编号。 接下来的一行,包含一个长度为N,仅包含小写字母的字符串,第i 位的字 符表示在城市i 流行的原料类型。 最后一行,包含一个长度为M,仅包含小写字母的字符串,表示特征字符串。 【输出文件】 输出文件jewelry.out 仅包含一个整数,为N2 * Expectation。 【样例输入】 3 5 1 2 1 3 aab abaab 【样例输出】 15 【数据规模】 有20%的数据,满足ܯ൑1000; ൑8000, ܯ൑50000; 有40%的数据,满足 对于100%的数据,ܰ, ܯ൑50000。 第5 页 共9 页