如今状态不佳,奋起而刷题

February 11, 2010 /

写于2009-05-18 09:17

如今状态不佳,做题没感觉,加之昨天的题目不大适合我,这么多的概率题,正式比赛最多也就一题,昨天比赛被人虐,还被人给BS了,这情况早就想到,前些天做腾讯的比赛,一些以前很快能做出来的题,要想好久,经历了几次WA才能AC。此次比赛也是首次个人作战,时间安排不合理,把四个小时花在了两个题上,最终还一个没过。

以下是解题报告:

A. 疯狂的石头

这是本次比赛最水的一题,一开始也不急着做题,先把所有题都看了一遍,看完发现有人过了此题,就开始做,只要分析好各种情况就很简单了。

每次只能取出两块白石头或一块黑石头,最终剩下一块白石头,剩下两块石头时只能是一块黑石头和一块白石头,那只要一开始白石头数量为偶数就无法剩下白石头,否则可以。

此题很快做完,由于用包含了C++的库,提交时用gcc,编译失败一次,太大意了。AC时间10:34。

C. 打赌

这是第二个做的题,但一直没过,这题要求的是箱子i到箱子j所装货物的总和小于l、大于等于l并且小于等于u、大于u的概率,需要设置一个数组sum[i]来记录从箱子1到箱子i所装货物的总和,箱子i到箱子j所装货物的总和=sum[j]-sum[i-1]。

一开始是用枚举起点,二分查找l和u的位置,累加概率,用G++交是错误的答案,改了几次还是,此时场上已有不少过2个的,于是去做了别的题。

后来用gcc交竟然是超时,在过了E之后才想到了用扫描线,即用了一个起点和终点指针,扫描一遍即可,时间复杂度为o(n),而原来方法为o(n*logn),可惜最后时间不多,写完还没来得及调试,比赛结束后用了不到5分钟就改好了。现在思维大不如以前了,前天晚上的线段树搞了好久超时才想到了树状数组。

H. 神奇的密码

这是第二个AC的题目,11:45。

这题也不难,对每组数据,先算出a1、a2、……、a9的和a19,如果a19不等于a10,将a19-a10存起来,因为a19%n=a10,所以a19=kn+a10,kn=a19-a10,最后再计算起来的数的最大公约数,如果最大公约数大于a10输出,否则输出“impossile”。

D. 空投训练

这是第三个AC的题目,13:09。

此题关键在于判断一个点是否在一个图形内部,矩形只要判断是否在x和y的范围之内,圆只要先求出点到圆心的距离,判断是否小于等于半径,比较麻烦的是三角形,我是根据三角形的任意两顶点算出直线方程ax+by+c=0,对三角形的另一顶点和欲判断的点求出ax+by+c的值,判断是否同号。

交了WA,又看了源码,发现没什么问题,又加了再WA,最后把自己写的宏定义ABS(f)给换成库函数fabs(f)就给过了,无语啦。

I. DNA序列检

这是第四个AC的题目,14:03。

因为字符串长度和查询次数都很大,不能每次查询都来计算,必须进行预处理,先算出字符串S的所有子串,这里用了一个技巧,因为字符集只有“ACTG”,而且子串长度不超过10,可以将子串转成5进制的数字,A=1,C=2,T=3,G=4,5^10=9765625,内存不超,用一个数组mark[i]来标记字符串只是存在子串T,T转成的数字为i。

预处理只需枚举子串的长度,从1到10,再枚举在字符串S中的起点,求出数字来,把mark[i]标记为1。查询时只要算出数字d,查一下mark[d]即可。

一开始用4进制,给WA了,改成5就过了。

E. 拯救小猫

这是第五个也是最后一个AC的题目,16:02。

这是一道比较典型的背包问题。用dp[i][j]表示前i个看守所救出j只小猫失败的最小概率,如果j小于第i个看守所的小猫数,dp[i][j]=dp[i-1][j],否则dp[i][j]=Min(dp[i-1][j],1-(1-dp[i-1][j-cat[i]])*(1-pi[i]))。

一开始以为dp[i][j]=Min(dp[i-1][j], dp[i-1][j-cat[i]]+pi[i]),从14:16第一次提交,改了快两小时还是错,才好好想想概率该怎么算,就这一道题终止了昨天的比赛。

F. 打折机票

这题要先求出任意两点间的最短距离,因为点数不多,可以用floyd算法,用pi[i][j]表示经过i条航线,总额为j成功的概率,可以用动态规划算出来。

对于每次查询,先查出a、b两点间的最短距离d,输出pi[d][m]即可。

G. 马路收费

输入的边刚好是棵树,用树形DP可以求出最大收益。这题写了没过,最后没时间改了。

J. 八皇后

先求出八皇后问题的解,解不多,对于每个解,将输入的每个点与解中的8个点分别求距离,而问题的求解是将输入的每个点移动到八皇后问题解中的点,且移动总步数最少,这可以转化为KM算法,将输入的点与八皇后问题解中的点进行匹配。

B. 减法游戏

此题数据比较弱,枚举周期都能过,小范就是在最后两分钟给水过了。

可惜下半学期课比较多,想多刷点题也没太多时间