题解 P2382 【化学分子式】

题目

不懂为什么，本蒟蒻用在线算法打就一直炸......

直到用了"半离线"算法......

一遍就过了好吗......

某位机房的小伙伴一遍就过了

另一位机房的小伙伴也是每次都爆零，还大叫"我再也不打这一题了"

嗯......真香！

【分析】

本蒟蒻看到题目的第一做法是考虑怎么储存元素的质量

假设我们把只由一个字母构成的元素符号看成后面补了一个空格

那么，每个元素都是由两位字符组成

其中第一位一定为大写，第二位一定为小写或空格

那么，也就是说，最多给定 \(26 \times 27 = 702\) 种不同的元素

因此，我们直接可以开一个数组 \(m_i\) 存各个元素的质量

根据上面的提示，显然，这边用27进制会比较 elegant 优雅

同时，我们可以在读入字符时加一个判定

读入完大写字符后，直接读入下一位

如果是空格，显然应该跳出

如果是小写，显然应该进制转换

根据题目，输入结束的标志为

"END_OF_FIRST_PART"

这是个很明显的标志，它的第二位也是大写

我们可以利用这个标志，判断什么时候读入部分结束

至于数字读入，可以参考读入优化的思路

这边加一条忠告 (过来人的语气) ：读到结束标志了记得吞掉整行

嗯，继续讲一下计算分子量的实现

这边本蒟蒻不懂为什么，按一边读入一边压栈一边算的在线算法打一直会出错(重点是本地测还没问题)，所以就用字符数组来存了......

我们用一个字符数组 (这里特地强调，不是字符串 string ，因为本蒟蒻觉得那个很耗时间) 来存化学式

接下来的运行跟读入其实差不多

不过，这边要加一个限制

如果出现括号，我们需要先计算括号内的值，再乘上括号的系数(在反括号后)

这边其实就是一个栈

一旦出现括号，说明要先算里面的，我就把之前算好的先放到栈里面

等对应的反括号出现，我们就可以直接算出这个括号描述的原子团的值

把这个值与系数的乘积加回上一层的栈里，就可以把这个括号解决了

那其他的细节就看一下本蒟蒻奇丑无比的代码吧

【代码】

那本蒟蒻就放代码了

#include<cstdio>

#include<cctype>

#include<cstring>

using namespace std;

int m[800]={0};

char s[100]={0};

inline int READ_NAME(char &c){

    register int ans=0; while(!isupper(c)) c=getchar();

    ans=c-'A'; c=getchar();

    if(islower(c)) ans+=(c-'a'+1)*26,c=getchar();

    return ans;

}//元素名读入

inline int READ_NUM(char &c){

    register int ans=0; while(!isdigit(c)) c=getchar();

    while(isdigit(c)) ans=(ans<<3)+(ans<<1)+c-'0',c=getchar();

    return ans;

}//数字读入

int READ_CHE(){

	int stack[80]={0},size=0,pos=0,len=strlen(s);

    //stack[i]表示第i层括号内的值

	while(pos<len){

			 if(!(s[pos]^'(')) stack[size++],pos++;

             //指针记得后移

		else if(!(s[pos]^')')){

			int tmp=0;

			if(!isdigit(s[pos+1])) tmp=1;

			while(isdigit(s[pos+1])) tmp=(tmp<<3)+(tmp<<1)+s[++pos]-'0';

            //读入优化类似代码

			pos++;

			stack[size-1]+=stack[size]*tmp;

			stack[size--]=0;

            //避免出现被(NH4)[Al(OH)4]卡掉的情况，虽然不知道是否存在这个物质

		}

		else if(isupper(s[pos])){

			int Tmp=s[pos]-'A';

			if(islower(s[pos+1])) Tmp+=(s[pos+1]-'a'+1)*26,pos++;

            //计算编码

			if(!m[Tmp]) return -1;

            //没读入到，直接返回"UNKNOWN"的指令

			int tmp=0;

			if(!isdigit(s[pos+1])) tmp=1;

			while(isdigit(s[pos+1])) tmp=(tmp<<3)+(tmp<<1)+s[++pos]-'0';

			pos++;

			stack[size]+=m[Tmp]*tmp;

		}

	}

	return stack[0];//返回第0层括号内的值

}//质量计算

inline void pre(){

    char c=getchar();

    while(1){

        int tmp=READ_NAME(c);

        if(isupper(c)){//读到结束语句

            while((c^'\n')&(c^'\r')) c=getchar();//吞掉整行

            return ;

        }

        m[tmp]=READ_NUM(c);

    }

}

int main(){

    pre();

    scanf("%s",s);

    while(s[0]^'0'){

        int tmp=READ_CHE();

        if(tmp>0) printf("%d\n",tmp);

        else puts("UNKNOWN");

        //读到未知元素会返回 -1

        memset(s,0,sizeof(s));

        //记得清零，避免被 H2O F2 卡掉

        scanf("%s",s);

    }

    return 0;

}

最后安利一下本蒟蒻的博客

巴特西

题解 P2382 【化学分子式】

【分析】

【代码】

最新文章

热门文章