ZZ大学的Dr.Kong最近发现实验室的很多试制品都已经用完。由于项目经费有限,为了节省,Dr.Kong决定利用实验室现有的试制品来生成所缺的试制品。为此,Dr.Kong连续几天通宵达旦整理出一份研究资料并让研究生Bill去实验并统计能产生多少种所缺的试制品。
Bill从头到尾翻完所有的资料,发现资料上写满了一大堆的化学方程式,上面除了大小写英文字母、数字、加号、等号外,再也没有其他的符号了。其中,每个方程式都是A1+A2+……+Ap=B1+B2+……+Bq的形式, 表示试制品A1,A2,……和Ap反应,生成了试制品B1,B2,……,Bq。其中Ai和Bj都是一种单质或化合物的化学式(长度不超过10个字符),1≤p,q ≤ 20 。每个方程式的总长不超过100个字符。有些试制品的化学式可能在现代社会的化学元素周期表里找不到,这是由于化学反应过程中可能又有物理反应导致的结果。
Bill头疼了,从哪个实验开始呢?你能帮助他吗?
- 输入
- 第一行:N表示Dr.Kong写的化学方程式个数(1<=N<=400)
接下来有N行, 每一行是一个方程式.
再接下来的一行:M表示已有多少种试制品.(1<=M<=500)
接下来有M行,每一行是已有的一种试制品的化学式. - 输出
- 第一行包含一个数T,表示可以产生多少种所缺的试制品.
在接下来的T行中,按ASCII码升序输出产生的试制品的化学式. - 样例输入
- 4
- H2O+Na=NaOH+H2
- Cl2+H2=HCl
- Fe+O2=Fe3O4
- NaOH+HCl=H2O+NaCl
- 3
- H2O
- Na
- Cl2
- 样例输出
4 H2 HCl NaCl NaOH
ac代码:
#include <iostream> #include<cstdio> #include<string> #include<cstring> #include<vector> #include<map> #include<algorithm> using namespace std; map<string,int>have; vector<string>c; vector<string>pre[1001]; vector<string>last[1001]; char s[110],char1[11]; int n,m,position; void turn(int count) { int x=strlen(s),k,u=0,flag=0,i,flag1; while(1) { k=0; memset(char1,0,sizeof(char1)); for(i=u;i<x;i++) { if(s[i]=='=') { pre[count].push_back(char1);position=i;flag=1;break; } if(s[i]!='+') { char1[k]=s[i]; k++; } else { u=i+1; pre[count].push_back(char1); break; } } if(flag==1) break; } u=position+1; while(1) { k=0;flag1=0; memset(char1,0,sizeof(char1)); for(i=u;i<x;i++) { if(s[i]!='+') { char1[k]=s[i]; k++; } else { u=i+1; flag1=1; last[count].push_back(char1); break; } } if(flag1==0) { last[count].push_back(char1); break; } } } int main() { int i,j,m1; char now[12]; while(scanf("%d",&n)!=EOF) { for(i=0;i<n;i++) { scanf("%s",s); turn(i); } scanf("%d",&m); m1=m; for(i=1;i<=m;i++) { scanf("%s",now); have[now]=i; } for(i=0;i<n;i++) { int len=pre[i].size(),flag2=0; for(j=0;j<len;j++) { if(have[pre[i][j]]==0) { flag2=1;break; } } if(flag2==0) { for(j=0;j<last[i].size();j++) { if(have[last[i][j]]==0) { have[last[i][j]]=m1++; c.push_back(last[i][j]); } } } } printf("%d\n",m1-m); sort(c.begin(),c.end()); for(i=0;i<m1-m;i++) { cout << c[i] << endl; } } return 0; }