当前位置：首页 > news >正文

2019 ICPC Greater New York Region C - PassTheBuck（概率）

news 来源：原创 2024/5/10 19:44:47

题目链接

题目大意

n个人开始传球，每次要么把球传递给相邻的人，要么自己保留（保留就会赢得游戏），现在需要求给定传球的起点，问终点的人获胜的概率

解题思路

第一次做概率题就被这种无限传递的情况给吓住了，但是看了看题解，实际上就是当某轮的概率小于 $1e^{-8}$ 时直接结束游戏即可。设置两个数组，一个表示当前轮每人得到球的概率，另一个表示下一轮每个人得到球的概率，然后第一个数组每轮结束后更新为第二个数组，再清空第二个数组开始下一轮游戏即可

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

bool G[50][50]={ 0 };
int degree[50]={ 0 };
int n,m,num;

double solve(int u,int v){
    double ans=0.0,roud=0.0,cur[25],nxt[25];
    for(int i=0;i<21;i++) cur[i]=nxt[i]=0.0;
    cur[u]=1.0;  //初始只有起点的人有球，概率为1
    while(roud==0.0 || roud>eps){  //第一次roud为0，后面不会为0，这里相当于特判
        ans+=roud;
        roud=0.0;
        for(int i=0;i<=n;i++) nxt[i]=0.0;
        for(int i=1;i<=n;i++){
            if(cur[i]>0.0){
                for(int j=1;j<=n;j++)
                    if(G[i][j]){  //能传递就传
                        if(i==j){ //终点的人传给本身才更新答案，其他人不能传给自己不然会导致游戏结束
                            if(i==v) roud+=cur[i]/(double)degree[i];
                        }else nxt[j]+=cur[i]/(double)degree[i];
                    }
            }
        }
        for(int i=0;i<21;i++) cur[i]=nxt[i];  //更新此轮每人得到球的概率
    }
    return ans;
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int x,kase,u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&num);
        degree[i]=num+1;
        while(num--){
            scanf("%d",&x);
            G[i][x]=G[x][i]=1;
        }
        G[i][i]=1;
    }
    while(m--){
        scanf("%d%d%d",&kase,&u,&v);
        //cout<<solve(u,v)<<endl;
        printf("%d %.5f\n",kase,solve(u,v));
    }
    return 0;
}