A6654 | $「雅礼集训 2018 Day11」字符串$

时间限制4s

内存限制512MB

通过 / 提交0/0

题目描述

有 $N$ 个字符串，每个字符串有一个权值 $v_i$。随后给出 $M$ 次询问，每次对一个区间进行检测。令最长的字符串长度为 $L$，那么会给出 $g_1, ..., g_L$ 表示每个长度的字符串的「识别值」。 对若干个字符串构成的集合 $P$ 进行测试的过程如下： 对字符串 $S$ 定义 $f(S)$ 表示 $S$ 在 $P$ 中以其为前缀出现的串的权值和。 那么如果 $S$ 在 $P$ 中作为前缀出现过，并且 $Bf(S) + A\times {\rm len}(S) \geq C$，那么则将 $g_{{\rm len}(S)}$ 加入集合 $G$。 最后随机选择一个区间 $[x, y](1 \leq x \leq y \leq L)$，如果 $[x, y] \bigcap G \neq \emptyset$，那么测试成功，否则测试失败。输出测试成功的概率并用最简分数表示。 特别地，整数 $k$ 表示为 $k / 1$。

第一行四个数 $N, A, B, C$。 接下来一行 $N$ 个数 $v_1, ..., v_N$。 接下来 $N$ 行表示 $N$ 个字符串。 接下来一行 $L$ 个数表示 $g_{1}, ... ,g_L$，保证 $g_1, ..., g_L$ 是一个 $1$ 至 $L$ 的排列。 接下来一行一个数 $M$。 接下来 $M$ 行，每行两个数 $l, r$，表示对第 $l$ 到第 $r$ 个字符串进行测试。

$M$ 个数表示答案。

输入 #1

5 2 3 15
1 2 3 2 0
aba
aa
abb
aaa
bbbb
1 3 2 4
6
1 4
1 3
2 3
2 4
5 5
3 5

输出 #1

9/10
9/10
7/10
9/10
0/1
7/10

C++ 编辑器

输入

输出