KIDx的解题报告
?
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4418
?
题意:一个人在数轴上来回走,以pi的概率走i步i∈[1, m],给定n(数轴长度),m,e(终点),s(起点),d(方向),求从s走到e经过的点数期望
?
解析:设E[x]是人从x走到e经过点数的期望值,显然对于终点有:E[e] = 0
一般的:E[x] = sum((E[x+i]+i) * p[i])(i∈[1, m])?
(走i步经过i个点,所以是E[x+i]+i)
?
建立模型:高斯消元每个变量都是一个互不相同的独立的状态,由于人站在一个点,还有一个状态是方向!例如人站在x点,有两种状态向前、向后,不能都当成一种状态建立方程,所以要把两个方向化为一个方向从而使状态不受方向的影响
实现:
n个点翻过去(除了头尾两个点~~~)变为2*(n-1)个点,例如:
6个点:012345? --->? 0123454321
那么显然,从5开始向右走其实就是相当于往回走
然后方向就由两个状态转化成一个状态的,然后每个点就是只有一种状态了,对每个点建立方程高斯消元即可
?
bfs判断是否可以到达终点,顺便建立方程
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <queue> #include <algorithm> #include <math.h> using namespace std; #define M 205 #define eps 1e-8 int equ, var; double a[M][M], x[M]; int Gauss () { int i, j, k, col, max_r; for (k = 0, col = 0; k < equ && col < var; k++, col++) { max_r = k; for (i = k+1; i < equ; i++) if (fabs (a[i][col]) > fabs (a[max_r][col])) max_r = i; if (k != max_r) { for (j = col; j < var; j++) swap (a[k][j], a[max_r][j]); swap (x[k], x[max_r]); } x[k] /= a[k][col]; for (j = col+1; j < var; j++) a[k][j] /= a[k][col]; a[k][col] = 1; for (i = 0; i < equ; i++) if (i != k) { x[i] -= x[k] * a[i][k]; for (j = col+1; j < var; j++) a[i][j] -= a[k][j] * a[i][col]; a[i][col] = 0; } } return 1; } //has[x]表示人在x点时的变量号,因为我们只用可达状态建立方程,所以需要编号 int has[M], vis[M], k, e, n, m; double p[M], sum; int bfs (int u) { memset (has, -1, sizeof(has)); memset (a, 0, sizeof(a)); //忘记初始化WA勒,以后得注意 memset (vis, 0, sizeof(vis)); int v, i, flg = 0; queue<int> q; q.push (u); k = 0; has[u] = k++; while (!q.empty ()) { u = q.front (); q.pop (); if (vis[u]) continue; vis[u] = 1; if (u == e || u == n-e) //终点有两个,你懂的~ { a[has[u]][has[u]] = 1; x[has[u]] = 0; flg = 1; continue; } //E[x] = sum ((E[x+i]+i) * p[i]) // ----> E[x] - sum(p[i]*E[x+i]) = sum(i*p[i]) a[has[u]][has[u]] = 1; x[has[u]] = sum; for (i = 1; i <= m; i++) { //非常重要!概率为0,该状态可能无法到达,如果还去访问并建立方程会导致无解 if (fabs (p[i]) < eps) continue; v = (u + i) % n; if (has[v] == -1) has[v] = k++; a[has[u]][has[v]] -= p[i]; q.push (v); } } return flg; } int main() { int t, s, d, i; scanf ("%d", &t); while (t--) { scanf ("%d%d%d%d%d", &n, &m, &e, &s, &d); n = 2*(n-1); sum = 0; for (i = 1; i <= m; i++) { scanf ("%lf", p+i); p[i] = p[i] / 100; sum += p[i] * i; } if (s == e) { puts ("0.00"); continue; } //一开始向左,起点要变 if (d > 0) s = (n - s) % n; if (!bfs (s)) { puts ("Impossible !"); continue; } equ = var = k; Gauss (); printf ("%.2f\n", x[has[s]]); } return 0; }
?