概率习题集（from kuangbin）

xiaoxiao2022-06-30 58

virtual judge中的kuangbin专题.链接:点击打开链接 .入口二：点击打开链接

分类浏览：

简单题：L.E.M

根据优惠劵收集原理：G.N

推导一元状态方程：A.B.C.C(1).F.K

推导多元状态方程：J.Q

需要特别优化：C(1)

概率dp：D.I.O

存在环只能用高斯消元：F.

剽悍的思路：H.J

状态压缩：K.O

P题没能完全理解

题意：n个门，每次从n个门中任选一个门，如果该门后面对应的值为负数ai，表示经过时间|ai|，又会回到原点。如果该门后面是正数，则表示经过时间ai后走出迷宫。经过多长时间t能走出迷宫，求该时间的期望。如果不可能走出迷宫输出inf。

解析：设当前走出该迷宫的期望为X。

x =∑ 1.0 / n * ai(ai > 0) + ∑1.0 / n * (x + ai) (ai < 0)

对该式子进行化简，假设正数的个数为p，解得： x =1.0 *( 正数和 + 负数绝对值和 )/ p

代码：另：需要判断如果都是负数则不可能走出迷宫

题意：你在点1，要走到点n。你选择扔骰子（六个面）的方法，投到多少走几步，但如果投的点数将走的超过点n，则要重新投骰子。每一点都有一个价值，走到该点就能获得，问走到终点时能获得的价值的期望。显然点1，点n 的价值是可以获得的。

解析：f(x)为从x点出发能获得的价值的期望。边界f(n) = an (边界可以不用）

f(x) = 1.0 / 6 * f(x + 1) + 1.0 / 6 * f(x + 2) + 1.0 / 6 * f(x + 3) + ……+1.0 / 6 * f(x + 6) + ax

当从该点出发可以到达超过点n时，假设可以走的方案有cnt 种

f(x) = 1.0 / 6 * f(x + 1) + ……+1.0 / 6 * f(x + cnt) + (6 - cnt) / 6.0 * f(x) + ax

整理后得到：f(x) = 1.0 / cnt * f(x + 1)+ ……+1.0 / cnt * f(x + cnt)

易知：cnt = n - x

代码： #include <iostream> #include <cstdio> #include <cstring> #include <sstream> #include <string> #include <algorithm> #include <list> #include <map> #include <vector> #include <queue> #include <stack> #include <cmath> #include <cstdlib> using namespace std; int a[105]; double dp[105]; bool vis[105]; int n; double dfs(int x) { //if(x == n) // return a[n]; if(vis[x] == true) return dp[x]; vis[x] = true; dp[x] = a[x]; int num = 6; if(6 + x > n) { num = n - x; } for(int i = 1; i <= num; i ++) { dp[x] += 1.0 / num * dfs(x + i); } return dp[x]; } int main() { //freopen("in.txt","r",stdin); int T; scanf("%d",&T); for(int t = 1; t <= T; t ++) { printf("Case %d: ",t); memset(vis,false,sizeof(vis)); scanf("%d",&n); for(int i = 1; i <= n; i ++) { scanf("%d",&a[i]); } double sum = 0; sum = dfs(1); printf("%f\n",sum); } return 0; }

C（pre 注意是另一道题）.题目链接：http://bak2.vjudge.net/problem/20869 uva11762

题意：我们都知道，任何一个整数都可以写成几个质数的乘积。那么我们将一个整数n，每次从所有小于等于n的素数中任选一个p，如果n能被该素数p整除，则n变为n/p.如果不能，则n不变。问将n变为1，需要选的次数的期望。

解析：f(x) 表示将x变为1，需要选的次数的期望是多少。其中n表示小于等于x的素数有几个

f(x) = ∑1.0 / n * f(x / i) (能被整除） + ∑ 1.0 / n * f(x)(不能被整除） + 1

整理后得到：f(x) = (∑f(x / i) + n) / k * 1.0

另：需要素数打表

此题时间复杂度较高时间为10s

代码：

#include <iostream> #include <cstdio> #include <cstring> #include <sstream> #include <string> #include <algorithm> #include <list> #include <map> #include <vector> #include <queue> #include <stack> #include <cmath> #include <cstdlib> using namespace std; typedef long long LL; double dp[1000005]; bool vis[1000005]; bool isPrime[2000005]; LL primeList[1000005],primeCount = 0; void primeInit(LL n) { memset(isPrime,true,sizeof(isPrime));//?????????? int m = sqrt(n + 0.5); for(int i = 2; i <= m; i ++) { if(isPrime[i])//????? { for(int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } for(int i = 2; i <= n; i ++) { if(isPrime[i]) { primeList[primeCount] = i; primeCount ++; } } } double dfs(int a) { if(a == 1) return 0.0; if(vis[a] == true) return dp[a]; double ans = 0.0; vis[a] = true; int p = 0,g = 0; while( p < primeCount) { if(primeList[p] > a) { break; } if(a % primeList[p] == 0) { ans += dfs(a / primeList[p]); g ++; } p ++; } if(g == 0) { return 0; } ans = (ans + p) / g; dp[a] = ans; return ans; } int main() { //freopen("in.txt","r",stdin); primeInit(2000000); int T; scanf("%d",&T); for(int t = 1; t <= T; t ++) { int x; scanf("%d",&x); //减少T大时候的复杂度，对相同n结果是确定的 // memset(vis,false,sizeof(vis)); // memset(dp,0,sizeof(dp)); double ans = dfs(x); printf("Case %d: %f\n",t,ans); } return 0; } C.(1)

题意：给定一个数N。从N的约数中任选一个i，另N = N / i问要进行这样操作期望的次数，使得N = 1。这里的约数从1到n

解析：先分析状态方程。设x要到1的期望为f(x)

f(x) = ∑1.0 / n * f(x/i) (i为x的约数) + 1.0 / n * f(x) + 1

整理后得：f(x) = 1.0 / (n - 1) * ∑f(x / i) + n / (n - 1) * 1.0

开始时利用记忆化搜索dp来写，但一直都TLE（3s，题目要求2s）

实际上该题还需要进一步化简，在求x的约数时可以只求到sqrt（x），如果一个数小于sqrt（x）且是x的约数，那么一定有一个与ta相乘为x，且大于sqrt的约数，如果这两个约数不想等，就把这两个因数都得f都加入到结果中。可以直接打表求。

另：注意求n/(n - 1)时要转化为double型。

代码：

题意：要求抢劫银行被抓住的概率小于p，银行的个数为n，没家银行都有Mi的钱，在该银行被捉住的概率为pi。求保证被抓住概率小于p时，最多能抢到多少钱。

解析：显然是dp。dp[x]表示抢劫x，被抓住的最小概率

dp[x] = dp[x - m[i]] + (1 - dp[x - m[i]]) * pi(在保证dp[x - m[i]] + (1 - dp[x - m[i]]) * pi < p的前提下）

外层循环从0到n - 1.内层循环钱数从最大值到最小值（保证x - m[i] 的结果是上一层循环的，而不是这一层循环所产生的，其实是二维ｄｐ的简化。）

代码：注意初始化ｄｐ均为１（一定会被抓住）dp[0] = 0没抢一定没被抓住

题意：一年有n天，问至少有多少个人，才能保证有人生日在同一天的概率大于等于0.5

解析：假设有x个人，那么所有人生日不在一天的概率P为

分母：n * n * n * n(x个n）

分子：n * (n - 1) *……*(n - x + 1)

有分子分母项数的个数是一样的。对应相除即可求解。枚举人数x使得 1 - P >= 0.5。

优化：每增加一个人实际上只是多成一项 n / （n - x + 1）

代码：

F.（此题理解不够深刻）

题意：首先有100个格子，你在第一个格子，要去第100个格子。扔骰子（6面的），投几走几，如果超过100就重新投。另外给出n个点有两个坐标（a,b）如果你到达了a点就会无条件的传输到b点。（可以从数值大的点传达小点，反之也是）问从1 - 100 扔骰子次数的期望。

解析：考虑在没有传输的情况下。与b题类似

设f（x）为从x点走到100点扔骰子的期望

当x不会超出边界时：

f(x) = 1.0 / 6 * f(x + 1) + 1.0 / 6 * f(x + 2) + 1.0 / 6 * f(x + 3) + ……+1.0 / 6 * f(x + 6) + 1

当从该点出发可以到达超过点n时，假设可以走的方案有cnt 种

f(x) = 1.0 / 6 * f(x + 1) + ……+1.0 / 6 * f(x + cnt) + (6 - cnt) / 6.0 * f(x) +1

整理后得到：f(x) = 1.0 / cnt * f(x + 1)+ ……+1.0 / cnt * f(x + cnt) + 6.0 / cnt

但是啊因为可以来回传输，就一定会有环。所以只能用高斯消元来求解方程组，那么方程组是什么呢

对于每个点来说方程为下面的二选一

1.f(x) = 1.0 / cnt * f(x + 1)+ ……+1.0 / cnt * f(x + cnt) + 6.0 / cnt

f(x) - 1.0 / cnt * f(x + 1)+ ……+1.0 / cnt * f(x + cnt) = 6.0 / cnt

代码中写的是

cnt * (x) - f(x + 1)+ ……f(x + cnt) = 6.0

cnt = n - x.if(cnt > 6)cnt = 6

2.f(x) = f(b)

f(x) - f(b) = 0

一共有100个方程，但由于模板是从1开始的，从0 - equ - 1固传入的数字应为101

一共有101个变量。高斯消元中的变元是包括常数的。模板中的变量是从0 - var

代码：（列方程+ 套模板）

#include<stdio.h> #include<algorithm> #include<iostream> #include<string.h> #include<math.h> using namespace std; const int MAXN=200; int mapp[MAXN]; const int maxn=1002; const double eps=1e-12; double a[maxn][maxn]; double x[maxn];//解集 bool free_x[maxn]; int n; int sgn(double x) { return (x>eps)-(x<-eps); } // 高斯消元法解方程组(Gauss-Jordan elimination).(0表示无解，1表示唯一解，大于1表示无穷解，并返回自由变元的个数) int Gauss(int equ,int var) { int i,j,k; int max_r; // 当前这列绝对值最大的行. int col; // 当前处理的列. double temp; int free_x_num; int free_index; // 转换为阶梯阵. col=0; // 当前处理的列. memset(free_x,true,sizeof(free_x)); for(k=0; k<equ&&col<var; k++,col++) { max_r=k; for(i=k+1; i<equ; i++) { if(sgn(fabs(a[i][col])-fabs(a[max_r][col]))>0) max_r=i; } if(max_r!=k) { // 与第k行交换. for(j=k; j<var+1; j++) swap(a[k][j],a[max_r][j]); } if(sgn(a[k][col])==0) { // 说明该col列第k行以下全是0了，则处理当前行的下一列. k--; continue; } for(i=k+1; i<equ; i++) { // 枚举要删去的行. if (sgn(a[i][col])!=0) { temp=a[i][col]/a[k][col]; for(j=col; j<var+1; j++) { a[i][j]=a[i][j]-a[k][j]*temp; } } } } for(i=k; i<equ; i++) { if (sgn(a[i][col])!=0) return 0; } if(k<var) { for(i=k-1; i>=0; i--) { free_x_num=0; for(j=0; j<var; j++) { if (sgn(a[i][j])!=0&&free_x[j]) free_x_num++,free_index=j; } if(free_x_num>1) continue; temp=a[i][var]; for(j=0; j<var; j++) { if(sgn(a[i][j])!=0&&j!=free_index) temp-=a[i][j]*x[j]; } x[free_index]=temp/a[i][free_index]; free_x[free_index]=0; } return var-k; } for (i=var-1; i>=0; i--) { temp=a[i][var]; for(j=i+1; j<var; j++) { if(sgn(a[i][j])!=0) temp-=a[i][j]*x[j]; } x[i]=temp/a[i][i]; } return 1; } int main(void) { // freopen("in.txt", "r", stdin); //freopen("out.txt","w",stdout); int T; scanf("%d",&T); for(int t = 1; t <= T; t ++) { memset(mapp,0,sizeof(mapp)); memset(a,0,sizeof(a)); printf("Case %d: ",t); int n; scanf("%d",&n); int p,q; for(int i = 0; i < n; i ++) { scanf("%d%d",&p,&q); mapp[p] = q; } a[100][100] = 1,a[100][101] = 0; for(int i = 1; i < 100; i ++) { if(mapp[i] != 0) { a[i][i] = 1; a[i][mapp[i]] = -1; a[i][101] = 0; } else { int k = 0; for(int j = 1; j <= 6 && i + j <= 100; j ++) { a[i][i + j] = -1; k ++; } a[i][i] = k; a[i][101] = 6; } } Gauss(101,101); printf("%.16f\n",x[1]); } return 0; } G.

题意：假设一个骰子有n面，设扔x次能使得每面至少被扔到一次，求x的期望。

解析：可以直接观察找规律。但注意此题是有一类经典题目优惠劵收集问题：链接http://www.guokr.com/article/5583/

第一次扔骰子，想要扔到一个新的点数需要扔一次，第二次扔骰子，扔到新的点数的概率为（n - 1）/ n.那么需要扔骰子的期望数为n/ (n - 1) ，再扔骰子，需要扔骰子的期望数为n/(n - 2) ……直到最后一次扔骰子，扔到新的点数的概率为1 / n,需要扔 n / 1次

代码：

题意：你在一个岛上，岛上有老虎，鹿，还有你。另外有一下几条规则：1.如果你遇到老虎，老虎就会吃掉你。2.如果鹿遇到老虎，鹿会被老虎吃掉。3.如果鹿遇到鹿，相安无事4.如果你遇到鹿，你会杀死鹿，或者留下鹿。5.如果老虎遇到老虎，它们会同归于尽。每天两个生物将会相遇，如果老虎都死了，你将获救。如果遇到鹿，你要做出最佳的选择，求你存货的概率是多少

解析：此题的破题点在于与鹿的个数是没有关系的。因为鹿的出现只会增加轮数，对老虎是否会同归于尽没有任何影响。

如果老虎的个数是单数，人必死。如果老虎的个数为0，人比活。

每次从所有的老虎和人中选择两个，再从老虎中选择两个，直到没有老虎了

代码：

题意：题面很长。意思就是有n个yes / no,它们的总长度为s。根据这个能算出有多少个yes，多少个no。对于有确定个数的yes、no的每一种排列。比如

no yes no yes.每一个yes/no向后移一位，前面补yes

yes no yes no 这样对于这种排列就有四个是错的，求对于所有排列错误数的期望

解析：dp。dp[i][j][k],i表示前i个位置，j表示前i个位置有几个yes，k表示当前位置是yes还是no。0表示yes，1表示no.整体表示对于这种情况错误的期望数。

p表示的是第i个位置之后的位置是yes的可能性。p = (yes个数 - j） / (n - i)

q为no的可能性q = 1.0 - p

dp[i][j][0] = dp[i + 1][j + 1][0] * p + (dp[i + 1][j][1] + 1)* q;

dp[i][j][1] = (dp[i + 1][j + 1][0] + 1) * p + dp[i + 1][j][1] * q

最后的值为dp[1][1][0] + dp[1][0][1]分别表示第一个位置是yes，和no

由于存不下，第一位采用的是滚动数组。dp的第一维应当是从大到小的，第二维要注意保证yes的个数是合法的，既不能少于i - no的个数，也不能大于i，yes的个数

代码：

#include <iostream> #include <cstdio> #include <cstring> #include <sstream> #include <string> #include <algorithm> #include <list> #include <map> #include <vector> #include <queue> #include <stack> #include <cmath> #include <cstdlib> using namespace std; double dp[2][5005][2];//yes = 0,no = 1; int main() { //freopen("in.txt","r",stdin); int T; scanf("%d",&T); for(int t = 1; t <= T; t ++) { printf("Case %d: ",t); int n,s; scanf("%d%d",&n,&s); int x = s - 2*n,y = 3 * n - s ;//x表示yes的个数，y表示no的个数 memset(dp,0,sizeof(dp)); int cur = 1;//滚动数组，表示i == 1 时求出的值是存在dp[0]中单 if(n % 2 == 0) cur = 0; //dp[cur][x][0] = dp[cur][x][1] = 0; for(int i = n - 1; i >= 1; i --) { // cout<<cur<<endl; cur = cur ^ 1; for(int j = max(i - y, 0 ); j <= i&& j <= x; j++) { double p1 = 1.0 * (x - j) *1.0/ (n - i); double p2 = 1.0 - p1; dp[cur][j][0] = dp[cur ^ 1][j + 1][0] * p1 +( dp[cur ^ 1][j][1] + 1)* p2; dp[cur][j][1] = (dp[cur ^ 1][j + 1][0] + 1) * p1 + dp[cur ^ 1][j][1] * p2; } } printf("%f\n",dp[1][1][0] * x / n +( dp[1][0][1] + 1)* y / n); } return 0; } J.

题意：从长宽高分别为xyz中，先任选三个x1,y1,z1,再任选三个x2,y2,z2将min(x₁, x₂) ≤ x ≤ max(x₁, x₂),min(y₁, y₂) ≤ y ≤ max(y₁, y₂) andmin(z₁, z₂) ≤ z ≤ max(z₁, z₂).的灯全部打开。开始为全部关上。重复k轮。问开着灯的个数的期望。

解析：先求解出每个点的等开着的概率。设该点为a,b,c.选择的x为x1,x2.该点开灯的概率为：1.0 - x1,x2都选在该点左侧的概率（a - 1） * (a - 1) / (x * x) - 都选在该点右侧的概率（x - a） * (x - a) / (x * x) 。设每个点一次后被按到的概率为p。那么k轮后开着灯的概率为被按到的概率为奇数的概率。设按k次被按到的次数为奇数的概率为f(k) .被按到次数为偶数的概率为 g(k)。f(k) = f(k - 1) * ( 1 - p) + g(k - 1) * p.g(k) = g(k - 1) * (1 - p) + f(k -1) * p.f(1) = p,g(1) = 1 - p.f(k) + g(k) = 1

整理后可以得到：f(k) = f(k - 1) * ( 1 - 2*p) + p

另f(k) + C = (1 - 2p) * (f(k - 1) + C) (解出C= -1.0 / 2.0)

就得到了：f(k) = ( 1 - ( 1 - 2p) ^k) / 2.0;

将每个点的概率求出来，再乘以总共灯的个数。

代码：

题意：T组数据，n个顶点，m个边。之后是m条边，分别是两个顶点，和权值及跑过路径的时间（u,v,w）.坏人一开始在接点零处，坏人经过一个顶点后就不能再次回到那个顶点了。坏人可以走到有边和它相连，并且从该点出发可以经过所有未经过的点。假设这样的方案有p种。坏人还可以就在该点再呆5min。这样坏人选择每一种方案的概率为1/（1+p）如果没有顶点可以走的时候，坏人被警察抓住。求坏人被警察抓住所需时间的期望

解析：状态压缩 + dp。将每个点是否走过，用二进制压缩成一串零一序列。之后用dfs记忆化搜索，判断条件为状态是否为每个点都走过，如果都做过则返回true

状态方程为设从当前点和状态出发一共可以走的点数为cnt。从当前点和状态出发被警察抓住时间的期望为f（x）

f(x) = 1.0 / (cnt + 1) * (f(x) + 5.0) + ∑1.0 / (cnt + 1) * (wi + f(y))(从当前点可以到达的状态和位置）

整理后：f(x) = (∑ (wi + f(y)) + 5 ) / cnt

为什么是状态压缩呢？因为当前点是否能够遍历所有安全的点，与哪些点是已经遍历过的有关。也就是说要已知过去的状态才能推导当前的状态。即必须要存储当前状态

代码：

/*int t,n,m; double mp[maxn][maxn]; double dp[maxn][1<<maxn]; bool vis[maxn][1<<maxn]; //化简后的公式为dp[u] = 5 / cnt + (求和 map[u][i] + dp[i]) / cnt int dfs(int st,int u){//u是当前点.如st=0110，那么这个状态是去过1,2两个点的 if (st==(1<<n)-1){//如果已经去过了所有的点，表示从某点出发能到达所有的点 dp[u][st]=0; return 1; } if (vis[u][st]) return dp[u][st]>eps; int cnt=0; dp[u][st]=5; vis[u][st]=true; for(int i=0;i<n;i++) if (mp[u][i]&&dfs(st|(1<<i),i)&&(!(st&(1<<i)))){//最后一个条件判断当前点是否去过。 int st0=st|(1<<i); cnt++; dp[u][st]+=mp[u][i]+dp[i][st0]; } if (cnt){ dp[u][st]/=cnt; return 1; } dp[u][st]=0;//从某点出发不能到达所有的点 return 0; } int main(){ //input; scanf("%d",&t); for(int Case=1;Case<=t;Case++){ memset(dp,0,sizeof(dp)); memset(mp,0,sizeof(mp)); memset(vis,false,sizeof(vis)); scanf("%d%d",&n,&m); int u,v,w; while(m--){ scanf("%d%d%d",&u,&v,&w); mp[u][v]=mp[v][u]=1.0*w; } dfs(1,0); printf("Case %d: %.10lf\n",Case,dp[0][1]); } return 0; } */ #include <iostream> #include <cstdio> #include <cstring> #include <sstream> #include <string> #include <algorithm> #include <list> #include <map> #include <vector> #include <queue> #include <stack> #include <cmath> #include <cstdlib> using namespace std; double mapp[20][20]; double dp[20][1 << 16]; bool vis[20][1 << 16]; int n; double dfs(int u,int st) { if(st == (1 << n) - 1) { dp[u][st] = 0; return 1; } if(vis[u][st] == true) return dp[u][st]; dp[u][st] = 5.0; vis[u][st] = true; int cnt = 0; for(int i = 0; i < n; i ++) { if(mapp[u][i] != 0 && ( !(st & (1 << i))) && dfs(i,st | (1<<i)))//保证当前点之前是没有走过的，增加当前点dfs的结果不是零即可 { cnt ++; dp[u][st] += mapp[u][i] + dp[i][st | (1<<i)]; } } if(cnt != 0) { dp[u][st] /= cnt; return 1.0; } dp[u][st] = 0; return 0; } int main() { // freopen("in.txt","r",stdin); int T; scanf("%d",&T); for(int t = 1; t <= T; t ++) { printf("Case %d: ",t); memset(dp,0,sizeof(dp)); memset(mapp,0,sizeof(mapp)); memset(vis,false,sizeof(vis)); int m,u,v,w; scanf("%d%d",&n,&m); for(int i = 0; i < m; i ++) { scanf("%d%d%d",&u,&v,&w); mapp[u][v] = w * 1.0; mapp[v][u] = w * 1.0; } dfs(0,1); printf("%f\n",dp[0][1]); } return 0; } L.

题意：n个人扔球任意投入到m个框中，投k次。每个人每次将球投入到任意一个框中的概率为p（也就是说要对准一个框投入的概率为p）问投完后所有框中球的个数之和的期望。

解析：水题。一个人投一次投入到一个框中的球的期望为p，投入到m个框中依旧为p（框是任意的，投完加和）投k次期望为kp，n个人期望为nkp。简单相乘就行

代码：

题意：T组数据。n个点，m条边，S大小的数据，没一个大小的数据来回需要2*k的时间。m条边，每条边都有一个pi表示发送成功的概率。是双向边。如果发送失败则需要从新发送。每次发送每一个大小的无论成功与否都要耗费2 * k的时间。求发送数据从0点到n - 1最小的期望时间。

解析：因为要求的是最小的期望时间，首先要求出从0 到n - 1,发送成功概率最大的路。由于n较小利用floyd即可。发送一次成功的概率为p。那么对于一个数据大小的发送成功的期望时间为2 * k/ p，对于s大小的数据来说则是 2 * k * s / p

代码：

题意：n个棍子，一种棍子可以和其它的棍子区别开来，一种不能。每根棍子有一个重量。一个人每次选择一根棍子，为了使得每根棍子都至少被选择过一次，求棍子重量的期望。

解析：又见优惠劵收集问题。如果只有不能和其他棍子区别开来的棍子，那么棍子的期望是可以算出来的。

但此题是按照贡献的期望数来计算的，能区分开的棍子贡献的期望数为棍子的重量本身。

按照全部都是不能区分开，需要抽n * Hn次（Hn为调和级数），这些次数抽到的棍子重量的期望为n * Hn * (总重量）/ n,那么对于每根不可区分的棍子来说，对期望的贡献时间为Hn * 棍子的重量。而对于可以区分的期望只能为棍子的重量

思路实际上是认为所有的棍子都是抽到后放回的（不能区分开的），来求期望数。抽到之后，还能再抽。但在能区分开的棍子的期望时则只计算一次

代码：

题意：一套扑克54张牌，其中大小王为混子。问使得你手上每一种花色都大于等于给定数目，需要发多少张牌的期望。如果不可能，则输出-1 解析：概率dp + 状态压缩 + 记忆化搜索

dp[a][b][c][d][5][5] // 前4项分别表示未发给你的各种花色的数量。第五，六维 = 0 表示你没有大小王，1,2,3,4表示大小王被认为是这四种不同的花色

表示从当前状态开始达到要求状态还需要发牌的数量

dp[a][b][c][d][x1][x2] += dp[a - 1][b][c][d][x1][x2] * a / tot （另：b，c，d）

tot 为牌的总数，注意考虑是否有大小王

另外如果大小王还没有用，就要遍历让大小王等于四种花色中的期望数最小的一个

dp[a][b][c][d][x1][x2] += dp[a][b][c][d][i][x2] / tot (大小王只有一张牌所以 * 1.0 省略）

dp[a][b][c][d][x1][x2] += 1.0;//总排数加1

边界条件当你手上的各种牌已经满足条件了，返回零

将每个要求的牌数大于13的部分加起来如果大于2，则是违法的输出-1

代码:

#include <iostream> #include <cstdio> #include <cstring> using namespace std; double dp[20][20][20][20][5][5];//注意是double 类型的 int q[10]; int A,B,C,D; double dfs(int a,int b,int c,int d,int x1,int x2) { double ans= dp[a][b][c][d][x1][x2]; if(ans > 0) return ans; q[1] =13 - a,q[2] =13 - b,q[3] = 13 - c,q[4] = 13 - d; q[x1] ++,q[x2] ++; if(q[1] >= A && q[2] >= B && q[3] >= C &&q[4] >=D) return 0; int tot = a + b + c + d + (x1 == 0? 1:0) + (x2 == 0? 1 :0);//如果 x== 0表示王海没用过，总排数加1 if(a > 0) ans += 1.0 * a / tot * dfs(a - 1,b,c,d,x1,x2); if(b > 0)ans += 1.0 * b / tot * dfs(a,b - 1,c,d,x1,x2); if(c > 0)ans += 1.0 * c / tot * dfs(a,b,c - 1,d,x1,x2); if(d > 0) ans += 1.0 * d / tot * dfs(a,b,c,d - 1,x1,x2); if(x1== 0)//如果大小王还没用，就有概率抽到大小王，收到大王的概率为 1.0 /tot { double t = 100000; for(int i = 1; i <= 4; i ++) { t = min(t,dfs(a,b,c,d,i,x2)); } ans += 1.0 * t / tot; } if(x2== 0) { double t = 100000; for(int i = 1; i <= 4; i ++) { t = min(t,dfs(a,b,c,d,x1,i)); } ans += 1.0 * t / tot; } ans += 1.0; dp[a][b][c][d][x1][x2] = ans; return ans; } int main() { // freopen("in.txt","r",stdin); int T; scanf("%d",&T); for(int t = 1; t <= T; t ++) { printf("Case %d: ",t); scanf("%d%d%d%d",&A,&B,&C,&D); int cnt= 0;//注意计算的是超过13的总个数，没超过的不要加起来 if(A > 13) cnt+= A - 13; if(B > 13) cnt+= B - 13; if(C > 13) cnt+= C - 13; if(D> 13) cnt+= D - 13; if(cnt > 2) { printf("-1\n"); continue; } memset(dp,0,sizeof(dp)); printf("%.8f\n",dfs(13,13,13,13,0,0)); } return 0; } P.（完全且依旧不理解）（网上没题解啦(；′⌒`)）

题意：再见迷宫（很眼熟啦）区别就是你会记住你选择的过去的k 个门，而不会再打开，问走出迷宫的期望。

解析：题面的类似，和做法的不同。。。

首先还是要判断是否能走出去。然后dfs（cnt1,cnt2,t）三个参数分别是有cnt1个正数，cnt2个负数，和已经走了t步

一般情况下 return cnt1 / (cnt1 + cnt2) * av1 + (dfs(cnt1,cnt2 - 1,t + 1) + av2) * cnt2 / (cnt1 + cnt2)

如果cnt2<= 0 return av1

如果t >= k即已经记住了k个门了，不会再多了。那么此种情况和A题是一样的直接就能求出结果return 1.0 *(c1 * av1 + c2 * av2 )/ c1;

代码：

//注意两个整数相处得到一个double型要乘1.0 #include <iostream> #include <cstdio> #include <cstring> #include <sstream> #include <string> #include <algorithm> #include <list> #include <map> #include <vector> #include <queue> #include <stack> #include <cmath> #include <cstdlib> using namespace std; int k; int sum1 ,sum2 ; int cnt1,cnt2; double av1,av2 = 0; double dfs(int c1,int c2,int t) { if(c2 <= 0) return av1; if(t >= k) { return 1.0 *(c1 * av1 + c2 * av2 )/ c1; } return 1.0 * c1 /(c1 + c2) * av1 + 1.0 * c2/(c1 + c2) *(dfs(c1,c2 - 1,t + 1) + av2); } int main() { //freopen("in.txt","r",stdin); int T,a; scanf("%d",&T); for(int t = 1; t <= T; t ++) { printf("Case %d: ",t); int n; sum1 = 0,sum2 = 0,cnt1= 0,cnt2 = 0,av1 = 0,av2 = 0; scanf("%d%d",&n,&k); for(int i = 0; i < n; i ++) { scanf("%d",&a); if(a> 0) { sum1 += a; cnt1 ++; } else { sum2 += -1 * a; cnt2 ++; } } if(cnt1) av1 =1.0* sum1 / cnt1; if(cnt2) av2 =1.0 *sum2 / cnt2; if(cnt2 == n) { printf("-1\n"); } else { printf("%.8f\n",dfs(cnt1,cnt2,0)); } } return 0; } Q.(最初表示不够理解）中间推导公式不够理解

参照的题解：http://blog.csdn.net/yeyeyeguoguo/article/details/46446905，

http://blog.csdn.net/whyorwhnt/article/details/9904151

题意：投中求的概率为p.如果连续投不中球k1次，或连续投中球k2次练习结束，求投球数的期望

解析：f(i)表示连续投中i次后剩余投球个数的期望数，g(i)表示连续投不中i次的期望数，剩余投球个数的期望数

注意：求期望数别忘记加1

f(i) = f(i + 1) * p + g(1) * (1 - p) + 1

g(i) = g(i + 1) * ( 1 -p) + f(1) * p + 1

已知边界f(k2) = 0,g(k1) = 0

可以求出f(1),g(1)：推导过程

设x = g(1) * (1-p) + 1.不要按通解来求

f(i) = f(i + 1) * p + x.

f(k2) = 0,f(k2 -1) = x,f(k2 - 2) = p*x + x,f(k2 -3) = p * p * x + p *x + x

顾f(1) = p^k - 2 * x + p ^ k - 3 * x +……＋p ^ 0*x

f(1) = (1 - p^(k - 1)) / (1 - p) * （g(1) * (1-p) + 1）

求出g(1) 。两方程联立求解

f(0) = f(1) * p + g(1) * (1-p) + 1,g(0) = ……

最后答案为f(0) + g(0)

代码：

转载请注明原文地址: https://ju.6miu.com/read-1125654.html

专利

最新回复(0)