http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1325. 字符串游戏(徐捷)
时间限制:3.0s   内存限制:256.0MB  
总提交次数:148   AC次数:34   平均分:48.04
将本题分享到:
   
 


问题描述
  给定N个仅有a~z组成的字符串ai,每个字符串都有一个权值vi,有M次操作,操作分三种:
  Cv x v':把第x个字符串的权值修改为v'
  Cs x a':把第x个字符串修改成a'
  Q:求出当前的最大权字符串集合,使得这个集合中的字符串经过重新排列后满足除最后一个字符串外,前一个字符串是后一个的前缀(两个字符串相同也是前缀关系,也可以一个字符串都不选)
  前50%的数据可以接受离线算法,后50%的数据要求在线算法。
输入格式
  输入的第一行包含一个正整数Test表示当前的数据类型。
  输入的第二行包含两个正整数N,M表示字符串数和操作数。
  以下N行,每行一个字符串ai
  第N+3行包含N个整数vi
  以下M行,为M次操作,操作有三种Cv x v',Cs x a',Q,第三种操作如题目描述一样,对于Test=1的修改操作,不用做 任何变化,对于Test=2的修改操作,假设当前最后一次询问操作的答案是ans(如果还没有询问操作,ans=0),那么对于第 一种操作中的v'=min(1000,v'+(ans mod 1000)),对于第二种操作的字符串a',它的每一位都要加上ans mod 26(a~z循环)
输出格式
  对于每一次询问输出合法的最大权字符串集合的权值和。
样例输入
1
5 5
aba
ab
babb
abaa
abab
-2 1 4 2 3
Q
Cv 1 2
Q
Cs 3 abaab
Q
样例输出
4
6
9
数据规模和约定
  数据分两种,A类数据可以用离线的方法来完成,B类数据必须使用在线算法。
  令len=输入数据中所有出现的字符串总长度
  |v|<1001
编号
数据类别
范围
1



A
N,M≤30,len≤500
2

N,M≤1000,len≤10000
3
4
5


N≤50000,M≤105,len≤106
6
7
8
9
10
11



B




N≤50000,M≤105,len≤106
12
13
14
15
16
17
18
19
20