题意：不难理解，照搬题意的解法。
代码：（Accepted，0.190s）
//UVa1597 - Searching the Web //#define _XIENAOBAN_ #include<iostream> #include<sstream> #include<cstring> #include<string> #include<vector> #include<map> #include<set> using namespace std; map<string, set<unsigned> > word; char lines[1510][85]; unsigned N, M, la[105], ln(1);//la:last line of the article; ln:line number char tmpword[80], tmpline[88], w1[80], w2[80], w3[80]; void ONLY(bool& flag, const string& on) { auto &t(word[on]); auto p(t.begin()); for (unsigned i(1);i <= N;++i) { while (p != t.end() && *p < la[i - 1]) ++p; if (p != t.end() && *p < la[i]) { if (flag) puts("----------"); else flag = true; while (p != t.end() && *p < la[i]) puts(lines[*p++]); } } } void NOT(bool& flag, const string& on) { auto &t(word[on]); auto p(t.begin()); for (unsigned i(0);i < N;++i) { while (p != t.end() && *p < la[i]) ++p; if (p == t.end() || *p >= la[i + 1]) { if (flag) puts("----------"); else flag = true; for (auto j(la[i]);j < la[i + 1];++j) puts(lines[j]); } } } void AND(bool& flag, const string& le, const string& ri) { auto &t1(word[le]), &t2(word[ri]); auto p1(t1.begin()), p2(t2.begin()); for (unsigned i(1);i <= N;++i) { while (p1 != t1.end() && *p1 < la[i - 1]) ++p1; while (p2 != t2.end() && *p2 < la[i - 1]) ++p2; if ((p1 != t1.end() && *p1 < la[i]) && (p2 != t2.end() && *p2 < la[i])) { if (flag) puts("----------"); else flag = true; unsigned re; while ((p1 != t1.end() && *p1 < la[i]) || (p2 != t2.end() && *p2 < la[i])) { if (p1 == t1.end() || *p1 >= la[i]) re = *p2++; else if (p2 == t2.end() || *p2 >= la[i]) re = *p1++; else if (*p2 > *p1) re = *p1++; else if (*p2 < *p1) re = *p2++; else re = *p1++, *p2++; puts(lines[re]); } } } } void OR(bool& flag, const string& le, const string& ri) { auto p1(word[le].begin()), p2(word[ri].begin()); for (unsigned i(1);i <= N;++i) { while (p1 != word[le].end() && *p1 < la[i - 1]) ++p1; while (p2 != word[ri].end() && *p2 < la[i - 1]) ++p2; if ((p1 != word[le].end() && *p1 < la[i]) || (p2 != word[ri].end() && *p2 < la[i])) { if (flag) puts("----------"); else flag = true; unsigned re; while ((p1 != word[le].end() && *p1 < la[i]) || (p2 != word[ri].end() && *p2 < la[i])) { if (p1 == word[le].end() || *p1 >= la[i]) re = *p2++; else if (p2 == word[ri].end() || *p2 >= la[i]) re = *p1++; else if (*p2 > *p1) re = *p1++; else if (*p2 < *p1) re = *p2++; else re = *p1++, *p2++; puts(lines[re]); } } } } int main() { #ifdef _XIENAOBAN_ #define gets(T) gets_s(T, 88) freopen("in.txt", "r", stdin); #endif scanf("%d", &N); getchar(); for (unsigned now(0);now < N;++now) { //read contexts of articles la[now] = ln; while (gets(tmpline) && strcmp(tmpline, "**********")) { strcpy(lines[ln], tmpline); char *pl(tmpline); do { if ((*pl >= 'a' && *pl <= 'z') || (*pl >= 'A' && *pl <= 'Z')) { char *pw(tmpword); while ((*pl >= 'a' && *pl <= 'z') || (*pl >= 'A' && *pl <= 'Z')) { if (*pl >= 'A' && *pl <= 'Z') *pl += 32; *pw++ = *pl++; } *pw = 0; word[tmpword].insert(ln); } } while (*pl++ != 0); ++ln; } } la[N] = ln; scanf("%d", &M); getchar(); int nnnn = 0; while (M--) { //read requests gets(tmpline); char *p = tmpline, *pw1 = w1, *pw2 = w2, *pw3 = w3; while (*p && *p != ' ') *pw1++ = *p++; *pw1 = '\0'; if (*p) ++p; while (*p && *p != ' ') *pw2++ = *p++; *pw2 = '\0'; if (*p) ++p; while (*p && *p != ' ') *pw3++ = *p++; *pw3 = '\0'; bool flag(false); if (!*w2) ONLY(flag, w1); else if (*w1 == 'N') NOT(flag, w2); else if (*w2 == 'A') AND(flag, w1, w3); else OR(flag, w1, w3); if (!flag) puts("Sorry, I found nothing."); puts("=========="); //printf("==========%d\n", ++nnnn);// } return 0; }分析：我选择死亡。。。难倒是不难，很快就解出来了。但是一开始用了近1秒的时间，很郁闷。于是又花了几天的时间去研究别人的代码，也包括把之前sstream全改掉用gets和puts，把only not and or全部分开做函数，写的老长。用gets和puts的版本用了0.600s，还是比别人的都慢好多。GitHub上看到大神0.080s的（https://github.com/morris821028/UVa/blob/master/temp/1597 - Searching the Web.cpp），我天这是差了多少倍！于是仿着大神的代码也写了个，结果1.090s！！？？一定是我没抄到其精髓？！花了几天时间了，结果还变慢了，好难过啊。。。然后过了几天我又回来研究了。我发现其实网上看到的算法全都是大同小异的，那我的代码一定是哪里有问题。看到大神函数里面的这一句：set<int> &t = wordInLine[args[1]]; 一开始我以他只是图个书写方便，但想了想，这样就不需要每次寻找wordInLine[args[1]]的值了，于是我就抱着试试的心态，也加了句类似的。结果瞬间从0.960s降到0.190s！新技能get！ 下面是仅仅没有给word[on]、word[le]、word[ri]加引用的版本。 代码：（Accepted，1.090s）
//UVa1597 - Searching the Web //#define _XIENAOBAN_ #include<iostream> #include<sstream> #include<cstring> #include<string> #include<vector> #include<map> #include<set> using namespace std; map<string, set<unsigned> > word; char lines[1510][85]; unsigned N, M, la[105], ln(1);//la:last line of the article; ln:line number char tmpword[80], tmpline[88], w1[80], w2[80], w3[80]; void ONLY(bool& flag, const string& on) { auto p(word[on].begin()); for (unsigned i(1);i <= N;++i) { while (p != word[on].end() && *p < la[i - 1]) ++p; if (p != word[on].end() && *p < la[i]) { if (flag) puts("----------"); else flag = true; while (p != word[on].end() && *p < la[i]) puts(lines[*p++]); } } } void NOT(bool& flag, const string& on) { auto p(word[on].begin()); for (unsigned i(0);i < N;++i) { while (p != word[on].end() && *p < la[i]) ++p; if (p == word[on].end() || *p >= la[i + 1]) { if (flag) puts("----------"); else flag = true; for (auto j(la[i]);j < la[i + 1];++j) puts(lines[j]); } } } void AND(bool& flag, const string& le, const string& ri) { auto p1(word[le].begin()), p2(word[ri].begin()); for (unsigned i(1);i <= N;++i) { while (p1 != word[le].end() && *p1 < la[i - 1]) ++p1; while (p2 != word[ri].end() && *p2 < la[i - 1]) ++p2; if ((p1 != word[le].end() && *p1 < la[i]) && (p2 != word[ri].end() && *p2 < la[i])) { if (flag) puts("----------"); else flag = true; unsigned re; while ((p1 != word[le].end() && *p1 < la[i]) || (p2 != word[ri].end() && *p2 < la[i])) { if (p1 == word[le].end() || *p1 >= la[i]) re = *p2++; else if (p2 == word[ri].end() || *p2 >= la[i]) re = *p1++; else if (*p2 > *p1) re = *p1++; else if (*p2 < *p1) re = *p2++; else re = *p1++, *p2++; puts(lines[re]); } } } } void OR(bool& flag, const string& le, const string& ri) { auto p1(word[le].begin()), p2(word[ri].begin()); for (unsigned i(1);i <= N;++i) { while (p1 != word[le].end() && *p1 < la[i - 1]) ++p1; while (p2 != word[ri].end() && *p2 < la[i - 1]) ++p2; if ((p1 != word[le].end() && *p1 < la[i]) || (p2 != word[ri].end() && *p2 < la[i])) { if (flag) puts("----------"); else flag = true; unsigned re; while ((p1 != word[le].end() && *p1 < la[i]) || (p2 != word[ri].end() && *p2 < la[i])) { if (p1 == word[le].end() || *p1 >= la[i]) re = *p2++; else if (p2 == word[ri].end() || *p2 >= la[i]) re = *p1++; else if (*p2 > *p1) re = *p1++; else if (*p2 < *p1) re = *p2++; else re = *p1++, *p2++; puts(lines[re]); } } } } int main() { #ifdef _XIENAOBAN_ #define gets(T) gets_s(T, 88) freopen("in.txt", "r", stdin); #endif scanf("%d", &N); getchar(); for (unsigned now(0);now < N;++now) { //read contexts of articles la[now] = ln; while (gets(tmpline) && strcmp(tmpline, "**********")) { strcpy(lines[ln], tmpline); char *pl(tmpline); do { if ((*pl >= 'a' && *pl <= 'z') || (*pl >= 'A' && *pl <= 'Z')) { char *pw(tmpword); while ((*pl >= 'a' && *pl <= 'z') || (*pl >= 'A' && *pl <= 'Z')) { if (*pl >= 'A' && *pl <= 'Z') *pl += 32; *pw++ = *pl++; } *pw = 0; word[tmpword].insert(ln); } } while (*pl++ != 0); ++ln; } } la[N] = ln; scanf("%d", &M); getchar(); int nnnn = 0; while (M--) { //read requests gets(tmpline); char *p = tmpline, *pw1 = w1, *pw2 = w2, *pw3 = w3; while (*p && *p != ' ') *pw1++ = *p++; *pw1 = '\0'; if (*p) ++p; while (*p && *p != ' ') *pw2++ = *p++; *pw2 = '\0'; if (*p) ++p; while (*p && *p != ' ') *pw3++ = *p++; *pw3 = '\0'; bool flag(false); if (!*w2) ONLY(flag, w1); else if (*w1 == 'N') NOT(flag, w2); else if (*w2 == 'A') AND(flag, w1, w3); else OR(flag, w1, w3); if (!flag) puts("Sorry, I found nothing."); puts("=========="); //printf("==========%d\n", ++nnnn);// } return 0; }哎呀呀，就少那么几行，天壤之别。顺便把一开始做的版本也贴了：
代码：（Accepted，0.960s）
//UVa1597 - Searching the Web #include<iostream> #include<sstream> #include<string> #include<vector> #include<map> #include<set> using namespace std; struct article { map<string, vector<unsigned> > word; vector<string> line; }; const article tmpart;//an empty article,just for push_back unsigned N, M; string tmpstr; vector<article> dat; inline bool ONLY(const article& ar, const string& l, const string& r) { return ar.word.count(l); } inline bool AND(const article& ar, const string& l, const string& r) { return ar.word.count(l) && ar.word.count(r); } inline bool OR(const article& ar, const string& l, const string& r) { return ar.word.count(l) || ar.word.count(r); } void NOT(const string& on) { bool flag(false); for (const auto& r : dat) { if (!r.word.count(on)) { if (flag) cout << "----------\n"; else flag = true; for (const auto& rr : r.line) cout << rr << '\n'; } } if (!flag) cout << "Sorry, I found nothing.\n"; } void solve(bool(*f)(const article&, const string&, const string&), const string& le, const string& ri) { bool flag(false); for (auto& r : dat) {//why it can't be "const auto& r"? because if a map is const,r.word[i] would be invalid if (f(r, le, ri)) { set<unsigned> re; if (r.word.count(le)) for (const auto& rr : r.word[le]) re.insert(rr); if (r.word.count(ri)) for (const auto& rr : r.word[ri]) re.insert(rr); if (re.empty()) continue; if (flag) cout << "----------\n"; else flag = true; for (const auto& rr : re) cout << r.line[rr] << '\n'; } } if (!flag) cout << "Sorry, I found nothing.\n"; } int main() { //freopen("in.txt", "r", stdin);// std::ios::sync_with_stdio(false); cin >> N; cin.ignore();//absorb '\n' for (unsigned now(0);now < N;++now) { //read contexts of articles int ln(0);//line number of current article dat.push_back(tmpart);//create a empty article while (getline(cin, tmpstr) && tmpstr != "**********") { dat[now].line.push_back(tmpstr); for (auto& r : tmpstr) { if (r >= 'a'&&r <= 'z') continue; if (r >= 'A'&&r <= 'Z') r += 32; else r = ' '; } istringstream in(tmpstr); while (in >> tmpstr) dat[now].word[tmpstr].push_back(ln); ++ln; } } cin >> M; cin.ignore(); while (M--) { //read requests string sl, sm, sr;//left middle right getline(cin, tmpstr); istringstream in(tmpstr); in >> sl; if (!(in >> sm)) solve(ONLY, sl, sl); else if (!(in >> sr)) NOT(sm);//why are you so special else if (sm[0] == 'A') solve(AND, sl, sr); else solve(OR, sl, sr); cout << "==========\n"; } return 0; }转载于:https://www.cnblogs.com/xienaoban/p/6798085.html
