2018-team11-017

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[[Image(HW13.PNG)]]

== 总结 ==

=== zb ===
考试周结束后的第一场训练，还是在空调一般的咖啡馆打的。

感觉自己今天状态还可以，上来先写了H题，就是细节调了有点久。

但是今天的D,K,L都感觉想到了很关键的一步，就是很遗憾都跟答案差一点，但是相比于原来还是能感受到自己有点进步的。

今天自己表现还可以////

=== zyh ===
只做了一个J（卑微

刚上来状态很差，一个小时以后才好点

最后有好几道都是想了但没做出来，感觉很可惜

=== sj ===

状态不是很好

该想出来的题也不会做，哎

== 题解 ==

B.Balls and Boxes

题意：n个球放进m个盒子，求期望方差

做法：手玩小样例找式子

C.Colosseo

题意：给一个矩阵，问你最多能把几个点加入到一个已满足前面的点都跟后面的点连边的序列里

做法：数据范围小，暴力找出能放进去的位置，然后求一个lis即为答案

E.Elegant Construction

题意：构造一个有向图，无环，每个点刚好能到达给定数量点

做法：可以看出从小到大构造，连接a最小的若干个点即可

H.HearthStone

题意：抽一张牌，有n张过牌和m张直伤，问无限费斩杀概率

做法：概率dp即可

J.Joint Stacks

题意：维护两个栈，要求支持push、pop、merge三种操作

做法：相当于是维护以push时间为值的堆

K.Knights

题意：有n个骑士，向左或者右走，相遇的骑士决斗随机死掉一人，在骑士走到头会转向，求第n个骑士活下来的概率

做法：考虑dp，设f[i][j]表示前i个骑士最终有j个向右走的骑士的概率

      如果第i个骑士向右走，f[i][j]=f[i-1][j-1]

      如果第i个骑士向左走，f[i][j]=\sigma f[i-1][k]*(\frac{1}{2})^{k-j+1}

      则有递推式f[i][j]=\frac{1}{2}*(f[i-1][j]+f[i][j+1])

      但是还有一种情况是这个骑士走到最左返回，f[i][1]+=\sigma f[i-1][j]*(\frac{1}{2})^{j}

      则有递推式f[i][1]+=\frac{1}{2}*(f[i-1][1]+f[i][2])

      综合得到f[i][1]=f[i-1][1]+f[i][2]

总结

zb

考试周结束后的第一场训练，还是在空调一般的咖啡馆打的。

感觉自己今天状态还可以，上来先写了H题，就是细节调了有点久。

但是今天的D,K,L都感觉想到了很关键的一步，就是很遗憾都跟答案差一点，但是相比于原来还是能感受到自己有点进步的。

今天自己表现还可以////

zyh

只做了一个J（卑微

刚上来状态很差，一个小时以后才好点

最后有好几道都是想了但没做出来，感觉很可惜

sj

状态不是很好

该想出来的题也不会做，哎

题解

B.Balls and Boxes

题意：n个球放进m个盒子，求期望方差

做法：手玩小样例找式子

C.Colosseo

题意：给一个矩阵，问你最多能把几个点加入到一个已满足前面的点都跟后面的点连边的序列里

做法：数据范围小，暴力找出能放进去的位置，然后求一个lis即为答案

E.Elegant Construction

题意：构造一个有向图，无环，每个点刚好能到达给定数量点

做法：可以看出从小到大构造，连接a最小的若干个点即可

H.HearthStone

题意：抽一张牌，有n张过牌和m张直伤，问无限费斩杀概率

做法：概率dp即可

J.Joint Stacks

题意：维护两个栈，要求支持push、pop、merge三种操作

做法：相当于是维护以push时间为值的堆

K.Knights

题意：有n个骑士，向左或者右走，相遇的骑士决斗随机死掉一人，在骑士走到头会转向，求第n个骑士活下来的概率

做法：考虑dp，设f[i][j]表示前i个骑士最终有j个向右走的骑士的概率

如果第i个骑士向右走，f[i][j]=f[i-1][j-1]

如果第i个骑士向左走，f[i][j]=\sigma f[i-1][k]*(\frac{1}{2})^{k-j+1}

则有递推式f[i][j]=\frac{1}{2}*(f[i-1][j]+f[i][j+1])

但是还有一种情况是这个骑士走到最左返回，f[i][1]+=\sigma f[i-1][j]*(\frac{1}{2})^{j}

则有递推式f[i][1]+=\frac{1}{2}*(f[i-1][1]+f[i][2])

综合得到f[i][1]=f[i-1][1]+f[i][2]

附加文件