题目要读很久才能理解它的意思和笑点（如果你也看过那个笑话的话），读懂之后就会发现是一个高斯消元法的题目，对于我来说难点不在高斯消元，而在于字符串处理。先来说说题意吧：
总共有n个人，n个人都会有一段话，先是princess说话，里面如果提到了a1,a2,a3...这几个不同的人的话，对应提到的次数是x1,x2,x3..的话，那么下一个对话是ai这个人说的概率是xi/(x1+x2+x3)....，然后下一个人的对话里也会提到别的人，然后也有一定的概率会有下一轮对话，现在要问的就是，给定了这些对话，问你期望的对话次数是多少。
我们可以设第i个人持续的对话的期望是xi，那么xi应该等于 xi=p1*x1+p2*x2+p3*x3+...+1 对应的pi即为在该人对话出现的次数所对应的频率。然后对每个人列出这样的方程就会构成一系列的方程组。然后高斯消元即可。
难度在于算在某个对话里出现了多少次，因为像如何你用KMP去做匹配 prince是会出现在princess那里的，题目说了人名之间是用五种间隔符隔开的，所以匹配的时候或者匹配前将对话里的每一个词分出来，然后和对应的字符串判相等即可。我写的不好跪了好几发呀－ －0
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101 |
#pragma warning(disable:4996)#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<cmath>#include<vector>#define ll long long#define maxn 220#define eps 1e-7using
namespace std;char
str[120][1050];char
name[120][20];int
n;double
mat[120][120];char
word[1200];int
dcmp(double
x) { return
(x > eps) - (x < -eps);}int
cnt(char*T, char
*S){ int
res = 0; int
idx = 0; for
(int i = 0; T[i]; i++){ if
(!(T[i] <= ‘z‘&&T[i] >= ‘a‘)) continue; int
id = 0; while
(T[i] <= ‘z‘&&T[i] >= ‘a‘){ word[id++] = T[i++]; } word[id] = ‘\0‘; if
(strcmp(word, S) == 0) res++; i--; } return
res;}bool
gauss(double
mat[120][120], int
n){ for
(int i = 0; i < n; i++){ int
pivot = i; for
(int j = i; j < n; j++){ if
(abs(mat[j][i])>abs(mat[pivot][i])) pivot = j; } swap(mat[i], mat[pivot]); if
(abs(mat[i][i]) < eps) return
false; for
(int j = i + 1; j <= n; j++) mat[i][j] /= mat[i][i]; for
(int j = 0; j < n; j++){ if
(i != j) for
(int k = i + 1; k <= n; k++){ mat[j][k] -= mat[j][i] * mat[i][k]; } } } return
true;}int
main(){ while
(cin >> n) { getchar(); memset(name, 0, sizeof(name)); memset(str, 0, sizeof(str)); for
(int i = 0; i < n; i++){ gets(str[i]); int
j; for
(j = 0; str[i][j]; j++){ if
(str[i][j] == ‘:‘) break; name[i][j] = str[i][j]; } name[i][j + 1] = ‘\0‘; int
k = 0; j++; for
(; str[i][j]; j++,k++){ str[i][k] = str[i][j]; } str[i][k] = ‘\0‘; } memset(mat, 0, sizeof(mat)); for
(int i = 0; i < n; i++){ double
tot = 0; double
tmp = 0; for
(int j = 0; j < n; j++){ if
(i == j) continue; tmp = cnt(str[i], name[j]); mat[i][j] = tmp; tot += tmp; } mat[i][i] = -tot; mat[i][n] = -tot; if
(dcmp(tot) == 0){ mat[i][i] = mat[i][n] = -1; } } if
(gauss(mat, n)){ printf("%.3lf\n", mat[0][n]); } else
puts("Infinity"); } return
0;} |
ZOJ3560 Re:the Princess(高斯消元法),布布扣,bubuko.com
ZOJ3560 Re:the Princess(高斯消元法)
原文：http://www.cnblogs.com/chanme/p/3636716.html