QQ帐户的申请与登陆
实现QQ新帐户申请和老帐户登陆的简化版功能。最大挑战是：据说现在的QQ号码已经有10位数了。
输入格式:
输入首先给出一个正整数N（≤ 105），随后给出N行指令。每行指令的格式为：“命令符（空格）QQ号码（空格）密码”。其中命令符为“N”（代表New）时表示要新申请一个QQ号，后面是新帐户的号码和密码；命令符为“L”（代表Login）时表示是老帐户登陆，后面是登陆信息。QQ号码为一个不超过10位、但大于1000（据说QQ老总的号码是1001）的整数。密码为不小于6位、不超过16位、且不包含空格的字符串。
输出格式:
针对每条指令，给出相应的信息：
1）若新申请帐户成功，则输出“New: OK”；
2）若新申请的号码已经存在，则输出“ERROR: Exist”；
3）若老帐户登陆成功，则输出“Login: OK”；
4）若老帐户QQ号码不存在，则输出“ERROR: Not Exist”；
5）若老帐户密码错误，则输出“ERROR: Wrong PW”。
输入样例:
5 L 1234567890 myQQ@qq.com N 1234567890 myQQ@qq.com N 1234567890 myQQ@qq.com L 1234567890 myQQ@qq L 1234567890 myQQ@qq.com
输出样例:
ERROR: Not Exist New: OK ERROR: Exist ERROR: Wrong PW Login: OK
解题思路
先给出std::unordered_map实现的AC代码：
1 #include <iostream>
2 #include <vector>
3 #include <string>
4 #include <unordered_map>
5 #include <algorithm>
6 using namespace std;
7
8 int main() {
9 int n;
10 cin >> n;
11 unordered_map<string, string> mp;
12
13 for (int i = 0; i < n; i++) {
14 string op, id, pw;
15 cin >> op >> id >> pw;
16 if (op == "N") {
17 if (mp.count(id) == 1) {
18 cout << "ERROR: Exist\n";
19 }
20 else {
21 mp[id] = pw;
22 cout << "New: OK\n";
23 }
24 }
25 else if (op == "L") {
26 if (mp.count(id) == 0) {
27 cout << "ERROR: Not Exist\n";
28 }
29 else if (mp[id] == pw) {
30 cout << "Login: OK\n";
31 }
32 else {
33 cout << "ERROR: Wrong PW\n";
34 }
35 }
36 }
37
38 return 0;
39 }
然后是手写的哈希散列AC代码：
1 ude <cstdio>
2 #include <cstdlib>
3 #include <cstring>
4 #include <cmath>
5 #include <vector>
6
7 const int MAXN = 17;
8
9 struct Data {
10 char id[MAXN], pw[MAXN];
11 };
12
13 struct HashTable {
14 int tableSize;
15 std::vector<std::vector<Data> > table;
16 };
17
18 HashTable *createTable();
19 int prime();
20 bool find(Data &data, HashTable *ht);
21 void insert(Data &data, HashTable *ht);
22
23 int main() {
24 int n;
25 scanf("%d", &n);
26 HashTable *ht = createTable();
27
28 for (int i = 0; i < n; i++) {
29 char op;
30 scanf("\n%c", &op);
31 Data data;
32 scanf(" %s %s", data.id, data.pw);
33
34 if (op == 'N') {
35 if (!find(data, ht)) {
36 insert(data, ht);
37 puts("New: OK");
38 }
39 else {
40 puts("ERROR: Exist");
41 }
42 }
43 else if (op == 'L') {
44 if (!find(data, ht)) {
45 puts("ERROR: Not Exist");
46 }
47 else {
48 int pos = atoi(data.id) % 10000;
49 std::vector<Data>::iterator it = ht->table[pos].begin();
50 for ( ; strcmp(it->id, data.id); it++);
51 if (strcmp(it->pw, data.pw) == 0) puts("Login: OK");
52 else puts("ERROR: Wrong PW");
53 }
54 }
55 }
56
57 return 0;
58 }
59
60 HashTable *createTable() {
61 HashTable *ht = new HashTable;
62 ht->tableSize = prime();
63 ht->table.resize(ht->tableSize);
64
65 return ht;
66 }
67
68 int prime() {
69 int i = 10001;
70 while (true) {
71 int j = (int)sqrt(10000);
72 for ( ; j > 2; j--) {
73 if (i % j == 0) break;
74 }
75 if (j == 2) break;
76 i += 2;
77 }
78
79 return i;
80 }
81
82 bool find(Data &data, HashTable *ht) {
83 int pos = atoi(data.id) % 10000;
84 for (std::vector<Data>::iterator it = ht->table[pos].begin(); it != ht->table[pos].end(); it++) {
85 if (strcmp(it->id, data.id) == 0) return true;
86 }
87
88 return false;
89 }
90
91 void insert(Data &data, HashTable *ht) {
92 int pos = atoi(data.id) % 10000;
93 ht->table[pos].push_back(data);
94 }
手写实现一般会比STL的要快，比如还有手写堆和优先队列。如果题目时间不是卡的很紧，还是用STL吧，毕竟太方便了。