POJ1487 Single-Player Games 高斯消元

时间:2024-12-25 13:35:44

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解


题目传送门 - POJ1487


题解概括

   给出多个树形结构,由小写字母和数字表示,每个小写字母表示一棵小树。现在,以a为根节点,构建一棵大树,树可能是无限的。现在,一个人从树根往叶子走,直到无法走为止,得到该叶子结点上数值所表示的相应分数,人在分叉的地方走每条路的概率是一样的,求得分期望。


题解

  首先通过关系建立方程组。

  这个貌似很麻烦,但是很暴力,有码量没有难度。

  然后高斯消元解方程。

  要注意精度的问题。

  解的时候要标记*元。

  也有点麻烦。

  具体的看代码吧。


代码

#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
using namespace std;
typedef long double LD;
const LD Eps=1e-8;
const int N=30;
int n,Case=0,now,pos[N];
char str[300];
bool free_x[N];
LD a[N][N],x[N];
void GetLn(){
while (getchar()!='\n');
}
int Match_Pracket(int now){//now为当前要匹配的左括号位置。
int len=strlen(str+1),p=0;
for (int i=now;i<=len;i++){
if (str[i]=='(')
p++;
if (str[i]==')')
p--;
if (!p)
return i;
}
return -1;
}
bool Is_Num_Part(char ch){
return ch=='-'||('0'<=ch&&ch<='9');
}
int GetNum(int now,int &Next){//now为当前要计算的数字的最左位置,Next返回跳过数字后的位置。
int len=strlen(str+1),f=1,x=0;
if (str[now]=='-')
f=-1;
else
x=str[now]-'0';
while (Is_Num_Part(str[++now]))
x=x*10+str[now]-'0';
Next=now;
return x*f;
}
void dfs(int L,int R,LD p){
if (L>R)
return;
int tot=0,i;
for (i=L;i<=R;){
if (Is_Num_Part(str[i])){
int j,v=GetNum(i,j);
i=j,tot++;
continue;
}
if (str[i]=='('){
i=Match_Pracket(i)+1;
tot++;
continue;
}
if ('a'<=str[i]&&str[i]<='z'){
i++,tot++;
continue;
}
i++;
}
p=p/tot;
for (int i=L;i<=R;){
if (Is_Num_Part(str[i])){
int j,v=GetNum(i,j);
i=j,a[now][n]-=p*v;
continue;
}
if (str[i]=='('){
int j=Match_Pracket(i);
dfs(i+1,j-1,p);
i=j+1;
continue;
}
if ('a'<=str[i]&&str[i]<='z')
a[now][str[i]-'a']+=p;
i++;
}
}
int Gauss(){
memset(free_x,0,sizeof free_x);
memset(pos,0,sizeof pos);
int k,c;
for (k=c=0;k<n&&c<n;k++,c++){
int Mk=k;
for (int i=k+1;i<n;i++)
if (fabs(a[Mk][c])<fabs(a[i][c]))
Mk=i;
if (Mk!=k)
for (int i=c;i<=n;i++)
swap(a[Mk][i],a[k][i]);
if (fabs(a[k][c])<Eps){
k--;
free_x[c]=1;
continue;
}
pos[k]=c;
for (int i=k+1;i<n;i++)
if (fabs(a[i][c])>Eps){
for (int j=n;j>=c;j--)
a[i][j]=a[i][j]-a[k][j]/a[k][c]*a[i][c];
a[i][c]=0;
}
}
for (int i=k;i<n;i++)
if (fabs(a[i][n])>Eps)
return -1;
memset(x,0,sizeof x);
for (int i=k-1;i>=0;i--){
if (free_x[pos[i]])
continue;
LD tmp=a[i][n];
for (int j=pos[i]+1;j<n;j++){
if (fabs(a[i][j])<Eps)
continue;
if (free_x[j]){
free_x[pos[i]]=1;
break;
}
tmp-=a[i][j]*x[j];
}
if (!free_x[pos[i]])
x[pos[i]]=tmp/a[i][pos[i]];
if (fabs(x[pos[i]])<Eps)
x[pos[i]]=0;
}
return 0;
}
int main(){
while (~scanf("%d",&n)&&n){
GetLn();
memset(a,0,sizeof a);
for (now=0;now<n;now++){
a[now][now]-=1;
gets(str+1);
int pos=1;
while (str[pos]!='=')
pos++;
dfs(pos+1,strlen(str+1),1);
}
int ans=Gauss();
printf("Game %d\n",++Case);
for (int i=0;i<n;i++)
if (free_x[i])
printf("Expected score for %c undefined\n",i+'a');
else
printf("Expected score for %c = %.3Lf\n",i+'a',x[i]);
puts("");
}
return 0;
}