期望+期望dp-爱代码爱编程
说实话,我本人目前是没有接触到多少关于期望的题的,基本这个专题就是抄学长PPT+写自己理解
(持续更新,见一道补一道)
A 本题主要考察了运气
https://ac.nowcoder.com/acm/contest/46800/L
题目来源:2023牛客寒假算法基础集训营1
这个题首先要读懂题,我一开始是真以为这个题是运气题了.......后来才发现了真正的题目要求,剩下的都是废话
思路:最优策略,肯定是先锁定在哪个团体,然后确定是团队中的第几个成员。
团体的话最多问4次(要是前四次都回答否,则一定在第五个,这一步是通过推理可得),问一次就问出结果的概率是1/5,问两次出结果是4/5*1/4=1/5,三次同理也是1/5,四次出结果是2/5
那么我们算一下团体的期望:
个人同理:第一次是1/4,第二次是1/4,第三次是2/4
2.8+2.25=5.05 所以答案就是32
B 抽A
第一次抽到A的概率:4/52=1/13
第二次抽到A的概率:
(第一次抽到A和第一次没抽到A的情况分别累加)
最后归纳,得出每次的概率都是1/13,然后期望累加,得到答案是 n/13
C Game
题目来源:第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(上海)(热身赛)
https://ac.nowcoder.com/acm/contest/9731/A
这个题的思路就很简单了,就是找互质的有多少,然后互质的占总共的
这个题注意得分奇偶
n为偶数
n为奇数
(思路和B是完全一样的,抽到不抽到对它完全没有影响)
#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const int mod=1e9+7;
ll n;
int main(){
ll cnt=0;
scanf("%lld",&n);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(__gcd(i,j)==1) cnt++;
ll p=cnt,q=n-1;
if(n&1) q=n;
printf("%lld/%lld\n",p/__gcd(p,q),q/__gcd(p,q));
system("pause");
return 0;
}
D Tlopex从赌场偷来的不锈钢的骰子
题目链接: https://buctcoder.com/problem.php?cid=2586&pid=1
题干:Tlopex从昨晚梦中的赌场里偷了一个有n个面的不锈钢骰子,请帮帮他计算一下期望扔几次才能把每个面都掷到呢?0<=n<=10000
输入n,输出一个两位小数
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
double dp[MAXN];
int main() {
int n;
scanf("%d", &n);
dp[n] = 0;
for (int i = n - 1; i >= 0; i--) {
dp[i] = dp[i + 1] + (double)n / (double)(n - i);
}
printf("%.2lf\n", dp[0]);
return 0;
}
思路:
化简后
dp[i]指的是距离所有面都被投到的步数
我们知道,每次投掷,要么投出已投出的面数(概率是i/n),要么投出未投出的面数(概率是(n-i)/n)
然后dp[n]=0,然后写代码就行了