分类 字符串哈希 下的文章

BZOJ 1014: [JSOI2008]火星人prefix

Solution用 Splay 维护区间 hash 值,然后每次二分长度即可。需要注意的就是这道题的哈希方式,如果想要支持合并操作,需要这么哈希:cur->hash = ls->hash + convert(cur->val) * base[ls->size] + base[ls->size+1] * rs->hash;可以发现每次是左儿子的哈希值 + 自身的值乘左儿子的大小 + 右儿子的哈希值乘上(左儿子大小+1)。这么做我们可以发现,每个数最终都会乘上比自己编号小的点数 - 1。所以树的结构不影响哈希值,就可以放心的用 splay 维- 阅读剩余部分 -

BZOJ 3555: [Ctsc2014]企鹅QQ

DescriptionPenguinQQ是中国最大、最具影响力的SNS(Social Networking Services)网站,以实名制为基础,为用户提供日志、群、即时通讯、相册、集市等丰富强大的互联网功能体验,满足用户对社交、资讯、娱乐、交易等多方面的需求。小Q是PenguinQQ网站的管理员,他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析,小Q发现同一个人注册的账户名称总是很相似的,例如Penguin1,Penguin2,Penguin3……于是小Q决定先对这种相似的情形进行统计。小Q定义,若两个账户名称是相似的,当且仅当这两个字符串等长且- 阅读剩余部分 -

【字符串哈希】洛谷 3370: 自然溢出、单模哈希、双模哈希

前言字符串哈希就是把一个字符串用一个数字表示,且尽量要保证不同的字符串对应的数字不同,方便利用此性质搞事情。题目原文https://www.luogu.org/problem/show?pid=3370做法大体的做法就是把字符串的每一个字符看作一个数字,然后答案累加每一个数字乘上一个质数,然后把答案模上一个质数。自然溢出哈希一般不会被卡,但是出题人想卡你也是可以做到的。利用了 unsigned long long 溢出之后自动对 $$ 2^{64} $$ 取模的性质,可以不手动取模。#include <cstdio> #include <cstring&g- 阅读剩余部分 -