概率

HDU 4015

题意：有两种蘑菇，好蘑菇捡到会加一点血，坏蘑菇捡到会掉ｍ点血，有m*k+1个好蘑菇和k个坏蘑菇随机排列，问按顺序吃蘑菇能活着的概率是多少。

看题解看了一会才看懂，刚开始看这个题就觉得使要算组合数然后除一下，结果完全不会算。。。换种思路，直接计算活着的占比，可以发现每一种活着的情况唯一对应m*k+k种死掉的情况，因为活着的排列做循环位移所得的排列必然不行（为啥不行？如果把序列分为两段，后一段移至开头，开头一段移至后面，本来的前一段的和必然是小于等于０的，因为后一段的和必然要大于０，不然就死了。。。然后这样移完之后必死）

ps:应该还要证明每一个序列的循环位移中必有一种合法，但是还没想清楚。。。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<functional>
#include<queue>
#include<set>
#include<cmath>
#include<utility>
#include<deque>
#include<cstdio>
using namespace std;
#define INF 0x7fffffff
#define pb push_back
typedef long long ll;
typedef pair<int,int> pii;
const int maxv=1e6+30;
const ll mod=1000000007;
int main(){
    ///freopen("in","r",stdin);
    //    freopen("out","w",stdout);
    int m,k,T,t=0;
    cin>>T;
    while(T--){
        t++;
        scanf("%d%d",&m,&k);
        printf("Case #%d: %.8f
",t,(double)1/(k+m*k+1));
    }
    return 0;
}

 Codeforces Round #335 (Div. 1) E - Intergalaxy Trips

题意:坐标轴上n个点,每个时刻可能存在一些通道,连接ij.走通道花费1个时间.也可以在原地等待.给出每个每个通道存在的概率,求从1到n的期望时间.

思路:每个点的期望可以表示为E[i]=A[i]*E[i]+B[i],其中A[i]是留在i点等的概率,B[i]是走到其他点的期望步数,每次松弛操作后更新E.

/*
* =.=
*/
#include <bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio (false);std::cin.tie(0)
#define pb push_back
#define PB pop_back
#define bk back()
#define fs first
#define se second
#define sq(x) (x)*(x)
#define eps (1e-6)
#define INF (0x3f3f3f3f)
#define clr(x) memset((x),0,sizeof (x))
#define cp(a,b) memcpy((a),(b),sizeof (b))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

const int maxn=1005;
int n;
double p[maxn][maxn];
long double E[maxn];
long double A[maxn],B[maxn];
bool vis[maxn];
int main(){
    //freopen("/home/slyfc/CppFiles/in","r",stdin);
    //freopen("/home/slyfc/CppFiles/out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%lf",&p[i][j]);
    E[n]=0;
    for(int i=1;i<n;i++) E[i]=1e20,A[i]=1;
    for(int k=0;k<n;k++){
        long double minv=1e20;
        int minp;
        for(int i=1;i<=n;i++) if(!vis[i]&&E[i]<minv)
            minv=E[i],minp=i;
        if(minp==1){
            printf("%.15f",(double)E[1]);
            return 0;
        }
        vis[minp]=1;
        for(int i=1;i<=n;i++) if(!vis[i]){
            B[i]+=E[minp]*A[i]*p[i][minp]*0.01;
            A[i]*=(1-p[i][minp]*0.01);
            if(A[i]<1-eps) E[i]=(1+B[i])/(1-A[i]);
        }
    }
    return 0;
}