#2303. 游戏人生
游戏人生
游戏人生
题目描述
2018 陕西省青少年信息学(计算机)奥林匹克集训队试题1 2018 年4 月22 日 游戏人生 题目描述 XDD 是个游戏迷,整天沉迷于游戏不能自拔,他的父亲为了拯救沉迷于游戏中的他, 只好通过设计游戏的方式让他学到一些知识。 一天,XDD 的父亲设计了这样一个游戏。 给定N 个由小写字母组成的字符串,接下来Q 组询问,每组询问仅有两个字符串s1,s2, 询问,两个字符串相遇的过程中,第K 小的代价是多少。 相遇的定义如下: 假设两个字符串s1,s2 的最长公共前缀是T,那么,不停的分别从s1,s2 的末尾删掉一个 字符串,直到两个字符串都等于T。从某个字符串末尾删除一个字符c 的代价是 pow(c,num[c]) % 100007,c 指的是该字符-’a’+1 后的结果,num[c]指的是该字符在整个当前 串中出现的次数。 例如,询问的两个串是”aabbcc”,”aabddd”,那么,两者相遇的代价序列是: aabbcc->aabbc(代价为33=9)->aabb(代价为3)->aab(代价为2) aabddd->aabdd(代价为444=64)->aabd(代价为44=16)->aab(代价为4) 从小到大分别是:2,3,4,9,16,64。 输入格式 第一行输入N,Q,含义如题意所示。 接下来输入N 行,每行一个字符串,表示s[i]。 然后输入Q 行,每行三个数字x,y,k 表示询问第x 个字符串和第y 个字符串相遇的第k 小的代价是多少,如果第k 小不存在,输出-1。 输出格式 每行一个整数,表示答案。 输入样例 5 5 oooono ooono oono ono no 1 2 5 2 3 4 3 4 3 4 5 2 1 5 4 输出样例 59326 3375 225 14 15 数据范围
2018 陕西省青少年信息学(计算机)奥林匹克集训队试题1 2018 年4 月22 日 case n q MAXLEN ∑LEN 额外的 1 <=1000 <=1000 <=1000 / 保证给定的字符串存在一种排列s[1]~s[n],可以 使得 ∑(len(s[i])-∑f(s[i],s[i+1])<=1000000 f(s[i],s[i+1])表示两个字符串的最长公共前缀 长度 2 3 <=1000 <=100000 <=1000 <=1000000 4 5 6 <=100000 / 7 8 <=10000000 9 10
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
(本题数据包未提供小体积样例)