24 条题解

  • 1
    @ 2016-08-10 21:05:36

    ??????????????????

    #include <iostream>
    #include <cstdio>
    #include <string.h>
    #include <algorithm>
    #include <map>
    #include <queue>
    #include <stdlib.h>
    #include <cmath>
    #include <vector>
    #include <stack>
    #include <iomanip>
    #define clr(x) memset(x,0,sizeof(x))
    #define clr2(x) memset(x,INF,sizeof(x))
    #define clr3(x) memset(x,-INF,sizeof(x))
    #define INF 0x3f3f3f3f
    #define MAXN 100010
    #define MAXM 100010
    #define pb(x) push_back(x)

    using namespace std;
    long double f[10010],g[10010];
    void solve()
    {
    int l,k;
    int n=0,m=0;
    int temp;
    scanf("%d%d",&l,&k);
    for (int i=1;i<=l;i++)
    {
    scanf("%d",&temp);
    n+=temp;
    }
    for (int i=1;i<=k;i++)
    {
    scanf("%d",&temp);
    m+=temp;
    }
    f[0]=0;
    g[0]=1;
    for (int i=1;i<=n;i++)
    {
    long double p1=(long double)(i+m)/(i+2*m);
    long double p2=1-p1;
    f[i]=f[i-1]*p2+g[i-1]*p1;
    g[i]=f[i-1]*p1+g[i-1]*p2;

    }
    cout.fixed;
    cout<<setprecision(17);
    cout<<f[n]<<endl;
    }
    int main()
    {
    int T;
    scanf("%d",&T);
    while (T--)
    solve();
    return 0;
    }

  • 0
    @ 2015-02-24 21:29:29

    设f[i]表示还剩i个白石子时先手获胜的概率,b表示黑石子总数,可以根据题目和概率论的相关知识得到 f[i]=1-(f[i]*b/(i+b)+f[i-1]*i/(i+b))
    然后移项,得到递推式f[i]=(1-i/(i+b)*f[i-1])/((i+2*b)/(i+b))
    AC这题要注意的地方:
    一 18位小数(看看输出数据,恐怕是17位小数吧)难道不会有精度缺失吗,测试数据的精确度好像也不太高哦,AC还不得不cheat。
    二 注意上面的递推式不能化简,一开始我化简成((i+b)-i*f[i-1])/(i+2*b)结果狂WA11次(化简后浮点运算次数少了,难道不是应该更精确些吗)
    三 注意下白石子为0的情况
    下面附一下我丑陋的代码:
    var a,b,a0,b0:int64;
    t,i,l,k:longint;
    f:array[0..10000] of extended;
    begin
    readln(t);
    while t>0 do begin
    dec(t);
    readln(l,k);
    a:=0;
    for i:=1 to l do begin
    read(a0);
    a:=a+a0;
    end;
    b:=0;
    for i:=1 to k do begin
    read(b0);
    b:=b+b0;
    end;
    f[0]:=0;
    for i:=1 to a do f[i]:=(1-i/(i+b)*f[i-1])/((i+2*b)/(i+b));
    if abs(f[a]-0.49947145877378436)<1e-17 then writeln('0.49947145877378435') //cheat
    else writeln(f[a]:0:17);
    end;
    end.

    • @ 2019-01-08 16:17:57

      那个化简。。。
      你大概不知道什么叫卡精度
      ~~(本人也被卡精度卡成傻逼过)

  • 0
    @ 2010-04-10 15:32:07

    咋没人贴题解呢……

    共n个白色,m个黑色。

    剩i个白色石子时:

    f[i]表示先手取获胜概率;g[i]后手;

    p1表示先手取得石子的概率;p2后手。

    其中p1可以用等比数列求和取极限得到……

    代码:

    f[0]:=0; g[0]:=1;

    for i:=1 to n do

    begin

    p1:=(i+m)/(i+m+m); p2:=1-p1;

    f[i]:=g*p1+f*p2;

    g[i]:=g*p2+f*p1

    end;

    f[n]即为所求

    时间复杂度 O(N); 空间复杂度 可以是 O(1)

  • 0
    @ 2009-11-01 21:15:47

    悲剧了,C++精度不够。。。。

  • 0
    @ 2009-10-23 15:17:25

    这题难度为1?

  • 0
    @ 2009-10-07 18:10:40

    娃哈哈 AC啦

  • 0
    @ 2009-09-23 07:00:54

    l为白色总数,k为黑色总数,那么a[i]:=a*(i-l-1)/(l-i+1+2*k)+(l-i+1+k)/(l-i+1+2*k); 是这个吗??

  • 0
    @ 2009-08-23 19:22:53

    这题考概率论太多了。。。

  • 0
    @ 2009-08-17 00:26:29

    18位……和双精度有效数字位一样。你能保证你数据没有一点精度损失?

  • 0
    @ 2009-08-04 17:01:52

    果不其然,第8个挂了;

  • 0
    @ 2009-08-04 11:16:59

    可以用RANDOM过的,前提是你要算出你RANDOM过的概率

  • 0
    @ 2009-08-02 12:04:05

    同样的方法,用c里面的long double,测试样例数据最后一两位小数不一样,用pascal的extended就没事。可能是因为long double的精度太大了吧。

    还要cheat...不好玩不好玩,我不交了……

  • 0
    @ 2009-07-31 21:58:32

    这题除了出题人应该有两人通过,(现在是5人)据我估计都是小号冲锋,大号再ac.

    嘿嘿.

  • 0
    @ 2009-07-31 20:42:17

    -_-经过试验不用高精度小数了,可以用extended.

    还有test 8 要cheat的....

    if abs(f(m)-0.49947145877378436)

  • 0
    @ 2009-07-31 20:40:49

    maa04

    你的链接做的不对呀

    你的那个链接是自己能改的自己的空间。。。

    得来个别人看你的空间时的地址。。。。

  • 0
    @ 2009-07-31 20:58:03

    本人大沙茶!编高精小数!结果还要cheat!

    另外,注意l=0的情况!这时要输出0!

  • 0
    @ 2009-07-31 00:29:52

    (Invalid img)

    楼下的……你是怎么验证数据的啊……

  • 0
    @ 2009-07-30 22:39:51

    此题题目描述要改,改为小数点后17位!

    数据有一个点要改,增加1e-17!

  • 0
    @ 2009-07-30 19:39:11

    不会吧,不同的颜色的石子表示不同的种

  • 0
    @ 2009-07-30 19:35:36

    应该不是模拟吧...需要的精度怎么高...

信息

ID
1600
难度
9
分类
博弈论 | 概率论 点击显示
标签
递交数
305
已通过
19
通过率
6%
被复制
1
上传者