我们都知道GNU提供了比STL更STL的库——pb_ds，里面实现了哈希表、优先队列、字典树和平衡树这4种数据结构。 那么我们试试pb_ds？

• gp_hash_table<string, bitset<1000>> 2.94s 16.87MB
• gp_hash_table<string, array<bool, 1000>> 4.25s 98.68MB
• cc_hash_table<string, bitset<1000>> 2.29s 5.40MB
• cc_hash_table<string, array<bool, 1000>> 2.06s 25.98MB

这4种组合都能A了，那……搭配O2优化使用？

• gp_hash_table<string, bitset<1000>> + O2优化 1.01s 16.75MB
• gp_hash_table<string, array<bool, 1000>> + O2优化 2.16s 98.70MB
• cc_hash_table<string, bitset<1000>> + O2优化 846ms 5.50MB
• cc_hash_table<string, array<bool, 1000>> + O2优化 1.04s 25.83MB

附cc_hash_table<string, bitset<1000>>的代码:

cpp
#include <bitset>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>
#include <string>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  __gnu_pbds::cc_hash_table<string, bitset<1000>> has;
  int n, m, l;
  string s;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> l;
    for (int j = 0; j < l; j++) {
      cin >> s;
      has[s][i] = true;
    }
  }
  cin >> m;
  for (int i = 0; i < m; i++) {
    cin >> s;
    for (int j = 0; j < n; j++) {
      if (has[s][j]) {
        cout << j + 1 << ' ';
      }
    }
    cout << endl;
  }
  return 0;
}

map +set也能过

cpp
#include<map>
#include<set>
#include<string>
#include<iostream>
using namespace std;

map<string,set<int> > m;
set<int>::iterator iter;

int main()
{
    ios::sync_with_stdio(false); //关闭同步，让cin与cout更高效
	int n,p;
	cin>>n;
	for(int i=1;i<=n;++i)
	{
	    int l;
	    cin>>l;
	    for(int j=0;j<l;++j)
	    {
	        string s;
	        cin>>s;
	        m[s].insert(i);
	    }
	}
	cin>>p;
	while(p--)
	{
	    string s;
	    cin>>s;
	    if(m.count(s))
	        for(iter=m[s].begin();iter!=m[s].end();++iter)
	            cout<<*iter<<" ";
	    cout<<endl;
	}
	return 0;
}

trie树解法

cpp
#include<cstdio>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
template<int set_,int mod>
struct trie {
    struct node {
        node* son[set_];  // 存储子节点的数组
        int flag;         // 用于标记词频
    };
    node* root, *ctrl_c;  // root用于当前的Trie树节点，ctrl_c用于迭代查找
    inline void init() {
        clear(root);      // 初始化Trie树
        root = new node(), ctrl_c = root;
    }
    inline void insert(string line) {
        root = ctrl_c;
        for (int i = 0; i < line.length(); i++) {
            if (root->son[line[i] % mod] == NULL) {
                root->son[line[i] % mod] = new node();
                root->son[line[i] % mod]->flag = 0;
            }
            root = root->son[line[i] % mod];
        }
        root->flag++, root = ctrl_c;
    }
    inline int count(string line) {
        root = ctrl_c;
        for (int i = 0; i < line.length(); i++) {
            if (root->son[line[i] % mod] == NULL) {
                root = ctrl_c;
                return false;
            }
            root = root->son[line[i] % mod];
        }
        return root->flag;
    }
    inline void del(string line) {
        root = ctrl_c;
        for (int i = 0; i < line.length(); i++) {
            if (root->son[line[i] % mod] == NULL) {
                root = ctrl_c;
                return;
            }
            root = root->son[line[i] % mod];
        }
        root->flag = (root->flag == 0 ? 0 : root->flag - 1);
    }
    void clear(node* now) {
        if (now == NULL) return;
        for (int i = 0; i < set_; i++)
            if (now->son[i] != NULL) clear(now->son[i]);
        delete now;
    }
};
string line;
trie<26, 'a'> word[1001]; // 设置trie树的字符集大小为26，mod为'a'
int main() {
    int n, m, l;
    bool first;
    scanf("%d", &n); // 输入短文篇数
    for (int i = 0; i < n; i++) word[i].init();  // 初始化trie树
    for (int i = 0; i < n; i++) {
        scanf("%d", &l);  // 输入当前短文的单词数量
        while (l--) {
            cin >> line;   // 输入当前单词
            word[i].insert(line);  // 插入单词到trie树
        }
    }
    scanf("%d", &m); // 输入查询次数
    while (m--) {
        first = true;  // 用于输出的标记
        cin >> line;    // 输入查询单词
        for (int i = 0; i < n; i++) {
            if (word[i].count(line)) {  // 查询单词是否在当前短文中出现
                if (first) {
                    first = false;
                } else {
                    printf(" ");
                }
                printf("%d", i + 1);  // 输出出现的短文编号
            }
        }
        printf("\n");
    }
    return 0;
}

cpp
#include <iostream>
#include <bitset>
using namespace std;

const int maxn = 500007;
const int maxm = 1001;
int n, m, tot = 0;
int tri[maxn][26];      // Trie树，用于存储生词
bitset<maxm> b[maxn];    // bitset数组，用于记录文档中的生词
char s[maxm];           // 用于存储输入的生词
int l;                  // 每个文档的生词数量

// 向Trie树中插入生词
void insert(char *s, int x) {
    int rt = 0;
    for (int i = 0; s[i]; i++) {
        int v = s[i] - 'a'; // 将字符映射为0-25的整数
        if (!tri[rt][v]) {
            tri[rt][v] = ++tot; // 如果节点不存在，创建新节点
        }
        rt = tri[rt][v]; // 移动到下一个节点
    }
    b[rt][x] = 1; // 在对应文档的bitset中标记生词出现
}

// 查询生词在哪些文档中出现
void query(char *s) {
    int rt = 0;
    for (int i = 0; s[i]; i++) {
        int v = s[i] - 'a'; // 将字符映射为0-25的整数
        if (!tri[rt][v]) {
            cout << ' ' << endl; // 如果节点不存在，输出空行表示生词未出现过
            return;
        }
        rt = tri[rt][v]; // 移动到下一个节点
    }
    for (int i = 1; i <= n; i++) {
        if (b[rt][i] == 1) {
            cout << i << ' '; // 输出文档编号
        }
    }
    cout << endl;
}

int main() {
    cin >> n; // 读取文档数量
    for (int i = 1; i <= n; i++) {
        cin >> l; // 读取每个文档的生词数量
        for (int j = 1; j <= l; j++) {
            cin >> s; // 读取生词
            insert(s, i); // 插入生词到Trie树中，标记文档编号
        }
    }
    cin >> m; // 读取查询数量
    for (int i = 1; i <= m; i++) {
        cin >> s; // 读取查询的生词
        query(s); // 查询生词在哪些文档中出现
    }
    return 0;
}