题解 P1184 【高手之在一起】

· · 题解

Upd 2019/3/2:
1.代码加上一些有利于理解的注释
2.有一些解释不清楚的重新解释或作出补充。

好！机会来了！

依评论区的要求，小金羊献上STLset<string>的题解。

当然不会告诉你map<string,bool>我根本不会用
所以，有什么STL救救孩子？？？

还是先复习 or 预习一下set。

先给set一个名字：

set<元素类型>qwq;

插入元素：

qwq.insert(元素);

查找元素：

qwq.find(元素);

如果元素没有找到，返回qwq.end()，是一个空的位置迭代器。
注：
1.迭代器可以看作是一个复合类型的指针，set的存储是动态线性的。
2.集合的最后一个元素是空的，qwq.end()指向最后一个元素。
3.如果找到元素，就会返回指向这个元素的指针，没有的话就返回qwq.end()。
于是得出： 如何判断元素p是否存在于qwq中？

if (qwq.find(p)!=qwq.end())
{
    //如果返回了qwq的end()，就代表是不存在。
    //所以不是end()就代表在qwq内
    //然后如果没有元素，就返回end()，避免了一些不必要的尴尬
    cout<<"p s in qwq."<<endl;
}
else 
    cout<<"Not found p in qwq."<<endl;

以上是这个题的STLset内置成员函数方面。

然后讨论一下这个题的操作。

这个题很明显卡的就是Windows Vista\XP\2003\7\8.1\10！！！
Linux系统13号是'\n',即换行......
因为题目测试点下载以后win会发现多了一个13号字符' '(空格)......
然后我们读入数据就必须特判（吃掉或者加上）char(13)。
然后每一个地方还不一定不含有空格，所以必须getline。
举个例子：Boston Center
cin读到Boston就停下了。
我们也可以读入一个' '就继续cin，然而getline更方便qwq
边读入要匹配的字符串，然后.find(input)判断是否存在，存在即ans++。

说的还是挺明白的吧......
星,上代码： 

#include <iostream>
#include <cstdio>
#include <string>
#include <set>
//STL の set 库

using namespace std;

int main()
{
    string input;//你要的字符串
    set<string>qwq;//你要的集合
    int n,m,ans=0;
    scanf("%d%d",&n,&m);
    getline(cin,input);//把数字后面乱七八糟的东西读干净
    for (register int i=1;i<=n;i++)
    {
        getline(cin,input);//读入字符串
        if (input[input.size()-1]!=(char)13)//最后一个是否是' '
            input=input+char(13);
        qwq.insert(input);//压入集合qwq
    }
    for (register int i=1;i<=m;i++)
    {
        getline(cin,input);
        if (input[input.size()-1]!=(char)13)//最后一个是否是' '
            input=input+char(13);
        if (qwq.find(input)!=qwq.end())ans++;
    }
    cout<<ans;
    return 0;
}

瞎举报前提交记录自己查询：Jelly_Goat。
感谢阅读，更多精彩移步。

另附后注：

做这样的字符串匹配问题，trie字典树和KMP算法基本都是正解。
但是这样的数据结构是用空间换时间，当字符串过长的时候，不宜使用静态Trie字典树。
当数据范围较小的时候，我们可以借助其他数据结构用时间换空间。