bzoj 2969: 矩形粉刷 概率期望+快速幂
还是老套路：期望图上的格子数=$\sum$每个格子被涂上的期望=$\sum$1-格子不被图上的概率这样的话就相对好算了.那么，对于$(i,j)$来说，讨论一下上，下，左，右即可.然后发现四个角的面积会被重复统计，所以再减去$4$个角的贡献即可.#include<bits/stdc++.h>...
bzoj 2969: 矩形粉刷 概率期望
题目:为了庆祝新的一年到来，小M决定要粉刷一个大木板。大木板实际上是一个W*H的方阵。小M得到了一个神奇的工具，这个工具只需要指定方阵中两个格子，就可以把这两格子为对角的，平行于木板边界的一个子矩形全部刷好。小M乐坏了，于是开始胡乱地使用这个工具。假设小M每次选的两个格子都是完全随机的（方阵中每个格...
[BZOJ4832]抵制克苏恩(概率期望DP)
方法一：倒推，最常规的期望DP。f[i][a][b][c]表示还要再攻击k次，目前三种随从个数分别为a,b,c的期望攻击英雄次数，直接转移即可。#include<cstdio>#include<cstring>#include<iostream>#include&...
【POJ 2096】Collecting Bugs 概率期望dp
题意有s个系统，n种bug，小明每天找出一个bug，可能是任意一个系统的，可能是任意一种bug，即是某一系统的bug概率是1/s，是某一种bug概率是1/n。求他找到s个系统的bug，n种bug，需要的天数的期望。分析计算期望E=∑所有可能需要的天数*概率找到s个系统n种bug，需要最少max（s，...
【专题】概率期望DP
11.22：保持更新状态：主要发一些相关的题目和个人理解（P.S.如果觉得简单，可以直接看后面的题目）upd11.30更完了【NO.1】UVA12230 CrossingRivers 一道比较坑的题目,多给了一个没用的条件...其实就是利用线性关系，取一个平均值就OK了。把最优情况和最差情况算出来，...
【loj6191】「美团 CodeM 复赛」配对游戏 概率期望dp
题目描述n次向一个栈中加入0或1中随机1个，如果一次加入0时栈顶元素为1，则将这两个元素弹栈。问最终栈中元素个数的期望是多少。输入一行一个正整数n。输出一行一个实数，表示期望剩下的人数，四舍五入保留三位小数。样例输入10样例输出4.168题解概率期望dp显然任何时刻栈中的元素自底至顶一定是若干个0+...
luoguP3750 [六省联考2017]分手是祝愿 概率期望DP + 贪心
...........真的神状态了，没办法去想的状态...................考试的时候选择$50$分贪心+$15$分状压吧，别的点就放弃算了........令$f[i]$表示从最小步数为$i$时走到最小步数为$i-1$的状态的期望步数（所以题目中的$k$实际上是个提示............
bzoj2969 矩形粉刷 概率期望
此题在bzoj是权限题，，，所以放另一个oj的链接题解：因为期望线性可加，所以可以对每个方格单独考虑贡献。每个方格的贡献就为至少被粉刷过一次的概率×1(每个格子的最大贡献就是1...)每个方格至少被粉刷过一次的概率=1-一次都没被粉刷过的概率因为每次选择都不互相影响，因此我们实际上只需要计算对于每一...
hdu-5810 Balls and Boxes(概率期望)
题目链接：BallsandBoxesTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/65536K(Java/Others)ProblemDescriptionMr.Chopsticksisinterestedinrandomphenom...
概率期望dp
对于概率dp，我一直都弄得不是特别明白，虽然以前也有为了考试去突击过，但是终究还是掌握得不是很好，所以决定再去学习一遍，把重要的东西记录下来。1.hdu4405Description在一个\(1*n\)的格子上掷色子，从\(0\)点出发，掷了多少前进几步，同时有些格点直接相连，即若\(a\)，\(b...
Codeforces - 1264C - Beautiful Mirrors with queries - 概率期望dp
一道挺难的概率期望dp，花了很长时间才学会div2的E怎么做，但这道题是另一种设法。https://codeforces.com/contest/1264/problem/C要设为\(dp_i\)表示第\(i\)个格子期望经过多少次，所以\(dp_{n+1}=1\)。https://www.cnbl...
【bzoj4832】[Lydsy2017年4月月赛]抵制克苏恩 概率期望dp
题目描述你分别有a、b、c个血量为1、2、3的奴隶主，假设英雄血量无限，问：如果对面下出一个K点攻击力的克苏恩，你的英雄期望会受到到多少伤害。输入输入包含多局游戏。第一行包含一个整数T(T<100)，表示游戏的局数。每局游戏仅占一行，包含四个非负整数K,A,B和C，表示克苏恩的攻击力是K，你有...
【BZOJ-1419】Red is good 概率期望DP
1419:RedisgoodTimeLimit: 10Sec MemoryLimit: 64MBSubmit: 660 Solved: 257[Submit][Status][Discuss]Description桌面上有R张红牌和B张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌...