[POJ 1487] | Eurce's Blog

还是高斯消元法。

这题的特点是输入是用树来表示的，并且需要做类似编译原理那样的词法和语法分析。处理字符的时候小心一点，问题不会太大（但还是被负数的’-‘阴到了。。）。用递归来表示每个括号的匹配情况，符号移到等式右端（取负），数值直接累加，递归返回时每个值除去子树规模再累加到父节点数组上即可。由于输入规模不大，除了字符串处理也没有其他麻烦了。

解线性方程组的时候，注意每个方程已经指定了主元了，如果系数为0即对应变量无解，所有依赖于该变量的其他变量也无解。但其他剩余有解的变量还是要解出来的。这题比之前那题取模的要好处理，方程比较整齐，而且可以直接用浮点数。

#include<cstdio>
#include<cstring>

const double eps=1e-6;

int n,ml,t;
double ab[26][27],m[1000000],d[26];
char c,b[26];

inline double abs(double e)
{
    return e>0?e:-e;
}

int getint()
{
    int d=c-'0';
    while((c=getchar())>='0'&&c<='9')
        d=d*10+c-'0';
    return d;
}

void calc(double *f)
{
    ml+=n+1;
    double *e=&m[ml];
    int i,l=0;
    c=getchar();
    while(1)
    {
        while(c==' ')
            c=getchar();
        if(c==')') break;
        l++;
        if(c=='(') calc(e);
        else if(c=='-'||c>='0'&&c<='9')
        {
            if(c=='-')
            {
                c=getchar();
                e[n]-=getint();
            }
            else e[n]+=getint();
        }
        else if(c>='a'&&c<='z')
        {
            e[c-'a']-=1;
            c=getchar();
        }
    }
    for(i=0;i<=n;i++)
        f[i]+=e[i]/l;
    c=getchar();
}

void init()
{
    int i;
    ml=0;
    memset(ab,0,sizeof ab);
    memset(m,0,sizeof m);
    for(i=0;i<n;i++)
    {
        ab[i][i]=1;
        scanf("%*s%*s");
        while((c=getchar())!='(');
        calc(ab[i]);
    }
}

void solve()
{
    int i,j,k,l;
    double e,f;
    memset(b,0,sizeof b);
    printf("Game %d\n",++t);
    for(i=0;i<n;i++)
    {
        if(abs(ab[i][i])<eps)
        {
            b[i]=-1;
            continue;
        }
        for(j=i+1;j<n;j++)
        {
            if(abs(ab[j][i])<eps) continue;
            e=ab[j][i]/ab[i][i];
            for(k=i;k<=n;k++)
                ab[j][k]-=ab[i][k]*e;
        }
    }
    for(i=n-1;i>-1;i--)
    {
        if(b[i]==-1) continue;
        for(j=0;j<n&&!(abs(ab[i][j])>eps&&b[j]==-1);j++);
        if(j<n)
        {
            b[i]=-1;
            continue;
        }
        d[i]=ab[i][n]/ab[i][i];
        for(j=i-1;j>-1;j--)
        {
            if(abs(ab[j][i])<eps) continue;
            ab[j][n]-=ab[i][n]*ab[j][i]/ab[i][i];
            ab[j][i]=0;
        }
    }
    for(i=0;i<n;i++)
    {
        if(b[i]==-1)
            printf("Expected score for %c undefined\n",'a'+i);
        else
            printf("Expected score for %c = %.3f\n",'a'+i,d[i]);
    }
    puts("");
}

int main()
{
    while(~scanf("%d",&n)&&n)
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

#include<cstdio>

#include<cstring>

const double eps=1e-6;

int n,ml,t;

double ab[26][27],m[1000000],d[26];

char c,b[26];

inline double abs(double e)

{

return e>0?e:-e;

}

int getint()

{

int d=c-'0';

while((c=getchar())>='0'&&c<='9')

d=d*10+c-'0';

return d;

}

void calc(double *f)

{

ml+=n+1;

double *e=&m[ml];

int i,l=0;

c=getchar();

while(1)

{

while(c==' ')

c=getchar();

if(c==')') break;

l++;

if(c=='(') calc(e);

else if(c=='-'||c>='0'&&c<='9')

{

if(c=='-')

{

c=getchar();

e[n]-=getint();

}

else e[n]+=getint();

}

else if(c>='a'&&c<='z')

{

e[c-'a']-=1;

c=getchar();

}

for(i=0;i<=n;i++)

f[i]+=e[i]/l;

c=getchar();

}

void init()

{

int i;

ml=0;

memset(ab,0,sizeof ab);

memset(m,0,sizeof m);

for(i=0;i<n;i++)

{

ab[i][i]=1;

scanf("%*s%*s");

while((c=getchar())!='(');

calc(ab[i]);

}

void solve()

{

int i,j,k,l;

double e,f;

memset(b,0,sizeof b);

printf("Game %d\n",++t);

for(i=0;i<n;i++)

{

if(abs(ab[i][i])<eps)

{

b[i]=-1;

continue;

}

for(j=i+1;j<n;j++)

{

if(abs(ab[j][i])<eps) continue;

e=ab[j][i]/ab[i][i];

for(k=i;k<=n;k++)

ab[j][k]-=ab[i][k]*e;

}

for(i=n-1;i>-1;i--)

{

if(b[i]==-1) continue;

for(j=0;j<n&&!(abs(ab[i][j])>eps&&b[j]==-1);j++);

if(j<n)

{

b[i]=-1;

continue;

}

d[i]=ab[i][n]/ab[i][i];

for(j=i-1;j>-1;j--)

{

if(abs(ab[j][i])<eps) continue;

ab[j][n]-=ab[i][n]*ab[j][i]/ab[i][i];

ab[j][i]=0;

}

for(i=0;i<n;i++)

{

if(b[i]==-1)

printf("Expected score for %c undefined\n",'a'+i);

else

printf("Expected score for %c = %.3f\n",'a'+i,d[i]);

}

puts("");

}

int main()

{

while(~scanf("%d",&n)&&n)

{

init();

solve();

}

return 0;

}

另外这题也是我在POJ上有记录的第200题，貌似里面夹杂的水题不少。。。但还是值得纪念：