071017模拟 杂题

071017模拟

T1 排队(line) 想清楚了非常水,十几行搞定。其实就是最后所有男生都会到最后,而越靠后的男生越早到达,所以最晚的永远是最前面的男生,我们关注的也只是最前面的男生。一个男生到达后面的最早时间是后面女生的数量,且中途可能被后面相邻的男生卡住。但是,相邻两男之间的女生可以“缓冲”掉一定的“浪费时间”···
BZOJ3566 [SHOI2014]概率充电器 概率+树形DP 动态规划 期望概率

BZOJ3566 [SHOI2014]概率充电器 概率+树形DP

对现在来说算是非常难的DP,这样计算感觉很不好想啊,但是思路其实很清晰。 首先,这题要求的其实就是每个点被充电的概率,但如果正着推会很复杂,因为充电的情况比较多,所以我们计算每个点不被充电的概率。 假设我们目前在计算点i的值,那么把树划分成三个部分:i的父节点及以上部分,i以及i的子树,i的兄弟节点···