2017 ACM-ICPC 亚洲区（南宁赛区）网络赛 A Weather Patterns(阅读理解)-蒲公英云

Weather Patterns

Consider a system which is described at any time as being in one of a set of NN distinct states, 1,2,3,…,N1,2,3,…,N. We denote the time instants associated with state changes as t = 1,2,…t=1,2,…, and the actual state at time tt as a_{ij}=p=[s_{i}=j\ |\ s_{i-1}=i], 1\le i,j \le Nai**j=p=[si=j ∣ si−1=i],1≤i,j≤N. For the special case of a discrete, first order, Markovchain, the probabilistic description for the current state (at time tt) and the predecessor state is s_{t}st. Furthermore we only consider those processes being independent of time, thereby leading to the set of state transition probability a_{ij}ai**j of the form: with the properties a_{ij} \geq 0ai**j≥0 and \sum_{i=1}^{N} A_{ij} = 1∑i=1NAi**j=1. The stochastic process can be called an observable Markovmodel. Now, let us consider the problem of a simple 4-state Markov model of weather. We assume that once a day (e.g., at noon), the weather is observed as being one of the following:

State 11: snow

State 22: rain

State 33: cloudy

State 44: sunny

The matrix A of state transition probabilities is:

A = \{a_{ij}\}= \begin{Bmatrix} a_{11}&a_{12}&a_{13}&a_{14} \\ a_{21}&a_{22}&a_{23}&a_{24} \\ a_{31}&a_{32}&a_{33}&a_{34} \\ a_{41}&a_{42}&a_{43}&a_{44} \end{Bmatrix}A={ ai**j}=⎩⎪⎪⎨⎪⎪⎧a11a21a31a41a12a22a32a42a13a23a33a43a14a24a34a44⎭⎪⎪⎬⎪⎪⎫

Given the model, several interestingquestions about weather patterns over time can be asked (and answered). We canask the question: what is the probability (according to the given model) thatthe weather for the next k days willbe? Another interesting question we can ask: given that the model is in a knownstate, what is the expected number of consecutive days to stay in that state?Let us define the observation sequence OOas O = \left \{ s_{1}, s_{2}, s_{3}, … , s_{k} \right \}O={ s1,s2,s3,…,sk}, and the probability of the observation sequence OO given the model is defined as p(O|model)p(O∣model). Also, let the expected number of consecutive days to stayin state ii be E_{i}Ei. Assume that the initial state probabilities p[s_{1} = i] = 1, 1 \leq i \leq Np[s1=i]=1,1≤i≤N. Bothp(O|model)p(O∣model) and E_{i}Ei are real numbers.

Input Format

Line 11~44 for the state transition probabilities. Line 55 for the observation sequence O_{1}O1, and line 66 for the observation sequence O_{2}O2. Line 77 and line 88 for the states of interest to find the expected number of consecutive days to stay in these states.

Line 11: a_{11}\ a_{12}\ a_{13}\ a_{14}a11 a12 a13 a14

Line 22: a_{21}\ a_{22}\ a_{23}\ a_{34}a21 a22 a23 a34

Line 33: a_{31}\ a_{32}\ a_{33}\ a_{34}a31 a32 a33 a34

Line 44: a_{41}\ a_{42}\ a_{43}\ a_{44}a41 a42 a43 a44

Line 55: s_{1}\ s_{2}\ s_{3}\ …\ s_{k}s1 s2 s3 … sk

Line 66: s_{1}\ s_{2}\ s_{3}\ …\ s_{l}s1 s2 s3 … sl

Line 77: ii

Line 88: jj

Output Format

Line 11 and line 22 are used to show the probabilities of the observation sequences O_{1}O1 and O_{2}O2 respectively. Line 33and line 44 are for the expected number of consecutive days to stay in states ii and jj respectively.

Line 11: p[O_{1} | model]p[O1∣model]

Line 22: p[O_{2} | model]p[O2∣model]

Line 33: E_{i}Ei

Line 44: E_{j}Ej

Please be reminded that the floating number should accurate to 10^{-8}10−8.

样例输入

0.4 0.3 0.2 0.1
0.3 0.3 0.3 0.1
0.1 0.1 0.6 0.2
0.1 0.2 0.2 0.5
4 4 3 2 2 1 1 3 3
2 1 1 1 3 3 4
3
4

样例输出

题意：这题一点都不难，一道英语阅读理解题，读懂了你就会做了！这道题其实就是每天会有四种天气，分别是①下雪②下雨③多云④晴天，然后给你一个4*4的矩阵，这个矩阵的第i行第j个表示的就是从天气i到天气j的概率，然后接下来给你两个观察序列，问你天气完全按照这个观察序列上的顺序变化的概率是多少，第一天是任何天气的概率都为1。接下来再给你两个数i和j，问连续数天都是i天气和j天气的数学期望分别是多少。

思路：对于任意一个观察序列，我们只要按序列的顺序把两个天气之间变化的概率不断地乘就可以得出答案，比如说题目中的第二个序列，2 1 1 1 3 3 4，那么a[2][1]*a[1][1]*a[1][1]*a[1][3]*a[3][3]*a[3][4]就是答案。对于数学期望，我们就是求连续1天是i天气的概率+连续2天是i天气的概率+……+连续n天是i天气的概率，虽然这个n是无限大的，但是当加到后面之后这个概率会非常小可以忽视，所以我们只需要加1000个差不多就够了。

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <string>  
#include <cstdlib>  
#include <cmath>  
#include <vector>  
#include <queue>  
#include <map>  
#include <algorithm>  
#include <set>  
#include <functional>  
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF = 1e9 + 5;
const int MAXN = 100000007;
const int MOD = 1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1.0);
LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a%b); }
double MA[5][5];
int main()
{
    double ans, res;
    int x, y;
    char ch;
    for (int i = 1; i <= 4; i++)
        for (int j = 1; j <= 4; j++)
            scanf("%lf", &MA[i][j]);
    ans = 1;
    getchar();
    y = -1;
    while (scanf("%d", &x))
    {
        if (y == -1)
        {
            y = x;
            continue;
        }
        else
        {
            ans *= MA[y][x];
            y = x;
        }
        ch = getchar();
        if (ch != ' ')
            break;
    }
    printf("%.8f\n", ans);
    y = -1;
    ans = 1;
    while (scanf("%d", &x))
    {
        if (y == -1)
        {
            y = x;
            continue;
        }
        else
        {
            ans *= MA[y][x];
            y = x;
        }
        ch = getchar();
        if (ch != ' ')
            break;
    }
    printf("%.8f\n", ans);
    scanf("%d", &x);
    ans = 0;
    res = 1;
    for (int i = 1; i <= 1000; i++)
    {
        ans += res;
        res *= MA[x][x];
    }
    printf("%.8f\n", ans);
    scanf("%d", &x);
    ans = 0;
    res = 1;
    for (int i = 1; i <= 1000; i++)
    {
        ans += res;
        res *= MA[x][x];
    }
    printf("%.8f\n", ans);
}