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次，感覺還不錯

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈