其实zoj 3415不是应该叫Yu Zhou吗。。。碰到ZOJ 3415之后用了第二个参考网址的方法去求通项,然后这次碰到4870不会搞。参考了chanme的,然后重新把周瑜跟排名都反复推导(不是推倒)四五次才上来写这份有抄袭嫌疑的题解。。。
这2题很类似,多校的rating相当于强化版,不过原理都一样。好像是可以用高斯消元做,但我不会。默默推公式了。
公式推导参考http://www.cnblogs.com/chanme/p/3861766.html#2993306
http://www.cnblogs.com/lijunle/archive/2010/10/09/1846577.html
各有不同,现在感觉第一个比较好理解。
HDU 4870 Rating
先考虑只注册一个帐号的情况(求的是初始e[0],即0到20的期望,有e[20]=0)
e[0] = p*e[1]+(1-p)*e[0] +1 ==> e[0] = e[1] +1/p
e[1] = p*e[2]+(1-p)*e[0] +1 ==> e[0] = e[2] +1/p+1/(p*p)
e[2] = p*e[3]+(1-p)*e[0] +1
e[n-1] = p*e[n]+(1-p)*e[n-3]+1
e[n] = 0
显然,可以知道,e[0] = e[k] + t[k]。(因为每一次代入后,e[0]跟e[k]都会是乘上系数p)
代入一般情况下的,e[k] = p*e[k+1]+(1-p)*e[k-2]+1,-t[k] = p*(-t[k+1])+(1-p)*(-t[k-2])+1
所以有了t[0]=0,t[1]=1/p,t[2]=1/(p*p)以及t[k],t[k+1],t[k-2]的关系,可以求出所有t[i]
而2个帐号的时候,由于每次取rating小的参赛,必然是这样的结果(0,0)=>(1,0)=>(1,1)=>(2,1)=>....=>(19,19)=>(20,19)
而t[k]表示的是一个帐号从0到达k的期望时间,所以答案上t[20]+t[19]。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std; int main(){
double p,t[];
while(~scanf("%lf",&p)){
t[]=,t[]=./p,t[]=./p+./(p*p);
for(int i=;i<=;++i) t[i] = (./p+./p*t[i-]-(-p)/p*t[i-]);
printf("%.6lf\n",t[]+t[]);
}
return ;
}
虽然觉得写完之后跟参考的非常非常非常……非常非常非常类似。。。
ZOJ 3415 Zhou Yu
(求的是初始e[n],即n到0的期望,有e[0]=0)
类似的方法,不想打推导过程了。。。
#include <cstdio>
#include <iostream>
using namespace std; double pp(double a,int n){
double ret=;
while(n){
if(n&) ret *= a;
a*=a;
n>>=;
}
return ret;
}
int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
if(m==){printf("%.10lf\n",.*n*(n+));continue;}
double ans = .*m/(m-)/(m-);
double tmp = pp(./(m-),n) + .*n*(m-) - ;
printf("%.10lf\n",ans*tmp);
}
return ;
}