071017模拟 杂题

071017模拟

T1 排队(line) 想清楚了非常水,十几行搞定。其实就是最后所有男生都会到最后,而越靠后的男生越早到达,所以最晚的永远是最前面的男生,我们关注的也只是最前面的男生。一个男生到达后面的最早时间是后面女生的数量,且中途可能被后面相邻的男生卡住。但是,相邻两男之间的女生可以“缓冲”掉一定的“浪费时间”···
BZOJ2707 [SDOI2012]走迷宫 Tarjan+高斯消元 图论 期望概率

BZOJ2707 [SDOI2012]走迷宫 Tarjan+高斯消元

  题目链接 和BZOJ3270比较相似,都是在图上高斯消元来转移状态。 观察数据范围,可以很明显地看出来必须先Tarjan缩点,之后在强连通分量里面进行高斯消元。 一开始仿照3270写了个正着推出的式子,发现不太好搞,于是重新倒着想了一遍。 设f[i]:从i点出发走到终点的期望步数,则f···
BZOJ3566 [SHOI2014]概率充电器 概率+树形DP 动态规划 期望概率

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

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

BZOJ1076 奖励关 期望概率+状压DP

看数据范围,是期望+状压,状态转移也很好想,但是这道题如果正向转移会比较麻烦,因为处理无效状态转移到有效状态会比较麻烦。但是,如果逆向思考,就会容易一些。设f[i][j]表示前i次选到了状态为j的最优解。倒序枚举每一次,枚举状态,枚举该次选到的物品,若当前状态允许选择该物品,则该物品可以选或不选,由···
书(book.*) 期望概率 期望概率

书(book.*) 期望概率

到目前为止,只做过两道用分数的期望概率题,一直觉得很难处理,但是貌似找到了一些规律。这道题只需要把分母化成逆元,所有除法也换成逆元,就可以当做一般的概率题搞了。 关于最后一步,感性理解一下吧= = [crayon-5a5f4ef0a3a25966761321/]    
BZOJ2438 [中山市选2011]杀人游戏 期望概率+tarjan 图论 期望概率

BZOJ2438 [中山市选2011]杀人游戏 期望概率+tarjan

考试的时候想的是警察一步一步确认凶手,还要缩减比例,所以完全想错了。警察是在同时完成所有调查工作,而且在同一个强连通分量中,警察只要调查一个人,剩下的人就都会被确认,即关系具有传递性。调查每个人,警察都有死亡的概率,所以最终存活的概率即为1-调查的人数/总人数。tarjan缩点建图,入度为0的点数即···
BZOJ1426 收集邮票 期望概率 动态规划 期望概率

BZOJ1426 收集邮票 期望概率

这道题已经听达哥和meaty讲了两种方法了,但是感觉还是有些麻烦,怂了一波题解之后,自己又推了推式子,找到了一个既好理解又容易实现的做法。 首先,第i张购买的邮票花费为i元,等效于“每张邮票原价1元,买了一张邮票后,其他邮票都涨了1元”。 设f[i]:当前已买到i种邮票,买全邮票的期望次数;g[i]···