andyli

题解 洛谷 P3879 【[TJOI2010]阅读理解】
用gcc自带的pb_ds库。 代码如下:#include <ext/pb_ds/assoc_contain...
扫描右侧二维码阅读全文
08
2018/09

题解 洛谷 P3879 【[TJOI2010]阅读理解】

用gcc自带的pb_ds库。
代码如下:

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp> // pb_ds头文件
#include <iostream>
#include <string>
using namespace __gnu_pbds; // pb_ds名称空间
using namespace std;

typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> Trie;
Trie tr[1001];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int siz;
        cin >> siz;
        for (int j = 0; j < siz; j++)
        {
            string tmp;
            cin >> tmp;
            tr[i].insert(tmp); // 插入到字典树中
        }
    }
    int m;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        string tmp;
        cin >> tmp;
        for (int i = 0; i < n; i++)
            if (tr[i].find(tmp) != tr[i].end()) // 如果找到,就输出
                cout << i + 1 << " ";
        cout << endl;
    }
    return 0;
}

很简单吧!
最后,如果要在NOIP中使用pb_ds库,切记不能加using namespace __gnu_pbds;,需要在用到的时候加上__gnu_pbds::

Last modification:June 25th, 2019 at 11:20 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment