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

亦凉 2022-06-08 11:39 207阅读 0赞

**Weather Patterns**

Consider a system which is described at any time as being in one of a set of N*N* 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 t*t* as a\_\{ij\}=p=\[s\_\{i\}=j\\ |\\ s\_\{i-1\}=i\], 1\\le i,j \\le N*a**i**j*=*p*=\[*s**i*=*j* ∣ *s**i*−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 t*t*) and the predecessor state is s\_\{t\}*s**t*. Furthermore we only consider those processes being independent of time, thereby leading to the set of state transition probability a\_\{ij\}*a**i**j* of the form: with the properties a\_\{ij\} \\geq 0*a**i**j*≥0 and \\sum\_\{i=1\}^\{N\} A\_\{ij\} = 1∑*i*=1*N**A**i**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*=\{ *a**i**j*\}=⎩⎪⎪⎨⎪⎪⎧*a*11*a*21*a*31*a*41*a*12*a*22*a*32*a*42*a*13*a*23*a*33*a*43*a*14*a*24*a*34*a*44⎭⎪⎪⎬⎪⎪⎫

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 O*O*as O = \\left \\\{ s\_\{1\}, s\_\{2\}, s\_\{3\}, ... , s\_\{k\} \\right \\\}*O*=\{ *s*1,*s*2,*s*3,...,*s**k*\}, and the probability of the observation sequence O*O* given the model is defined as p(O|model)*p*(*O*∣*m**o**d**e**l*). Also, let the expected number of consecutive days to stayin state i*i* be E\_\{i\}*E**i*. Assume that the initial state probabilities p\[s\_\{1\} = i\] = 1, 1 \\leq i \\leq N*p*\[*s*1=*i*\]=1,1≤*i*≤*N*. Bothp(O|model)*p*(*O*∣*m**o**d**e**l*) and E\_\{i\}*E**i* are real numbers.

### Input Format ###

Line 11~44 for the state transition probabilities. Line 55 for the observation sequence O\_\{1\}*O*1, and line 66 for the observation sequence O\_\{2\}*O*2. 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\}*a*11 *a*12 *a*13 *a*14

Line 22: a\_\{21\}\\ a\_\{22\}\\ a\_\{23\}\\ a\_\{34\}*a*21 *a*22 *a*23 *a*34

Line 33: a\_\{31\}\\ a\_\{32\}\\ a\_\{33\}\\ a\_\{34\}*a*31 *a*32 *a*33 *a*34

Line 44: a\_\{41\}\\ a\_\{42\}\\ a\_\{43\}\\ a\_\{44\}*a*41 *a*42 *a*43 *a*44

Line 55: s\_\{1\}\\ s\_\{2\}\\ s\_\{3\}\\ ...\\ s\_\{k\}*s*1 *s*2 *s*3 ... *s**k*

Line 66: s\_\{1\}\\ s\_\{2\}\\ s\_\{3\}\\ ...\\ s\_\{l\}*s*1 *s*2 *s*3 ... *s**l*

Line 77: i*i*

Line 88: j*j*

### Output Format ###

Line 11 and line 22 are used to show the probabilities of the observation sequences O\_\{1\}*O*1 and O\_\{2\}*O*2 respectively. Line 33and line 44 are for the expected number of consecutive days to stay in states i*i* and j*j* respectively.

Line 11: p\[O\_\{1\} | model\]*p*\[*O*1∣*m**o**d**e**l*\]

Line 22: p\[O\_\{2\} | model\]*p*\[*O*2∣*m**o**d**e**l*\]

Line 33: E\_\{i\}*E**i*

Line 44: E\_\{j\}*E**j*

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

#### 样例输出 ####

0.00004320
    0.00115200
    2.50000000
    2.00000000

**题意**：这题一点都不难，一道英语阅读理解题，读懂了你就会做了！这道题其实就是每天会有四种天气，分别是①下雪②下雨③多云④晴天，然后给你一个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);
    }