Death
Educational Codeforces Round 97 (Rated for Div 2) G. Death DBMS
Problem - G - Codeforces 题意 给定n个字符串,每个字符串有一个值val,n次询问,每次给一个字符串,询问给定n个字符串中是询问字符串子串的值的最大值 分析 多模式匹配,从中找到给定串的子串,想到建立ac自动机,对于给定字符串,在自动机上面匹配时,沿fail指针向上跳并求最大 ......
Death DBMS题解(AC自动机)
题目传送门 CF1437G 好题 观察这道题,发现有关字串的题目,一般来说,这种题都要构建\(AC\)自动机,所以考虑构建。 构建之后,原来的所有 \(fail\) 是一个树形结构。 解法 \(1\): 考虑从询问入手,那么对于每一个询问,等价于就是查询每一个 \(Q_i\) 包含的后缀的最大值,再 ......
Educational Codeforces Round 138 (Rated for Div. 2) B. Death's Blessing
这是一个电脑游戏,$n$ 个怪物排成一行,第 $i$ 个怪物的血量为 $a_i$ 并且它的亡语强度为 $b_i$ 。规则是: * 玩家每秒可以削减一只怪物的一点血量。 * 第 $i$ 只怪物死亡后会释放亡语,它两侧的怪物血量会得到 $b_i$ 的增幅血量。边界上的怪物只能对它的邻居进行亡语增幅。 * ......