NYOJ542试制品,<虐心模拟题>

描写

ZZ大学的Dr.Kong最近发现实验室的很多试制品都已用完。由于项目经费有限，为了节省，Dr.Kong决定利用实验室现有的试制品来生成所缺的试制品。为此，Dr.Kong连续几天通宵达旦整理出1份研究资料并让研究生Bill去实验并统计能产生多少种所缺的试制品。

Bill从头到尾翻完所有的资料，发现资料上写满了1大堆的化学方程式，上面除大小写英文字母、数字、加号、等号外，再也没有其他的符号了。其中，每一个方程式都是A₁+A₂+……+A_p=B₁+B₂+……+B_q的情势， 表示试制品A₁,A₂,……和A_p反应，生成了试制品B₁,B₂,……,B_q。其中A_i和B_j都是1种单质或化合物的化学式(长度不超过10个字符)，1≤p,q ≤ 20 。每一个方程式的总长不超过100个字符。有些试制品的化学式可能在现代社会的化学元素周期表里找不到，这是由于化学反应进程中可能又有物理反应致使的结果。

Bill头疼了，从哪一个实验开始呢？你能帮助他吗？

输入

有多组测试数据。
第1行：N表示Dr.Kong写的化学方程式个数（1<=N<=400） 
接下来有N行, 每行是1个方程式.
再接下来的1行：M表示已有多少种试制品.(1<=M<=500)
接下来有M行，每行是已有的1种试制品的化学式.

输出

第1行包括1个数T，表示可以产生多少种所缺的试制品.
在接下来的T行中，按ASCII码升序输生产生的试制品的化学式.

样例输入

4H2O+Na=NaOH+H2Cl2+H2=HClFe+O2=Fe3O4NaOH+HCl=H2O+NaCl3H2ONa Cl2

样例输出

4H2HClNaClNaOH

来源

第5届河南省程序设计大赛

上传者

ACM_李如兵

思路：

由于数据很小那末就无穷遍历方程式，把已有的物资放入map中，分解方程式，让判断该方程是不是产生，产生就把生成的物资放入map中，当有1轮没有新方程产生就表示不会再有产生了

#include<bits/stdc++.h> using namespace std; struct fcs { string sz; bool fs;//方程式，有fs标记产生否 }a[444]; int main() { int n,m,i,j; while(scanf("%d",&n)==1) { for(i=0;i<n;++i) { cin>>a[i].sz; a[i].fs=false; } scanf("%d",&m); map<string,bool> jb;//用map表示已有物资右点Bool表示的是生成物还是反应物 for(i=0;i<m;++i) { string s; cin>>s; jb[s]=false; } bool sad=true;//标记变量当判断是不是有方程式产生 while(sad) { sad=false; for(i=0;i<n;++i) { if(a[i].fs)//该方程产生过就不看 continue; int len,gfs=0; string wz;//分解方程得出单个物资 for(j=0,len=a[i].sz.size();j<len;++j) { if(a[i].sz[j]=='+'||a[i].sz[j]=='=')//+或等于结束 { if(!jb.count(wz))//表示的是该物资不存在直接退出 break; wz=""; if(a[i].sz[j]=='=')//等号的时候表示的是所有物资都有该方程能产生 { a[i].fs=true;//标记这个方程式为产生过 sad=true;//该轮有物资生成 gfs=1;//标记 break; } continue; } wz+=a[i].sz[j];//连接 //if(a[i].sz[j]!='+'&&a[i].sz[j]!='=') } if(gfs)//把生成物加入 { wz=""; for(++j;j<len;++j)// { if(a[i].sz[j]=='+') { if(jb.count(wz))//生成物资要判重 { wz=""; continue; } jb[wz]=true;//insert wz=""; continue; } wz+=a[i].sz[j]; } if(!jb.count(wz))//最后1个也要判重，第1次交WA了 jb[wz]=true; } } } cout<<(jb.size()-m)<<endl; map<string,bool>::iterator p=jb.begin(); while(p!=jb.end())//输出 { if(p->second) cout<<p->first<<endl; p++; } } return 0; }

大1的时候这个题写了两天，心都碎了，过了1年重新再来1次，感觉还不错

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠