题目和解答在这里:
ACM练习 题目1029:魔咒词典 C++ map的使用
上次用C++的map做的,运行时间并不理想。
用了两个map确实有点浪费,还有一点是把所有字符串都在一个map中。
数据过多时查找肯定慢。可以把map分成26个,以首字母分类,放在不同的map中。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <map>
using namespace std;
map<string, string> map1[26]; //保存<魔咒,对应功能>
map<string, string> map2[26]; //保存<对应功能,魔咒>
int main() {
char first;
scanf("%c", &first);
while (first == '[') {
char temp[100]; //用临时变量保存剩下的整行
gets(temp);
char * text = strchr(temp, ']'); //找到 ] 的位置
int len = strlen(temp) - strlen(text);
text += 2; //得到后半部分的 char *
string value(text);
temp[len] = '\0';
string key(temp);
map1[key[0] - 'a'].insert(pair<string, string>(key, value));
map2[value[0] - 'a'].insert(pair<string, string>(value, key));
scanf("%c", &first);
}
char aaaa[10];
gets(aaaa); //把剩余的读取了
int n;
scanf("%d\n", &n);
map<string, string>::iterator it;
for (int i = 0; i < n; i++) {
string str;
getline(cin, str);
if (str.at(0) == '[') {
str = str.substr(1, str.length() - 2);
it = map1[str[0] - 'a'].find(str);
if (it != map1[str[0] - 'a'].end())
cout << it->second << endl;
else
printf("what?\n");
} else {
it = map2[str[0] - 'a'].find(str);
if (it != map2[str[0] - 'a'].end())
cout << it->second << endl;
else
printf("what?\n");
}
}
return 0;
}
时间为60ms,还是不够好。
其实可以不用map,使用vector
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
typedef struct {
string name, func;
} dict_def;
vector<int> dict_indexed_by_name[26], dict_indexed_by_func[26];
vector<int>::iterator it_vec;
vector<dict_def> dict;
int item_num;
void Parse(char p_input[]) {
char s_name[20], s_func[80], *pos;
pos = strchr(p_input,']');
strcpy(s_func, pos + 2);
*pos = '\0';
strcpy(s_name, p_input + 1);
string s1(s_name), s2(s_func);
dict_def a_word;
a_word.name = s1, a_word.func = s2;
dict.push_back(a_word);
dict_indexed_by_name[s_name[0] - 'a'].push_back(item_num);/*该魔法单词的序号*/
dict_indexed_by_func[s_func[0] - 'a'].push_back(item_num);
item_num++;
}
string FindName(string p_func)/*按功能找魔法名*/
{
int index = p_func[0] -'a';
for (it_vec = dict_indexed_by_func[index].begin();
it_vec < dict_indexed_by_func[index].end(); it_vec++)
if (dict[(*it_vec)].func == p_func)
break;
if (it_vec < dict_indexed_by_func[index].end())
return dict[(*it_vec)].name;
return "";
}
string FindFunc(string p_name)/*按魔法名找功能*/
{
int index = p_name[0] - 'a';
for (it_vec = dict_indexed_by_name[index].begin();
it_vec < dict_indexed_by_name[index].end(); it_vec++)
if (dict[(*it_vec)].name == p_name)
break;
if (it_vec < dict_indexed_by_name[index].end())
return dict[(*it_vec)].func;
return "";
}
int main() {
char input[100];
while (gets(input) != NULL) {
while (strcmp(input, "") == 0)
gets(input);
if (strcmp(input, "@END@") == 0)
break;
Parse(input);/*将一条记录拆分成单词名称和功能,并存入相应vector*/
}
int case_num;
string s_name, s_func, ans;
scanf("%d", &case_num);
getchar();
while (case_num--) {
gets(input);
if (input[0] == '[') {
s_name = input;
s_name.erase(s_name.begin());
s_name.erase(s_name.end() - 1);
ans = FindFunc(s_name);
printf("%s\n", ans == "" ? "what?" : ans.c_str());
} else {
s_func = input;
ans = FindName(s_func);/*真正进行对比的数组,数组下标,要对比的字符串*/
printf("%s\n", ans == "" ? "what?" : ans.c_str());
}
}
return 0;
}
时间为10ms
分享到:
相关推荐
浙江大学的ACM题目可以在其在线判题系统(ZOJ)上找到,网址是:http://acm.zju.edu.cn/onlinejudge/。同时,这个平台也对外开放,外校学生也可以参与其中。 以下是一些浙大ACM的题目样例: 第一套动态规划:ZJU...
acm练习原题 算法练习 acm小的练习题目 acm典型算法
ACM经典C++题目:Gone Fishing算法详解及源代码.doc
凯凯刚写了一篇美妙的作文,请问这篇作文的标题中有多少个字符? 注意:标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字符数时,空格和换行符不计算在内。 输入格式 输入文件只有一行,一个字符...
ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM...
ACM竞赛题目简介ACM竞赛题目简介ACM竞赛题目简介ACM竞赛题目简介
ACM练习建议 ACM练习建议 ACM练习建议
ACM题目分类,ACM题目分类,ACM题目分类,ACM题目分类ACM题目分类,ACM题目分类
ACM题目解析ACM题目解析ACM题目解析
自己搜集的ACM题目汇总 大多都是入门的经典题目初学者可以练练手大佬请路过
acm acm acm acm acm acm acm acm 题目分类 题目分类 题目分类
java做acm题目入门知识 java acm java做ACM的必备
《ACM国际大学生程序设计竞赛:题目与解读》讲述了ACM国际大学生程序设计竞赛(ACM—ICPC)是国际上公认的水平最高、规模最大、影响最深的计算机专业竞赛,目前全球参与人数达20多万。《ACM国际大学生程序设计竞赛:...
ACM数学题目,适用于ACM爱好者,内含 各种类型的数学题目
本系列丛书包括《ACM国际大学生程序设计竞赛:知识与入门》、《ACM国际大学生程序设计竞赛:算法与实现》、《ACM国际大学生程序设计竞赛:题目与解读》、《ACM国际大学生程序设计竞赛:比赛与思考》等4册,其中《ACM...
ACM经典题目解题报告ACM经典题目解题报告
acm的好题目,如果你正在做ACM程序设计,这是一个不错的学习资料
暑假学校ACM集训用的课件,动态规划专题。
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
acm poj 比较详细的将poj的题目进行了分类,如dp,搜索,数据结构等等