题意：不难理解，照搬题意的解法。
代码：（Accepted，0.190s）
1 | //UVa1597 - Searching the Web |
分析：我选择死亡。。。难倒是不难，很快就解出来了。但是一开始用了近1秒的时间，很郁闷。于是又花了几天的时间去研究别人的代码，也包括把之前sstream全改掉用gets和puts，把only not and or全部分开做函数，写的老长。用gets和puts的版本用了0.600s，还是比别人的都慢好多。GitHub上看到大神0.080s的（https://github.com/morris821028/UVa/blob/master/temp/1597%20-%20Searching%20the%20Web.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）
1 | //UVa1597 - Searching the Web |
哎呀呀，就少那么几行，天壤之别。顺便把一开始做的版本也贴了：
代码：（Accepted，0.960s） 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95//UVa1597 - Searching the Web
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;
}