2017 ACM-ICPC 亚洲区（南宁赛区）网络赛 A Weather Patterns

100 阅读 0 评论 66 点赞

我是靠谱客的博主开朗电源，最近开发中收集的这篇文章主要介绍2017 ACM-ICPC 亚洲区（南宁赛区）网络赛 A Weather Patterns，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Consider a system which is described at any time as being in one of a set of $N$ distinct states, $1, 2, 3, . . ., N$ . We denote the time instants associated with state changes as $t = 1, 2, . . .$ , and the actual state at time $t$ as $a_{ij}=p=[s_{i}=j | s_{i-1}=i], 1le i,j le N$ . For the special case of a discrete, first order, Markovchain, the probabilistic description for the current state (at time $t$ ) and the predecessor state is $s_{t}$ . Furthermore we only consider those processes being independent of time, thereby leading to the set of state transition probability $a_{ij}$ of the form: with the properties $a_{ij} geq 0$ and $sum_{i=1}^{N} A_{ij} = 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 $1$ : snow

State $2$ : rain

State $3$ : cloudy

State $4$ : sunny

The matrix A of state transition probabilities is:

${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}$

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

Input Format

Line $1$ ~ $4$ for the state transition probabilities. Line $5$ for the observation sequence $O_{1}$ , and line $6$ for the observation sequence $O_{2}$ . Line $7$ and line $8$ for the states of interest to find the expected number of consecutive days to stay in these states.

Line $1$ : $a_{11} a_{12} a_{13} a_{14}$

Line $2$ : $a_{21} a_{22} a_{23} a_{34}$

Line $3$ : $a_{31} a_{32} a_{33} a_{34}$

Line $4$ : $a_{41} a_{42} a_{43} a_{44}$

Line $5$ : $s_{1} s_{2} s_{3} ... s_{k}$

Line $6$ : $s_{1} s_{2} s_{3} ... s_{l}$

Line $7$ : $i$

Line $8$ : $j$

Output Format

Line $1$ and line $2$ are used to show the probabilities of the observation sequences $O_{1}$ and $O_{2}$ respectively. Line $3$ and line $4$ are for the expected number of consecutive days to stay in states $i$ and $j$ respectively.

Line $1$ : $p[O_{1} | model]$

Line $2$ : $p[O_{2} | model]$

Line $3$ : $E_{i}$

Line $4$ : $E_{j}$

Please be reminded that the floating number should accurate to $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

样例输出

题目来源

2017 ACM-ICPC 亚洲区（南宁赛区）网络赛

题意：先给你4 * 4 的矩阵，表示天气 i 到天气 j 转变的概率，然后输入 k 个数字，以 ‘n’ 表示输入结束，这 k 个数字的意思以

4 4 3 2 2 1 1 3 3

这组数字举例，其实就是天气从 4 转变为 4，然后从 4 转变为 3，然后从 3 转变为 2，然后从 2 转变为 2，然后从 2 转变为 1，然后从 1 转变为 1，然后从1 转变为 3，然后从3 转变为 3的概率是多少。

这样的输入数据有两组

然后输入两个数字 i 和 j ，这两个数字都表示天气的状况为 i 和 j 一直不变，不管天数增加多少，然后要你求一直不变的数学期望是多少。

附代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long LL;
///o(っ。Д。)っ AC万岁!!!!!!!!!!!!!!
const int maxn = 10;
double maps[maxn][maxn] = {};

int main()
{
for(int i = 1; i <= 4; i++)
{
for(int j = 1; j <= 4; j++)
{
scanf("%lf", &maps[i][j]);
}
}
double pp = 1.0;
int d1, d2;
char ch;
scanf("%d", &d1);
while(scanf("%d%c", &d2, &ch) != EOF)
{
pp *= maps[d1][d2];
d1 = d2;
if(ch == 'n') break;
}
printf("%.8lfn", pp);
pp = 1.0;
scanf("%d", &d1);
while(scanf("%d%c", &d2, &ch) != EOF)
{
pp *= maps[d1][d2];
d1 = d2;
if(ch == 'n') break;
}
printf("%.8lfn", pp);
scanf("%d", &d1);
pp = maps[d1][d1];
double sum = 0.0;
while(pp >= 0.000000001)
{
sum += pp;
pp *= maps[d1][d1];
}
printf("%.8lfn", sum + 1.0);
sum = 0.0;
scanf("%d", &d2);
pp = maps[d2][d2];
while(pp >= 0.000000001)
{
sum += pp;
pp *= maps[d2][d2];
}
printf("%.8lfn", sum + 1.0);
return 0;
}
/*

*/