首页 > HDOJ解题报告 > HDU 1880 魔咒词典

HDU 1880 魔咒词典

做这些题,主要是复习STL。我用map写的,结果超内存了,非常郁闷。思路是这样的:用两个map,一个存咒语-意思,另一个存意思-咒语。于是我只用一个map,存咒语-意思,只有一个的话,value就要自己找了,没规律,只能暴力搜索,超时。

传送:http://acm.hdu.edu.cn/showproblem.php?pid=1880

后来,我还是用两个map,提交语言改为G++,结果就AC了。另外,自己试着用两个vector,然后快排,然后二分搜索,也行;不过还是必须G++,否则MLE。两个程序从本质上来说是没有区别的。时间和内存消耗都相差不大。

另外,本题应该用HASH来做,这样才不会出现超内存的情况。具体正在研究中。

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
// map
// 作者:代码疯子
// Blog: http://www.programlife.net/
// G++ Accepted
#include <iostream>
#include <string>
#include <map>
using namespace std;
 
map<string, string> dic[2];
 
int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	map<string, string>::iterator pos;
	int n;
	string tmp, word, meaning;
 
	getline(cin, tmp);
	while (tmp != "@END@")
	{
		string::size_type idx = tmp.find(']');
		word = tmp.substr(0, idx + 1);	// substr(index, num)
		meaning = tmp.substr(idx + 2, tmp.size() - idx - 2);
		dic[0].insert(make_pair(word, meaning));
		dic[1].insert(make_pair(meaning, word));
		//dic[0][word] = meaning;
		//dic[1][meaning] = word;
		getline(cin, tmp);
	}
 
	cin >> n;
	getline(cin, tmp);	// '\n'
	while (n--)
	{
		getline(cin, tmp);
		if (tmp[0] == '[')
		{
			pos = dic[0].find(tmp);
			if (pos != dic[0].end())
				cout << pos->second << endl;
			else
				cout << "what?" << endl;
		}
		else
		{
			pos = dic[1].find(tmp);
			if (pos != dic[1].end())
			{
				tmp = (pos->second).substr(1, (pos->second).size() - 2);
				cout << tmp << endl;
			}
			else
				cout << "what?" << endl;
		}
	}
 
	return 0;
}
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
// vector
// 作者:代码疯子
// Blog: http://www.programlife.net/
// G++ Accepted
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
 
#define MAX_WORD_NUM 100010
 
class Node
{
public:
	string key;
	string val;
	Node (string _key, string _val) : key(_key), val(_val){}
};
 
vector<Node> dic[2];
 
bool sort_less(const Node& lhs, const Node& rhs)
{
	return lhs.key < rhs.key;
}
 
int my_binary_search(int b, int e, const string& dest, int i)
{
	int minIndex = b, maxIndex = e, midIndex;
	while (minIndex < maxIndex - 1)
	{
		midIndex = minIndex + (maxIndex - minIndex) / 2;
		if (dic[i][midIndex].key < dest)
		{
			minIndex = midIndex;
		}
		else
		{
			maxIndex = midIndex;
		}
	}
	if (dic[i][maxIndex].key == dest)
	{
		return maxIndex;
	}
	else if (dic[i][minIndex].key == dest)
	{
		return minIndex;
	}
 
	return -1;
}
 
int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
 
	vector<Node>::iterator pos;
	int n, i;
	string tmp, word, meaning;
 
	dic[0].reserve(MAX_WORD_NUM);
	dic[1].reserve(MAX_WORD_NUM);
 
	getline(cin, tmp);
	while (tmp != "@END@")
	{
		string::size_type idx = tmp.find(']');
		word = tmp.substr(0, idx + 1);	// substr(index, num)
		meaning = tmp.substr(idx + 2, tmp.size() - idx - 2);
		dic[0].push_back(Node(word, meaning));
		dic[1].push_back(Node(meaning, word));
		getline(cin, tmp);
	}
 
	sort(dic[0].begin(), dic[0].end(), sort_less);
	sort(dic[1].begin(), dic[1].end(), sort_less);
 
	cin >> n;
	getline(cin, tmp);	// '\n'
	while (n--)
	{
		getline(cin, tmp);
		if (tmp[0] == '[')
		{
			i = my_binary_search(0, dic[0].size() - 1, tmp, 0);
			if (i != -1)
			{
				cout << dic[0][i].val << endl;
			}
			else
				cout << "what?" << endl;
		}
		else
		{
			i = my_binary_search(0, dic[1].size() - 1, tmp, 1);
			if (i != -1)
			{	
				tmp = (dic[1][i].val).substr(1, (dic[1][i].val).size() - 2);
				cout << tmp << endl;
			}
			else
				cout << "what?" << endl;
		}
	}
 
	return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> HDU 1880 魔咒词典
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



分类: HDOJ解题报告 标签: , , , , ,
  1. 本文目前尚无任何评论.