试 制 品
时间限制：1000 ms | 内存限制：65535 KB
难度：4
- 描写
-
ZZ大学的Dr.Kong最近发现实验室的很多试制品都已用完。由于项目经费有限，为了节省，Dr.Kong决定利用实验室现有的试制品来生成所缺的试制品。为此，Dr.Kong连续几天通宵达旦整理出1份研究资料并让研究生Bill去实验并统计能产生多少种所缺的试制品。
Bill从头到尾翻完所有的资料，发现资料上写满了1大堆的化学方程式，上面除大小写英文字母、数字、加号、等号外，再也没有其他的符号了。其中，每一个方程式都是A1+A2+……+Ap=B1+B2+……+Bq的情势， 表示试制品A1,A2,……和Ap反应，生成了试制品B1,B2,……,Bq。其中Ai和Bj都是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次，感觉还不错