XieNaoban's Blog
0%

算法竞赛入门经典(第2版) 5-10UVa1597 - Searching the Web

发表于 更新于 分类于 ， 阅读次数： 评论次数：
本文字数： 11k 阅读时长 ≈ 10 分钟

题意：不难理解，照搬题意的解法。

代码：（Accepted，0.190s）

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
//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%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
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
//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） 

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
#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;
}

Powered By Valine
v1.5.2