ZOJ3560 Re:the Princess(高斯消元法)

题目要读很久才能理解它的意思和笑点(如果你也看过那个笑话的话),读懂之后就会发现是一个高斯消元法的题目,对于我来说难点不在高斯消元,而在于字符串处理。先来说说题意吧:

总共有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

#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-7
using 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;
}
上一篇:[设计模式] javascript 之 代理模式


下一篇:Android下实现GPS定位服务