第一题:
Alice和Bob两个人正在玩一个游戏，游戏有很多种任务，难度为p的任务（p是正整数），有1/2p 的概率完成并得到2p−1分，如果完成不了，得0分。一开始每人都是0分，从Alice开始轮流做任务，她可以选择任意一个任务来做；而Bob只会做难度为1的任务。只要其中有一个人达到n分，即算作那个人胜利。求Alice采取最优策略的情况下获胜的概率。
n<=500
解题过程:
1.感觉这题是今天最难的一题。主要是概率的题目基本没有做到过。先做了后面两题,然后花了一个多小时才把这题给想出来。
2.首先可以转化一下,两个人一开始都是n分,Alice每次有1/2p 的概率减去1/2p−1分.Bob每次有1/2的概率减去一分,看谁先减到<=0. 那么令F[x][y]表示当前Alice是x分,Bob是y分,当前是Alice取,Alice获胜的最大概率是多少。
3.假设本次Alice要减去k分,其成功的概率是p.那么分下面2种情况来讨论。
A:如果本次操作成功,那么胜利的概率是 p*(F[x-k][y]/2+F[x-k][y-1]/2). 对Bob也要讨论是否成功,如果成功,
F[x-k][y-1],否则就是F[x-k][y-1].
B:如果本次操作失败了,那么胜利的概率是 (1-p)*(F[x][y-1]/2+F[x][y]/2).
所以如果本次取k,成功的概率是p,那么获胜的概率
F[x][y]=p/2*(F[x-k][y]+F[x-k][y-1])+(1-p)/2*(F[x][y-1]+F[x][y]).
注意到递推式里面又出现了F[x][y],所以需要移项解方程:
( 1-(1-p)/2 )F[x][y]=p/2*(F[x-k][y]+F[x-k][y-1])+(1-p)/2*F[x][y-1]. 两边同时乘2得到
p*F[x][y]=p*(F[x-k][y]+F[x-k][y-1])+(1-p)*F[x][y-1]. 两边同时除以p得到
F[x][y]=F[x-k][y]+F[x-k][y-1]+(1-p)/p*F[x][y-1]. 按照方程枚举k写个记忆化搜索就可以了。
枚举k的时候傻逼了,限制了k<=x.实际上应该是k*2<=x的。 初始得分20.
第二题:
题目大意:
n头牛叠在一起,每头牛有两个指数A,B.每头牛承受的压力为它头上所有牛的指数A的和减去它本身的B。安排顺序使得压力最大的牛压力最小.
解题过程:
1.典型的相邻交换法证明贪心. 因为交换相邻的两头牛对其它牛是没有影响的.
2.假设有相邻的两头牛,指数分别为(Ai,Bi) (Ai+1,Bi+1).设它们头顶的牛的指数A之和为S.那么它们两个压力较大的那个的压力为 max{S+Ai+1-Bi , S-Bi+1}. 如果交换它们的位置,max{S+Ai-Bi+1 , S-Bi}.
如果原顺序更优,那么有max{S+Ai+1-Bi , S-Bi+1}<=max{S+Ai-Bi+1 , S-Bi}
两边同时减去S并加上Bi+Bi+1得到
max{Ai+1+Bi+1,Bi}<=max{Ai+Bi,Bi+1}
按照这个规则定义<,然后快排就可以了。
初始得分100.
第三题:
题目大意:
N点M边无向图,Q个询问(A,B),求A到B的一条路径使得权值最大边的权值最小。
解题过程:
1.这题完全就是NOIP2013 day1 T3 货车运输。用倍增求个lca就可以了,因为权值最大边的权值最小的路径必定是在最小生成树上,所以先求一个最小生成树。初始得分100.
2.网络上还有一种十分巧妙的方法,感兴趣的可以搜一下。