「BZOJ 3578」GTY的人类基因组计划2-Hash

$n$ 个人来做实验,有 $m$ 个房间,一开始所有人都在 $1$ 号房间里,有两个操作:

  1. 让第 $i$ 个人去房间 $j$
  2. 让区间 $[l,r]$ 的房间做实验

实验会获得一些实验信息点数,点数为房间里的人数(不会重复增加点数),求每次操作获得的点数。

「ARC 071E」TrBBnsformBBtion

给定两个由 AB 组成的字符串 $S, T$,其中字符 A 可以变为 BBB 可以变为 AAAAABBB 可以被删掉,询问 $S$ 中的一个给定子串能否变为 $T$ 中的一个给定子串。

「CF-633C」Spy Syndrome 2-Hash+map

After observing the results of Spy Syndrome, Yash realised the errors of his ways. He now believes that a super spy such as Siddhant can’t use a cipher as basic and ancient as Caesar cipher. After many weeks of observation of Siddhant’s sentences, Yash determined a new cipher technique.

For a given sentence, the cipher is processed as:

「BZOJ-1056」「BZOJ-1862」-排名系统-Splay+map/SBT+HashSet

排名系统通常要应付三种请求:上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时,他原有的得分记录会被删除。为了减轻服务器负担,在返回某个区段内的排名记录时,最多返回$10$ 条记录。

字符串 Hash 学习总结

字符串Hash学习总结

定义

字符串Hash简单来说就是:把字符串有效地转换为一个整数

Hash函数

就是使得每一个字符串都能够映射到某一个整数上的函数

「NOIP 2014」解方程-Hash

分析

令$f(x) = a_0 + a_1 x + a_2x^2 + \cdot \cdot \cdot + a_nx^n = 0$,那么对于一个质数$p$取模,如果有$f(x) = 0$,则一定有$f(x)\% p = 0$。
我们只需要求出所有满足$f(x)\%p = 0$的$x$,然后模另一个质数检验。
时间复杂度为$O(np + n \frac{nm}{p})$。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×