一份仅用于学习的伸展树C实现

这份代码来自于以前的Wikipedia,遇到这份代码也许是缘分吧,虽然实现上十分的冗长(好多好多的废话),但是也正因为如此这份代码展示了伸展树操作的每一个细节,尽管没什么实用价值,但是拿来理解splay是很好的。我自己抄了一遍同时加上了注释。

 

POJ 3744 Scout YYF I

题意

某人在直线上走,直线上有若干格子,起点是1号格,每次这个人都有p概率走1格,1-p概率走二格,有一些格子有地雷,走上去就被爆了,所以要你求你能安全走到终点(可以看成是站在n+1号格)上概率。

思路

每一个格子的概率都可以通过它前两个的格子的概率推出来,这样的话跟斐波那契很像。
联想我们想快速地搞出来一个非常大的fib值的方法是什么?快速幂。
所以这个题我们用快速幂来做。

dp方程其实都不叫dp,叫递推,大概长这个样子:

\begin{bmatrix}p&1-p\\1&0 \end{bmatrix}\begin{bmatrix}p_{n} \\ p_{n-1}\end{bmatrix}=\begin{bmatrix} p_{n+1}\\p_{n}\end{bmatrix}

直接矩阵乘法模版+快速幂就行。

处理地雷的话,你就先走到地雷那里,停一下,把地雷格的dp值抹成0,然后继续往下走,走到下一个地雷,最后走到终点。

代码

 

HDU 4405 Aeroplane chess

题意

玩线性飞行棋,一共有n个格子,每一次扔骰子,扔几点走几格,如果踩到了跳跃格,就跳过去,而且可以连续跳跃,走到或冲过终点游戏就胜利。问你扔多少次骰子之后游戏胜利(求期望)。

思路

很直接的概率dp题,加上了跳跃,不过因为我们的方向始终如一,所以没有成环的悲剧发生,可以很轻松的解出来。
我们设dp[i]表示位于第i格时,完成游戏需要的扔骰子数目,那么我们有:

dp[i]=\sum_{k=1}^{6}(\frac{1}{6}dp[i+k])+1

对于a to b的跳跃关系,我们又有:

dp[a]=dp[b]

这样dp方程就推好了。

代码

 

POJ 2096 Collecting Bugs

题意

给软件挑bug,每天挑出来一个,每个bug都有两个属性:分类和子系统,这两个属性都是完全随机的,已知一共有n个分类,s个子系统,问你挑出的bug完全覆盖全部分类和子系统需要多长时间(求期望)。

思路

优惠券问题的变种,相当于升高到了二维,因此dp数组也要开成二维。

我们设定dp[i][j]表示距离完成任务还有i个分类j个子系统没有覆盖,状态的转移用如下几种:
1.挑出的bug属于全新的分类和子系统
2.挑出的bug仅仅属于全新的分类
3.挑出的bug仅仅属于全新的子系统
4.挑出的bug没有任何新意
这样,我们可以得出状态转移方程:dp[i][j]=\frac{i}{n}\frac{j}{s}dp[i-1][j-1]+\frac{n-i}{n}\frac{j}{s}dp[i][j-1]+\frac{i}{n}\frac{n-j}{s}dp[i-1][j]+\frac{n-i}{n}\frac{n-j}{s}dp[i][j]+1

经过化简可以发现这是个很直接的递推方程了,所以可以很轻松的出答案了。

代码

 

ZOJ 1889 Ones

题意

给你一个数n,n不能被2,5整除,问你n的最小的每个数位全是1的倍数有多少位。

思路

同余定理,另外这个题保证有解,所以相信自己,暴力出奇迹。

代码

 

POJ 3488 Arne Saknussemm

题意

这个题的目的是练习读题,所以请努力理解这个题的题意,这里故意不翻译,it’s good for you~。

思路

操作时需要注意,string对象的结束位置并不是像char数组那样用’\0‘标记的,除非string对象被重做,否则这个对象的size值不会改变,即使你把一个string对象的每个字符全都弄成’\0’,你输出的也不是空串,而是一堆不可见的’\0’。

如果这个题很神秘的WA到死,请检查一下是不是跪在了不可见字符上。

代码

 

CodeForces 484B Maximum Value

题意

给你一串数,让你找出一组(i,j),使得在保证第i项大于等于第j项的同时,第i项mod第j项最大,求这个最大值。

思路

要有一种转换的思维,余数最大的话,可以另一个方向进行考虑,a%b=c的话,a可以看成是kb+c,这个里面b,c是已知的,这个k可以枚举,这样就把求余数这个事情转换成了枚举/搜索,换一个思路问题可能就突破了。

对给出的数列sort一下,unique一下,erase一下,这样就有效的避免了重复数据的干扰(如果你不unique可能会被这个题的某组坑数据给弄T),而且sort完才能做。sort好之后,我们挨个数枚举,对于每个数k,我们考虑这个数列上0~k,k~2k,2k~3k,…这些个小区段,每个小区段中最大的那个数 mod k可能是最大的,我们挨个数挨个区段去枚举就可以了。
但是暴力枚举是过不了的,我们就把在数列中找k,2k,…这个过程改成二分搜索,这样复杂度降为nlogn就行了。

代码

 

 

POJ 1019 Number Sequence

题意

11212312341234512345612345671234567812345678912345678910123456789101112345678910…
让你求这么一个丧心病狂的数列第i位是啥。

思路

找规律,我们可以把数列切割为1/12/123/1234/…这样我们可以想办法求出每一段的控制范围,然后对于给出的i,先快速确定这个i会落在哪一个数的控制范围里面,是第几个,然后再想办法快速确定在这个控制范围内i到底对应了哪个数,我写的比较恶心(很长),其实在纸上试着写一些应该是能发现具体的规律和算法的。

代码

 

POJ 3685 Matrix

题意

好像是《挑战程序设计竞赛》上面的原题。题意是给你一个矩阵上每一项的位置与值对应的公式,让你求第k小的项。

思路

我们仔细看公式会发现对于每一个固定的j,公式结果随i单调递增,这样我们可以二分答案,对于mid值,我们在每一列再二分一次,求出比这个数小的数的个数,然后每一列的个数相加,就是这个数的排名。然后这个排名可以作为二分中判定的基准。这里还有一种替代思路,就是对于每一列不二分,而是解一个二次方程直接求出每一列的分排名。

代码

 

hihoCoder wk40 A 三分求极值

从来没有遇到过这样的三分题(毕竟因为是鶸),http://hihocoder.com/contest/hiho40/problem/1,因为是教学题所以没有难度,思路人家都给你了。

代码

 

Scroll to top