1.题目描述：点击打开链接
2.解题思路：本题要求模拟一个搜索引擎，该引擎可以处理四种搜索方式：term，term1ANDterm2，term1ORterm2，NOTterm。在题目描述部分已经介绍了搜索引擎的搭建方式，理论上只需要按照题意搭建即可，不过这样的话，代码会很长，由于中间还要输出一些分隔符来区分文章或者询问，代码长度至少快300行了。这样的代码难以维护，而且在比赛中也不切实际，因此需要进行再优化。
由于需要建立每个关键词和对应的文章，段落的映射，因此想到可以使用map。为了便于处理，这里指记录关键词与行之间的映射关系，同时用limit数组来标记每篇文章的边界行。由于一共有四种查询方式，为了便于处理不同的查询方式，再设一个mark数组，来标记该查询方式下的行号。
那么最后一个问题，如何处理两种不同的分隔符。通过观察可以发现，dash分隔符出现在上一次有输出的情况下，equal分隔符出现在每次查询的末尾。这样以来，只需要用两个标记变量hasOut,needOut来判断上一次是否有过输出并且dash分隔符是否需要输出即可，具体实现方式见代码注释。
本题的一个重要技巧是定义Bit来表示一个所有行的标记数组，即tyoedef bool Bit[1505]，还有一个技巧是活用逻辑运算符来计算mark数组。另外需要注意输入n,m时要多打一个空格，抵消掉换行符，否则会WA。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;#define N 1505#define rep(i,n) for(int i=0;i<(n);i++)#define FOR for(int j=limit[i];j<limit[i+1];j++)typedef bool Bit[N];map<string, Bit>Index;string doc[N];int limit[105];int n, lines, m;void update(string s, int p){string word;string::iterator it = s.begin();for (it; it != s.end();it++)if (isalpha(*it))*it = tolower(*it);else *it = ' ';stringstream ss(s);while (ss >> word)Index[word][p] = true;}int main() {//文档数据输入//freopen("t.txt", "r", stdin);scanf("%d ", &n);//注意，要多打一个空格，，抵消掉换行符rep(i, n) {limit[i] = lines;while (getline(cin, doc[lines]), doc[lines] != "**********") {update(doc[lines], lines);lines++;}}limit[n] = lines;//为了便于用FOR统一处理//对获取的请求输出对应的内容string s;// s存储每次得到的请求Bitmark;//记录哪些行应该输出//mark的解释: 因为每篇文档要用10个'-'隔开,比较麻烦,最后统一处理bool *A, *B;scanf("%d ", &m);//多打一个空格，方便处理多余的字符while (m–){getline(cin, s);//计算出mark中介if (s[0] == 'N') {A = Index[s.substr(4)];rep(i, n) {bool logo = true;FOR if (A[j]) { logo = false; break; }FOR mark[j] = logo;}}else if (s.find("AND") != string::npos) {int p = s.find(" AND ");A = Index[s.substr(0, p)];B = Index[s.substr(p + 5)];memset(mark, 0, sizeof(mark));bool hasA, hasB; // 在同一文章中, 两个词是否都出现rep(i, n){hasA = hasB = false; // 默认没出现FOR if (A[j]) { hasA = true; break; }FOR if (B[j]) { hasB = true; break; }if (!(hasA&&hasB)) continue;FOR mark[j] = (A[j] || B[j]);}}else if (s.find("OR") != string::npos) {int p = s.find(" OR ");A = Index[s.substr(0, p)];B = Index[s.substr(p + 4)];rep(i, lines) mark[i] = (A[i] || B[i]);}else memcpy(mark, Index[s], sizeof(mark));//{subsection: 输出markbool hasOut = false, needOut = false; // 记录上一轮是否有输出文档rep(i, n) {if (hasOut) needOut = true;hasOut = false;FOR if (mark[j]){if (needOut){cout << "———-\n";needOut = false;}cout << doc[j] << "\n";hasOut = true;}}if (!(needOut || hasOut)) cout << "Sorry, I found nothing.\n";//如果有过输出，必然有一个为truecout << "==========\n";}return 0;}
命运掌握在自己手中
