ACM概率题

全栈程序员-站长 • 2026年3月18日下午5:09 • 未分类 • 阅读 2

2014多校第一场遇到两道概率题。。。直接跪了 WTF

hdu 4870 Rating

题目大意：

就是一个人参加比赛，有两个帐号，Rating的初始值都为0，每次选取Rating低的那个帐号参加比赛，直到有一个帐号的Rating为1000。每次比赛赢了加50，输了-100，如果得到的值为负取0。每次给出赢比赛的概率p，求有一个Rating等于1000的所需比赛场数的期望。

先考虑只注册一个帐号的情况（求的是初始e[0]，即0到20的期望，有e[20]=0）

而2个帐号的时候，由于每次取rating小的参赛，必然是这样的结果（0,0）=>（1,0）=>（1,1）=>（2,1）=>….=>（19,19）=>（20,19）

而t[k]表示的是一个帐号从0到达k的期望时间，所以答案为t[20]+t[19]。

代码比较容易：

#include 
    
      #include 
     
       #include 
      
        using namespace std; int main() { double p,t[25]; while(~scanf("%lf",&p)) { t[0]=0; t[1]=(double)(1.0/p); t[2]=(double)((double)1.0/p+(double)1.0/(p*p*1.0)); for(int i=3;i<25;i++) t[i]=1.0/p+t[i-1]*1.0/p-(1-p)/p*t[i-3]; printf("%lf\n",t[19]+t[20]); } return 0; }

这题还有高斯消元的方法。。。高斯消元还是没懂怎么赋值的也没搞太清楚。。还得看下线代书啊啊啊啊

/*思路：f(i, j)表示i >= j，第一个号i分，第二个号j分时候， 达到目标的期望，那么可以列出转移为 f(i, j) = p f(i', j') + (1 - p) f(i'' + j'') + 1 f(i', j')对应的是赢了加分的状态， f(i'', j'')对应输的扣分的状态，可以把50分当作一个单位， 一共有20 * 21 / 2 = 210个状态， 也就是对应了210个方程组，利用高斯消元去求解方程组，解出f(0, 0)就是答案*/ #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          //高斯消元 using namespace std; const double eps=1e-9; const int N=220; double p,a[N][N]; int mark[25][25]; double solve() { for(int i=0;i<210;i++) { int k=i; for(;k<210;k++) if(fabs(a[k][i])>eps) break; for(int j=0;j<=210;j++) swap(a[i][j],a[k][j]); for(int j=0;j<210;j++) { if(i==j) continue; if(fabs(a[j][i])>eps) { double x=a[j][i]/a[i][i]; for(int k=i;k<=210;k++) { a[j][k]-=a[i][k]*x; } } } } return a[0][210]/a[0][0]; } void init() { memset(a,0,sizeof(a)); for(int i=0;i<20;i++) { for(int j=0; j

ZOJ 3415 ZhouYu

这题是给牌的数量因为取的概率是一样的所以取到符合要求的概率是1/m 这题是求从n分到0分的期望

递推公示差不多但是要分m与2的关系总的求下来的过程很复杂。。。不再推导。。。

给个参考的网址http://files.cnblogs.com/lijunle/zju3415.pdf

代码蛮简单的就是用到了double类型的快速幂运算。。

#include           #include             using namespace std; double dpow(double a,int n) { double res=1.0; while(n) { if(n&1) res*=a; a*=a; n>>=1; } return res; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { if(m==2) printf("%.10lf\n",1.0*n*(n+1)); else { double ans=1.0*m/(1.0*(m-2)*(m-2)); double tmp=dpow((double)(1.0/(1.0*(m-1))),n)+1.0*n*(m-2)-1; printf("%.10lf\n",ans*tmp); } } return 0; }

//待续欢迎评论给点建议。。。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/214026.html原文链接：https://javaforall.net