占位

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

#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;
}

设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.

咋没人贴题解呢……

共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)

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

这题难度为1？

娃哈哈 AC啦

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

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

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

果不其然，第8个挂了；

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

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

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

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

嘿嘿.

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

还有test 8 要cheat的....

if abs(f(m)-0.49947145877378436)

maa04

你的链接做的不对呀

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

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

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

另外，注意l=0的情况！这时要输出0！

(Invalid img)

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

此题题目描述要改，改为小数点后17位！

数据有一个点要改，增加1e-17！

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