首页 > ACM题库 > HDU-杭电 > HDU 3527-SPY-线性结构-[解题报告]HOJ
2014
11-05

HDU 3527-SPY-线性结构-[解题报告]HOJ

SPY

问题描述 :

The National Intelligence Council of X Nation receives a piece of credible information that Nation Y will send spies to steal Nation X’s confidential paper. So the commander of The National Intelligence Council take measures immediately, he will investigate people who will come into NationX. At the same time, there are two List in the Commander’s hand, one is full of spies that Nation Y will send to Nation X, and the other one is full of spies that Nation X has sent to Nation Y before. There may be some overlaps of the two list. Because the spy may act two roles at the same time, which means that he may be the one that is sent from Nation X to Nation Y, we just call this type a “dual-spy”. So Nation Y may send “dual_spy” back to Nation X, and it is obvious now that it is good for Nation X, because “dual_spy” may bring back NationY’s confidential paper without worrying to be detention by NationY’s frontier So the commander decides to seize those that are sent by NationY, and let the ordinary people and the “dual_spy” in at the same time .So can you decide a list that should be caught by the Commander?
A:the list contains that will come to the NationX’s frontier.
B:the list contains spies that will be sent by Nation Y.
C:the list contains spies that were sent to NationY before.

输入:

There are several test cases.
Each test case contains four parts, the first part contains 3 positive integers A, B, C, and A is the number which will come into the frontier. B is the number that will be sent by Nation Y, and C is the number that NationX has sent to NationY before.
The second part contains A strings, the name list of that will come into the frontier.
The second part contains B strings, the name list of that are sent by NationY.
The second part contains C strings, the name list of the “dual_spy”.
There will be a blank line after each test case.
There won’t be any repetitive names in a single list, if repetitive names appear in two lists, they mean the same people.

输出:

There are several test cases.
Each test case contains four parts, the first part contains 3 positive integers A, B, C, and A is the number which will come into the frontier. B is the number that will be sent by Nation Y, and C is the number that NationX has sent to NationY before.
The second part contains A strings, the name list of that will come into the frontier.
The second part contains B strings, the name list of that are sent by NationY.
The second part contains C strings, the name list of the “dual_spy”.
There will be a blank line after each test case.
There won’t be any repetitive names in a single list, if repetitive names appear in two lists, they mean the same people.

样例输入:

8 4 3
Zhao Qian Sun Li Zhou Wu Zheng Wang
Zhao Qian Sun Li
Zhao Zhou Zheng
2 2 2
Zhao Qian
Zhao Qian
Zhao Qian

样例输出:

Qian Sun Li
No enemy spy

题意:

(老实说,我自己也读不太懂= =)大概意思就是,有3个队列;

A:要进入X国的人。

B:是Y国派过来的间谍。

C:曾经是X国派到Y国的间谍,也就是双重间谍。

题目中说了双重间谍和普通人都是不需要被抓的。因此就是让你找出,在B中且在A中,但不能在C中的人。

思路:

map一顿乱搞。

(虽说是道水题,不过也写了有些时间,反映了我在map,priority_queue以及pair的使用上还是不够熟练。)

code:

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
map <string, int> mp, mp2, mp3;
map <string, int>::iterator it, it2;

struct PP
{
    string str;
    int p;
    bool operator < (const PP & a) const
    {
        return p > a.p;
    }
};
void solve()
{
    priority_queue <PP> pq;
    for(it = mp2.begin(); it != mp2.end(); it++)
    {
        string tmp = it->first;
        if(mp.find(tmp) != mp.end() && mp3.find(tmp) == mp3.end())
            pq.push((PP){it->first, it->second});
    }

    if(pq.size() == 0)
    {
        cout<<"No enemy spy"<<endl;
        return ;
    }
    bool flag = false;
    while(!pq.empty())
    {
        if(flag)
            cout<<" "<<pq.top().str;
        else
        {
            cout<<pq.top().str;
            flag = true;
        }
        pq.pop();
    }
    cout<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    //freopen("in.txt", "r", stdin);
    int a, b, c;
    while(cin>>a>>b>>c)
    {
        mp.clear();
        mp2.clear();
        mp3.clear();
        string str;
        for(int i = 0;i < a; i++)
        {
            cin>>str;
            mp[str] = 1;
        }
        for(int i = 0;i < b; i++)
        {
            cin>>str;
            mp2[str] = i;
        }
        for(int i = 0;i < c; i++)
        {
            cin>>str;
            mp3[str] = 1;
        }
        
        solve();
    }
    return 0;
}
    

参考:http://blog.csdn.net/u011580493/article/details/41519675