题意:给定0~n(1<=n<=100000)个位置和m(0<=m<=1000)个传送门(从xi传送到yi xi<yi),到达xi一定会被传送到yi,
问从0通过掷骰子到达n点的掷骰子的期望。
题解:E[i] 表示到达 i 点的期望,P[i] 表示到达 i 点的概率,E[pos] += (E[i] + P[i]) * 1.0 / 6.0;P[pos] += P[i] * 1.0 / 6.0;即在当前位置到达的下一个位置是
以1.0 / 6.0的概率转移的。
Sure原创,转载请注明出处。
#include <iostream> #include <cstdio> #include <memory.h> using namespace std; const int maxn = 100002; const double unit = 1.0 / 6.0; int m,n; double E[maxn],P[maxn]; int next[maxn]; void read() { memset(E,0,sizeof(E)); memset(P,0,sizeof(P)); for(int i=0;i<=n;i++) { next[i] = i; } int u,v; for(int i=0;i<m;i++) { scanf("%d %d",&u,&v); next[u] = v; } return; } int find(int u) { return (u == next[u]) ? next[u] : (next[u] = find(next[u])); } void make() { for(int i=0;i<=n;i++) { next[i] = find(next[i]); } return; } void solve() { P[0] = 1.0; for(int i=0;i<n;i++) { for(int j=1;j<=6;j++) { int pos = i + j; if(pos > n) pos = n; pos = next[pos]; E[pos] += (E[i] + P[i]) * unit; P[pos] += P[i] * unit; } } printf("%.4f\n",E[n]); return; } int main() { while(scanf("%d %d",&n,&m) && n+m) { read(); make(); solve(); } return 0; }