由于快要交概率论文了，先刷刷概率题，然后糊弄一篇上去就算了= =
自己挂了一场概率比赛，链接为http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=17303#overview，密码为yejinru
若以下有什么地方是错误的，欢迎指出^_^
| Problem A | Football |
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int X = 130;
double dp[8][X];
double a[X][X];
int main(){
freopen("sum.in","r",stdin);
int h;
while(cin>>h,h!=-1){
int n = 1<<h;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%lf",&a[i][j]);
for(int i=0;i<n;i++)
dp[0][i] = 1;
for(int i=1;i<=h;i++){
for(int j=0;j<n;j++){
int len = 1<<(i-1);
int s = ((j>>(i-1))^1)<<(i-1);
//cout<<i<<" "<<j<<" "<<len<<" "<<s<<endl;
dp[i][j] = 0;
for(int k=s;k<s+len;k++)
dp[i][j] += dp[i-1][k]*a[j][k];
dp[i][j] *= dp[i-1][j];
}
}
int pos = 0;
for(int i=0;i<n;i++)
if(dp[h][i]>dp[h][pos])
pos = i;
cout<<1+pos<<endl;
}
return 0;
}
| Problem H | HDU 3853 | LOOPS |
题目：
给出一幅二维格子地图，然后每次会有三种去向（消耗均为2），概率分别为pr(向右),pd(向下),p(原地)，现在某人从格子[1,1]出发，问到达[n,m]的期望消耗是多少
分析：
根据期望公式，不难想到期望公式如下: dp[i][j]表示从[i,j]出发到达[n,m]的期望消耗。
dp[i][j] = (dp[i][j]+2)*p[i][j]+(dp[i+1][j]+2)*pd[i][j]+(dp[i][j+1]+2)*pr[i][j];
由于等式右面有dp[i][j]，移项后即可解出答案dp[1][1]。注意当a[i][j] == 1时，该格子不能再往下走，所以得要特殊处理。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int X = 1005;
double d[X][X],r[X][X],a[X][X];
double dp[X][X];
int n,m;
int main(){
freopen("sum.in","r",stdin);
while(cin>>n>>m){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%lf%lf%lf",&a[i][j],&r[i][j],&d[i][j]);
memset(dp,0,sizeof(dp));
for(int i=n;i;i--)
for(int j=m;j;j--){
double temp = 0;
if(a[i][j]<1){
temp = (2+dp[i+1][j])*d[i][j]+(2+dp[i][j+1])*r[i][j]+2*a[i][j];
temp /= 1-a[i][j];
}
dp[i][j] = temp;
}
printf("%.3lf\n",dp[1][1]);
}
return 0;
}
| Problem K | UVA 11021 | Tribles |
题目：
第一天的时候，有k个小鸟（Trible），她只能活一天，在她死之前，生下i个小鸟的概率为p[i]，问第m天（包括m天之前）全死亡的概率。（小鸟最多能够生下n-1个后代）
分析：
独立概率问题，由于k只小鸟相互独立，所以求出一只小鸟以及她的后代在m天之内全死亡的概率dp[m]，答案就为dp[m]^k。
考虑：
m = 1，概率为p[0]，即没有生下后代
m = i，若第一天小鸟生下了i个后代的时候，即这i个小鸟得要在第i天都得死，这i个小鸟以及她们的后代只能够存活i-1天，有全概率公式，
dp[i] = p[0]+p[1]*f[i-1]+p[2]*f[i-1]^2+...+p[n-1]*f[i-1]^(n-1)
考虑p[j]*f[i-1]^j，表示第一天的小鸟生下了j个后代，要在i天全死，所以这j个后代又分别考虑，把第二天看成这j个小鸟的第一天，相当于子问题，然后得要在i-1天死亡，且j个小鸟相互独立，所以递推公式（dp[i] = p[0]+p[1]*f[i-1]+p[2]*f[i-1]^2+...+p[n-1]*f[i-1]^(n-1)）很容易想到了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int X = 1005;
double p[X],dp[X];
int n,k,m;
int main(){
//freopen("sum.in","r",stdin);
int ncase,cnt = 0;
cin>>ncase;
while(ncase--){
cin>>n>>k>>m;
for(int i=0;i<n;i++)
cin>>p[i];
dp[0] = 0;
dp[1] = p[0];
for(int i=2;i<=m;i++){
dp[i] = p[0];
for(int j=1;j<n;j++)
dp[i] += p[j]*pow(dp[i-1],j);
}
dp[m] = pow(dp[m],k);
printf("Case #%d: %.7lf\n",++cnt,dp[m]);
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define debug puts("here");
int s1,s2,t1,t2;
double tot;
double area(int w){
int lc = t1+w;
int rc = t2+w;
int uc = s2-w;
int dc = s1-w;
if(lc>=s2)
return tot;
if(rc<=s1)
return 0;
bool okl = (lc>=s1)&&(lc<=s2);
bool okd = (dc>=t1)&&(dc<=t2);
bool okr = (rc>=s1)&&(rc<=s2);
bool oku = (uc>=t1)&&(uc<=t2);
if(okl&&oku)
return tot-(uc-t1)*(s2-lc)*0.5;
if(okl&&okr)
return ((lc-s1)+(rc-s1))*(t2-t1)*0.5;
if(okd&&oku)
return ((t2-uc)+(t2-dc))*(s2-s1)*0.5;
if(okd&&okr)
return (t2-dc)*(rc-s1)*0.5;
return 0;
}
int main(){
freopen("sum.in","r",stdin);
int ncase,cnt = 0;
int w;
cin>>ncase;
while(ncase--){
cin>>t1>>t2>>s1>>s2>>w;
tot = (t2-t1)*(s2-s1);
double ans = area(w)-area(-w);
ans /= tot;
printf("Case #%d: %.8lf\n",++cnt,ans);
}
return 0;
}
| Problem M | UVA 11762 | Race to 1 |
题目：给出一个数n，从不大于n的数中随机选择一个素数，若该数是n的因子p的时候，可以转化为n/p的形式，否则n不变，现在给出n，问他能够转化为1的期望次数
分析：这题可以看做一个随机状态转换机，每个不大于n的素数都是一个等概率事件，根据全期望公式，不难发现递推关系如下：
dp[x] = 1+dp[x]*( (sum[x]-p[x])/sum[x] )+∑ (dp[x/y] / sum[x] ),y为x的素数因子。
1表示为已经转移了一次，若随机选出的不是x的素因子，则x不变化，所以有dp[x]*( (sum[x]-p[x])/sum[x] )，若y为x的素因子，转化为∑ (dp[x/y] / sum[x] )
算法的实现：利用记忆化搜索即可实现该算法。先利用略为修改过的筛法，把不大于x的素数的个数统计出来，以及把x的素数因子存在二维数组里（注意到2*3*5*7*11*13*17*19>1000000），所以第二维可以开到9就行了。另外对于每次求过了的dp[x]，不用再次求出（对于所有的测试数据都一样~~）
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
const int X = 1000002;
int use[X];
int sum[X];
int p[X];
int div[X][9],top[X];
int n;
double dp[X];
void init(){
memset(use,0,sizeof(use));
memset(top,0,sizeof(top));
for(int i=2;i<X;i++){
if(use[i])
sum[i] = sum[i-1];
else{
top[i] = 1;
div[i][0] = i;
sum[i] = sum[i-1]+1;
for(int j=i+i;j<X;j+=i){
use[j] = true;
div[j][top[j]++] = i;
}
}
}
}
double f(int x){
if(use[x])
return dp[x];
use[x] = true;
if(x==1)
return dp[x] = 0;
double ans = sum[x];
for(int i=0;i<top[x];i++)
ans += f(x/div[x][i]);
return dp[x] = ans/top[x];
}
int main(){
freopen("sum.in","r",stdin);
init();
int ncase,cnt = 0;
cin>>ncase;
memset(use,false,sizeof(use));
while(ncase--){
cin>>n;
printf("Case %d: %.10lf\n",++cnt,f(n));
}
return 0;
}