PAT甲级1149.

目录

A1149

题目

样例

输入:

6 3
20001 20002
20003 20004
20005 20006
20003 20001
20005 20004
20004 20006
4 00001 20004 00002 20003
5 98823 20002 20003 20006 10010
3 12345 67890 23333

输出:

No
Yes
Yes

思路和坑点

　　思路：
　　标记两种反应物的关系，然后根据每一个货物清单，查找相关反应物是否出现在清单中。
　　坑点:
　　一个物品的反应物可能不止一种，所以要选用合适的方式存储这种关系。

AC代码

#include<bits/stdc++.h>
using namespace std;
unordered_map<string,string> mp;                    //记录反应物对应关系
bool check(){
    int n;
    cin>>n;
    unordered_map<string,int> m;                    //记录某个物品是否出现过
    vector<string> v(n);
    for(int i=0;i<n;i++){                           //读取每一种货物
        cin>>v[i];
        m[v[i]]=1;
    }
    for(int i=0;i<n;i++)                            
        if(mp[v[i]]!=""){                           //如果当前物品有反应物
            for(int j=0;j<mp[v[i]].size();j+=5){    
                string temp=mp[v[i]].substr(j,5);   //每次提取从j开始的五位进行核查 
                if(m[temp]==1)  return false;       //如果与之反应的物品也出现在清单里，则不能安全运输
            }
        }
    return true;
}
int main(){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif 
    int n,m;
    string a,b;    
    cin>>n>>m;
    for(int i=0;i<n;i++){                           //采用衔接的方式构建一个类似于二维矩阵的map，
        cin>>a>>b;                                  //把每一个物品对应的反应物品string类变量直接加在value值的后边，构成一个长串 
        mp[a]+=b;                                   //检查时每次取出5位进行对比核查
        mp[b]+=a;                                   
    }
    for(int i=0;i<m;i++)                           //判定m箱货物清单
        puts(check()?"Yes":"No");
    return 0;
}