P2382 化学分子式

luogu的oier化学一定都很好

这个题是让我们模拟计算化学方程式的过程。

和时间复杂度类似的题目。

我们可以根据括号，将求解分成若干个步骤。

从外部看，需要将一对括号看做一个整体。然后进行计算。

从内部看，括号外面的下标对内部没有影响。

我们可以将给定的分子式，看做在一个大括号内。

然后写出一个函数，函数的作用就是求解某一个括号内的质量。

当然，这个函数很显然是递归的。递归就要用到栈。所以是隐形的开了栈。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

const int maxn=5000;

int T[maxn][100],tail;

int End[maxn];

char c[maxn];

void insert(char *A,int len,int w)

{

    int now=0;

    for(int i=1;i<=len;i++)

    {

        int nxt=A[i]-'A';

        if(!T[now][nxt])    T[now][nxt]=++tail;

        now=T[now][nxt];

    }//trie树

    End[now]=w;

    return ;

}

int get(int &now,int len)

{

    int res=0,R=T[0][c[now++]-'A'];

    while(c[now]>='a'&&c[now]<='z')//还在一个原子内

    {

        int nxt=c[now]-'A';

        if(!T[R][nxt])  return -0x7fffffff;

        R=T[R][nxt];

        now++;

    }

    if(!End[R]) return -0x7fffffff;//没有这个原子，返回非法

    return End[R];//返回单个原子的质量

}

int calc(int &now,int len)

{

    int res=0;

    while(c[now]<='9'&&c[now]>='0'&&now<=len)

    {

        res=res*10+c[now]-'0';

        now++;

    }//数字

    return res;

}

int dfs(int &now,int len)//

{

    int sum=0;//括号内原子的质量总和

    while(c[now]!=')'&&now<=len)//没有到右括号。PS：一次循环处理一个原子和其下标（若没有则不处理）

    {

        int pas=0,x=1;//pas为原子质量，x为下标

        if(c[now]=='(')//遇到一个左括号

            pas=dfs(++now,len);//递归处理

        else

        if(c[now]<'0'||c[now]>'9')

            pas=get(now,len);//计算原子质量

        if(c[now]==')'||pas<0)//后面没有下标而且到了右括号

        {

            sum+=pas;//加上，退出循环

            break;

        }

        if(c[now]>='0'&&c[now]<='9')

            x=calc(now,len);//计算下标

        sum+=pas*x;//相乘

    }

    now++;//越过右括号

    return sum;

}

int main()

{

    while(true)

    {

        int weight;

        scanf("%s",c+1);

        scanf("%d",&weight);

        int len=strlen(c+1);

        if(c[1]=='E'&&c[2]=='N'&&c[3]=='D') break;

        insert(c,len,weight);

    }//输入元素

    while(true)

    {

        scanf("%s",c+1);

        if(c[1]=='0')   break;//终止条件

        int len=strlen(c+1);//长度

        c[len+1]=')';//将整个分子式括号扩起来，只括右半部分的原因是，我写的函数，在所处理的括号的区间是左开右闭的。

        int n=1;

        int ans=dfs(n,len+1);

        if(ans<0)   printf("UNKNOWN\n");//不合法。

        else    printf("%d\n",ans);

    }//计算

}

附带：豪华大样例（当然可能有锅）

巴特西

P2382 化学分子式

luogu的oier化学一定都很好

最新文章

热门文章