准备ACM，看了一下STL库。
http://www.docin.com/p-46121844.html
豆丁这个PDF不错，福州大学的，感觉简明扼要刚好够ACM用。
很水，所以做水题。
每一道题都能多发现几个有用的函数。
map很多时候都不是最好的办法，自己写hash估计其实会更快的，不过既然是熟悉map，就全部用map了。
相关的POJ题目, 搜索"poj map"然后找出来的可以用map解决的题目。
POJ 1002map<string, int>
每次读入一个原始号码，转化成数字的标准形式，用map来存储每个号码的出现次数。
POJ 2491map<string, int>
题意简单说来就是给一堆单词，有一个开头，一个结尾，要求连成一串。
看一下样例就可以明白了。
给每个字符串编个号，再记录一下相应的父子状态。
POJ2491
#include <map>
#include <cstdlib>
#include <iterator>
#include <iostream>
#include <string>
using namespace std;
int main(){
int T, s, cs, pos1, pos2, len, i, k;
int cnt1[700], cnt2[700], son[700];
string str[700], str1, str2;
cin >> T;
for (cs=1; cs<=T; cs++){
//Def
if (cs!=1) cout << endl;
map <string,int> m;
//Init
cin >> s;
len = 1;
for (i=1; i<=2*s+1; i++)
cnt1[i] = cnt2[i] = 0;
//Doit
for (i=1; i<s; i++){
cin >> str1;
cin >> str2;
if (!m[str1]) m[str1] = len++;
if (!m[str2]) m[str2] = len++;
pos1 = m[str1];
pos2 = m[str2];
str[pos1] = str1;
str[pos2] = str2;
son[pos1] = pos2;
cnt1[pos1]++;
cnt2[pos2]++;
}
for (k=1; k<=len; k++){
if (cnt1[k] == 1 && cnt2[k] == 0) break;
}
printf("Scenario #%d:\n", cs);
for (i=1; i<=s; i++){
cout << str[k] << endl;
k = son[k];
}
}
return 0;
}
字典问题，map<string, string>
直接dict[foreign] = english;
最后查找。
题目提示最好用scanf和printf，我用了C的字符串读入，再转化成string。
网上看了一些人的程序，一位大牛10+行用cin string直接搞，2000+ms过。
第一次输出的时候没转换了，直接string输出，900+ms。
修改了一次，把string转换成char *a形式输出，700+ms。
说明使用C字符串读入还是确实节省不少时间的。
同时也学习了一下string转换成 char *a，又有函数……
const char *a;/*因为str.c_str()返回值是const char* 类型的*/
string str="hello";
a=str.c_str();
POJ2503
#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
#define end_line cin.ignore(100,'\n');
int main(){
map<string, string> dict;
string e, f; // english foreign;
char str[100];
gets(str);
while (str[0]>='a' && str[0]<='z'){
int i, len;
e = ""; f="";
len = strlen(str);
for (i=0; i<len; i++){
if (str[i] == ' ') break;
e += str[i];
}
for (i++; i<len; i++){
f += str[i];
}
dict[f] = e;
gets(str);
}
while (gets(str)){
f = str; //char[]杞瑂tring
map<string, string>::iterator temp;
if ((temp=dict.find(f)) == dict.end()){
printf("eh\n");
}
else{
//cout << temp->second << endl;
const char *a; //因为str.c_str()返回值是const char* 类型的*/
a=temp->second.c_str();
printf("%s\n", a);
}
}
return 0;
}
POJ 2643map<string, string>
map<string, int>
综合了Discuss里很多人的讨论，这个代码应该算挺完善的了，
1、如果投票给不在之前输入的名字范围之内，忽略掉
2、不管输入的n和m之后有多少空格什么的一律忽略，无影响
3、直接按姓名投票，所有independent直接在党派里记录为independent
顺带学习了几个函数，注释出来
POJ2643
1 /*
2 * POJ2643.CPP
3 *
4 * Created on: 2010-10-8
5 * Author: dango
6 */
7
8 #include <string>
9 #include <iostream>
10 #include <map>
11 #include <algorithm>
12 using namespace std;
13
14 int main(){
15 int n,m;
16 string name, party;
17 map<string, string> name_party;
18 map<string, int> name_ballot;
19
20 cin >> n;
21 cin.ignore(100,'\n'); //避免行末的空格之类，忽略至多100个字符，直到把\n忽略掉
22
23 while (n--){
24 getline(cin, name); //读一行，直到换行，忽略换行
25 getline(cin, party);
26 name_party[name] = party;
27 name_ballot[name] = 0;
28 }
29
30 cin >> m;
31 cin.ignore(100,'\n');
32
33 int temp;
34 int max = 0;
35 int tie = true;
36 while (m--){
37 getline(cin, name);
38 if (name_ballot.find(name) != name_ballot.end()){
39 //一开始用 if (name_ballot.find(name)) 死活编译不过，后来才发现应该这么写……
40 //还一度脑子发热以为只能传const量去find, SB了一把
41 temp = ++name_ballot[name];
42 if (temp == max) tie = true;
43 else
44 if (temp>max){
45 tie = false;
46 max = temp;
47 }
48 }
49 }
50
51 if (tie) cout << "tie" << endl;
52 else{
53 map<string, int>::iterator it;
54 for (it = name_ballot.begin(); it!=name_ballot.end(); it++)
55 //迭代器的使用
56 if ((*it).second == max){
57 cout << name_party[(*it).first] << endl;
58 break;
59 }
60 }
61
62 return 0;
63 }
64
POJ3087map绝对是很水的一个解决方式，不过我就是为了练习map的所以用了……
我用了map<vector<char>, int>，用map<string, int>应该也是可以的。
给一个洗牌的序列，具体就是题目的图，画的挺明白的。如果达不到目标状态，必定是洗着洗着到了一个死循环了
总结：
原来vector是可以用==判断的……看了网上的一个代码又有了很水的新发现……
vector<char> temp(now); //构造一个新的向量，作为已存在的向量的完全复制
用了一个新东西……
POJ3087
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define end_line cin.ignore(100,'\n');
map<vector<char>, int> shuffle_map;
vector<char> now, target;
void init(int &C){
char ch;
int i;
cin >> C;
end_line; //cin.ignore(100,'\n');
now.clear(); //vector清空
target.clear(); //vector清空
for (i=1; i<=C; i++){
cin >> ch;
now.push_back(ch);
}
end_line;
for (i=1; i<=C; i++){
cin >> ch;
now.push_back(ch);
}
end_line;
for (i=1; i<=2*C; i++){
cin >> ch;
target.push_back(ch);
}
}
void shuffle(int C){
vector<char> temp(now); //构造一个新的向量，作为已存在的向量的完全复制
//temp临时存放now, now利用temp改变为洗牌后新的值
for (int i=0; i<(int)temp.size(); i++){
if (i%2==0)
now[i] = temp[C+i/2];
else
now[i] = temp[i/2];
}
}
int solve(int C){
int times = 0;
shuffle_map[now] = 1;
while (now!=target){
times++;
shuffle(C);
if (shuffle_map[now]!=0) return -1;
}
return times;
}
int main(){
int N, C, cs;
cin >> N;
for (cs=1; cs<=N; cs++){
init(C);
cout << cs << " " << solve(C) << endl;
}
return 0;
}
时间紧迫，map就这样先用一晚上告一段落吧～