不懂为什么，本蒟蒻用在线算法打就一直炸......
直到用了"半离线"算法......
一遍就过了好吗......
某位机房的小伙伴一遍就过了
另一位机房的小伙伴也是每次都爆零，还大叫"我再也不打这一题了"
嗯......真香！
【分析】
本蒟蒻看到题目的第一做法是考虑怎么储存元素的质量
假设我们把只由一个字母构成的元素符号看成后面补了一个空格
那么，每个元素都是由两位字符组成
其中第一位一定为大写，第二位一定为小写或空格
那么，也就是说，最多给定 \(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;
}
最后安利一下 本蒟蒻的博客