Uva 10217 概率
uva 11722 - Joining with Friend(概率)
题目连接：uva 11722 - Joining with Friend 题目大意：你和朋友乘火车，而且都会路过A市。给定两人可能到达A市的时段，火车会停w。问说两人能够见面的概率。 解题思路：y = x + w 和y = x - w在给定时间内围成的面积除以时间的总面积，就是求面积的时候要分情况处理。 #include <cstdio> #include <cstr
日期 2023-06-12 10:48:40
UVA 11021 - Tribles(概率递推)
UVA 11021 - Tribles 题目链接 题意：k个毛球，每一个毛球死后会产生i个毛球的概率为pi。问m天后，全部毛球都死亡的概率 思路：f[i]为一个毛球第i天死亡的概率。那么 f(i)=p0+p1f(i−1)+p2f(i−1)2+...+pnf(i−1)n 然后k个毛球利用乘法定理，答案为f(m)k 代码： #include <stdio.h> #inc
日期 2023-06-12 10:48:40UVA10056 - What is the Probability ?(概率）
UVA10056 - What is the Probability ?(概率） 题目链接 题目大意：有n个人玩游戏，一直到一个人胜出之后游戏就能够结束，要不然就一直从第1个到第n个循环进行，没人一轮，给出每一个人胜出的概率为p，问第i个人胜利的概率。 解题思路：第i个人要胜利。那么就可能在第一轮胜利。也可能在第i轮胜利，那么胜利的概率就是q = 1 - p;概率 = q^(i -
日期 2023-06-12 10:48:40UVA 11427 - Expect the Expected(概率递归预期)
UVA 11427 - Expect the Expected 题目链接 题意：玩一个游戏。赢的概率p，一个晚上能玩n盘，假设n盘都没赢到总赢的盘数比例大于等于p。以后都不再玩了，假设有到p就结束 思路：递推，dp[i][j]表示玩i盘。赢j盘的概率,那么一个晚上玩了n盘小于p的概率递推式为： dp(i,j)=dp(i−1,j)∗(1−p)+dp(i−1,j−1)∗p 总和为Q=dp
日期 2023-06-12 10:48:40UVA11722(见面概率)
题意： 有一个车站，两个人想要在这个车站见面，第一个人会在t1到t2之间的任意一个时刻到（时间上任意一点概率一样），并且停留w时间，第二个人是s2到s2的时间段到，停留也是w，问两个人的见面概率是多少？ 思路： 这个应该算
日期 2023-06-12 10:48:40
UVA11722(见面概率)
题意： 有一个车站，两个人想要在这个车站见面，第一个人会在t1到t2之间的任意一个时刻到（时间上任意一点概率一样），并且停留w时间，第二个人是s2到s2的时间段到，停留也是w，问两个人的见面概率是多少？ 思路： 这个应该算
日期 2023-06-12 10:48:40UVA11427玩纸牌（全概率+递推）
题意： 一个人玩纸牌游戏，他每天最多玩n局，枚举获胜的概率是a/b,每天玩牌只要获胜概率达到p，那么他今天就不玩了，明天接着玩，如果有一天他的概率没有达到p,(没有达到p的话他今天一定是玩了n次)，那么他以后就在也不玩了，问题是在平均的情况下，他能玩多少个晚上的牌
日期 2023-06-12 10:48:40
UVA11427玩纸牌（全概率+递推）
题意： 一个人玩纸牌游戏，他每天最多玩n局，枚举获胜的概率是a/b,每天玩牌只要获胜概率达到p，那么他今天就不玩了，明天接着玩，如果有一天他的概率没有达到p,(没有达到p的话他今天一定是玩了n次)，那么他以后就在也不玩了，问题是在平均的情况下，他能玩多少个晚上的牌
日期 2023-06-12 10:48:40UVa 11427 Expect the Expected (数学期望 + 概率DP)
题意：某个人每天晚上都玩游戏，如果第一次就䊨了就高兴的去睡觉了，否则就继续直到赢的局数的比例严格大于 p，并且他每局获胜的概率也是 p，但是你最玩 n 局，但是如果比例一直超不过 p 的话，你将不高兴的去睡觉，并且以后再也不玩了，现在问你，平均情况下他玩几个晚上游戏。 析：先假设第一天晚上就不高兴的去睡觉的概率是 q，那么有期望公式可以得到 E = q + (1-q) * (E + 1)，其中
日期 2023-06-12 10:48:40UVa 11722 Joining with Friend (几何概率 + 分类讨论)
题意：某两个人 A，B 要在一个地点见面，然后 A 到地点的时间区间是 [t1, t2]，B 到地点的时间区间是 [s1, s2]，他们出现的在这两个区间的每个时刻概率是相同的，并且他们约定一个到了地点，等待另一个人 w 分钟，问你他们可能见面的概率是多少。 析：就是一个高中的一个几何概率的典型例题，他们相遇的条件是 |s -t | <= w，然后在画出二维图，再求面积即可，现在问题的情况
日期 2023-06-12 10:48:40UVa 11021 Tribles (概率DP + 组合数学)
题意：有 k 只小鸟，每只都只能活一天，但是每只都可以生出一些新的小鸟，生出 i 个小鸟的概率是 Pi，问你 m 天所有的小鸟都死亡的概率是多少。 析：先考虑只有一只小鸟，dp[i] 表示 i 天全部死亡的概率，那么 dpi] = P0 + P1*dp[i-1] + P2*dp[i-1]^2 + ... + Pn*dp[i-1]^(n-1)，式子 Pjdp[i-1]^j 表示该小鸟生了 j 后代
日期 2023-06-12 10:48:40UVa 11468 Substring (AC自动机+概率DP)
题意：给出一个字母表以及每个字母出现的概率。再给出一些模板串S。从字母表中每次随机拿出一个字母，一共拿L次组成一个产度为L的串， 问这个串不包含S中任何一个串的概率为多少？ 析：先构造一个AC自动机，然后随机生成L个字母，就是在AC自动机的某个结点走多少步，dp[i][j] 表示在 i 结点，并且剩下 j 步， 然后记忆化搜索就OK了。 代码如下： #pragma comment(linker
日期 2023-06-12 10:48:40UVa 557 Burger (概率+递推)
题意：有 n 个牛肉堡和 n 个鸡肉堡给 2n 个客人吃，在吃之前抛硬币来决定吃什么，如果剩下的汉堡一样，就不用投了，求最后两个人吃到相同的概率。 析：由于正面考虑还要要不要投硬币，太麻烦，所以我们先求最后两人吃到不同的概率即可，再用 1 减去就OK。 假设最后两个人吃的不一样，那么前 n-2 个人吃的肯定是 n/2 -1个牛肉堡和n/2-1 个鸡肉堡，根据排列组合可知，概率应该是C(n-2,
日期 2023-06-12 10:48:40UVa 10900 So you want to be a 2n-aire? （概率DP，数学）
题意：一 个答题赢奖金的问题，玩家初始的金额为1，给出n，表示有n道题目，t表示说答对一道题目的概率在t到1之间，每次面对一道题，可以选择结束游戏， 获得当 前奖金；回答下一道问题，答对的概率p在t到1之间，答对的话奖金翻倍，答错的话结束游戏，没有奖金，求玩家赢的奖金的期望值的最大值。 析：首先是求期望，那就和平均值差不多，我们来分析第 i 道题时，两个情况，要么回答，要么不回答，如果不回答那么
日期 2023-06-12 10:48:40
UVa 11346 Probability (转化+积分+概率)
题意：给定a，b，s，在[-a, a]*[-b, b]区域内任取一点p，求以原点（0，0）和p为对角线的长方形面积大于s的概率。 析：应该明白，这个和高中数学的东西差不多，基本就是一个求概率的题，只不过更简单了，不用你算了，你给出表达式， 让计算机帮你算即可。 由对称性知道，只要求[a, b]区域内的概率就OK了，也就是xy > s，由高中的知识也知道应该先求xy = s的曲线， 然后求在
日期 2023-06-12 10:48:40
UVA 557 - Burger(概率 递推）
Burger When Mr. and Mrs. Clinton's twin sons Ben and Bill had their tenth birthday, the party was held at the McDonald's restaurant at South Broadway 202, New York.
日期 2023-06-12 10:48:40uva 11605 - Lights inside a 3d Grid(概率)
题目链接：uva 11605 - Lights inside a 3d Grid 题目大意：给定一个三维坐标系大小，每一个位置有一个灯。初始状态为关。每次随机选中两个点，以这两点为对角线的长方体内全部灯转变状态。操作K次。问说平均情况下。最后会有多少栈灯亮着。 解题思路：枚举坐标系上的点。计算单个点亮着的概率，然后累加即使总体的期望。对于一个点x，y，z，分别考虑每维坐标系，比如x。选
日期 2023-06-12 10:48:40