标签归档:hash

BZOJ 1014: [JSOI2008]火星人prefix(二分hash+splay)

Description

  火星人最近研究了一种操作:求一个字串两个后缀的公共前缀。比方说,有这样一个字符串:madamimadam,
我们将这个字符串的各个字符予以标号:序号: 1 2 3 4 5 6 7 8 9 10 11 字符 m a d a m i m a d a m 现在,
火星人定义了一个函数LCQ(x, y),表示:该字符串中第x个字符开始的字串,与该字符串中第y个字符开始的字串
,两个字串的公共前缀的长度。比方说,LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0 在研究LCQ函数的过程
中,火星人发现了这样的一个关联:如果把该字符串的所有后缀排好序,就可以很快地求出LCQ函数的值;同样,
如果求出了LCQ函数的值,也可以很快地将该字符串的后缀排好序。 尽管火星人聪明地找到了求取LCQ函数的快速
算法,但不甘心认输的地球人又给火星人出了个难题:在求取LCQ函数的同时,还可以改变字符串本身。具体地说
,可以更改字符串中某一个字符的值,也可以在字符串中的某一个位置插入一个字符。地球人想考验一下,在如此
复杂的问题中,火星人是否还能够做到很快地求取LCQ函数的值。

Input

  第一行给出初始的字符串。第二行是一个非负整数M,表示操作的个数。接下来的M行,每行描述一个操作。操
作有3种,如下所示
1、询问。语法:Qxy,x,y均为正整数。功能:计算LCQ(x,y)限制:1<=x,y<=当前字符串长度。
2、修改。语法:Rxd,x是正整数,d是字符。功能:将字符串中第x个数修改为字符d。限制:x不超过当前字
符串长度。
3、插入:语法:Ixd,x是非负整数,d是字符。功能:在字符串第x个字符之后插入字符d,如果x=0,则在字
符串开头插入。限制:x不超过当前字符串长度

Output

  对于输入文件中每一个询问操作,你都应该输出对应的答案。一个答案一行。

Sample Input

madamimadam
7
Q 1 7
Q 4 8
Q 10 11
R 3 a
Q 1 7
I 10 a
Q 2 11

Sample Output

5
1
0
2
1

HINT

1、所有字符串自始至终都只有小写字母构成。

2、M<=150,000

3、字符串长度L自始至终都满足L<=100,000

4、询问操作的个数不超过10,000个。

对于第1,2个数据,字符串长度自始至终都不超过1,000

对于第3,4,5个数据,没有插入操作。

发现是大白书上的某个题的弱化版,通过splay来维护字符串的hash值,询问可以二分判断LCP的长度。

但是hash的函数得弄的好一点,一不小心就T掉了。。。

 

2016-2017 ACM-ICPC CHINA-Final Problem F. Mr. Panda and Fantastic Beasts(蛤习做法)

最近没怎么做题,状态很差。。。

题意:给出n个字符串,让你找出一个最短的子串满足,这个子串只在第一个字符串内出现在剩余的n-1个字符串内都不会作为子串。如果有多个答案的话,输出字典序最小的那种。n<=50000,每组数据的字符串长度之和不超过250000,所有数据的字符串长度之和不超过3*10^6。

据说可以SAM或者SA,但是比赛的时候直接就想了二分+hash的策略。但是没调出来,赛后经过一番痛苦的过程给搞过去了。其实就是无脑暴力,因为cf10s的时限,跑了6s多。。。。

首先要求一个满足条件的最短字符串,我们可以二分这个长度。如果一个长度的所有子串不满足条件,那么需要这个长度更长一点,因为这个长度的前缀肯定还是不满足的。然后hash验证。我们预处理出来第一个串的各个位置的hash值,以及剩余的串的所有hash值。因为长度不超过250000,所以可以O(250000)预处理出来。然后我们验证的时候,先把第一个串在该长度下的所有子串的hash值放到一个multimap里面去,并存放这个子串的结束位置。然后在搞出来其余字符串的子串的hash值,判断出来哪些是可以用的。找一个字典序最小的就好了。

 

Divide by Zero 2017 and Codeforces Round #399 (Div. 1 + Div. 2, combined)做题记录

终于把这套题补完了,get到了不少已经忘了的和新的姿势。。。

A. Oath of the Night’s Watch

题意:找寻一个数组内比最小元素大而且比最大元素小的元素有多少个。

排序扫一下就好了。

B. Code For 1

题意:给出一个数字n,一次操作可以把一个数字变成x/2,x%2,x/2这样的一个序列。操作若干次直到把所有数字变为了1或者0。给出L和R统计这个区间有多少个1。0<=R-L<=1e5,n<=2^50。

我们可以先递归的找出n最后会化成一个多长的序列。设长度为len。然后区间长度才1e5,可以对每个位置都递归一下判断是0还是1。时间复杂度O(1e5*log(n))就好了。。。

C. Jon Snow and his Favourite Number

题意:略。

随机了一些数据,发现找不超过十几次就可以出现一个循环节,循环节长度没超过5。(随机的,不怎么靠谱)。然后就这么暴力的找循环节,hash一下序列就可以了。

 

D. Jon and Orbs

题意:给出k种球,每天等概率的产生一种球,现在想知道让每种球都至少有一件的概率大于等于p/2000至少需要多少天.一共k次询问。k,p,q均小于1000。

概率dp,设dp[i][j]为到第i天产生j种球的概率。那么dp[i][j]=dp[i-1][j-1]*(k-j+1)/k+dp[i-1][j]*j/k。dp[0][0]=1.

然后就这么dp就可以了。但是天数的上限并不是k。而估计天数的限制又去学习了一波。。。

假设我们现在有i种球了,那么我们获得下一种新球的概率就是p=(n-i)/n。那么获得i+1种球的期望抽取次数也就是:

那么就是一个期望的线性相加的过程了。从1-k进行求和,,这个和项是一个调和级数,大概是一个log(k)。那么我们天数开到k*log(k)就好了。当然需要预处理dp数组。

E. Game of Stones

题意:给出n堆石子,和nim游戏类似的规则,但是假如一堆石子已经在之前被拿走了x个石子,那么之后任何人都不能再拿这么多个石子了。每堆石子不超过60个。

暴力求sg函数了。sg[0]=0。dfs(n,mask)代表当前有n个石头,mask是当前不能选的数字的集合。然后求出来sg函数值即可。。。可以本地打表,但是我直接交了dfs也给过了。可能状态数少吧。。

F. Barrels and boxes

题意:给出f个食物和w瓶酒,一种东西可以放到一个stack里,要求相同种类的stack不能连续的放。而且w的各个stack必须要大于给出的H才可以。求合法的概率p/q。输出p*q对于1e9+7的逆元。

一共有w个酒,那么酒可以分成的堆数就是w种。我们枚举酒被分成的堆数,假设现在被分成了i堆(每堆都不为空)。那么由插板法可知w个物品分成i堆的方案数C(w-1,i-1)。那么考虑这i堆相当于隔板把f个物品又分组。因为可能把f分成i组或者i+1组或者i-1组相当于是在f+1个空位里放。所以就是C(f+1,i)。两个相乘就是不考虑h的方案数。

考虑h的时候需要减去个i*h就可以了。