R7-1 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
#include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<math.h> #include<string.h> #define KEYLENGTH 16 //问题编号的最大长度 #define MAXTABLESIZE 10000 //散列表的最大大小 typedef char ElementType[KEYLENGTH + 1]; //定义问题编号和密码的类型 typedef struct LNode* PtrToLNode; //链表节点指针类型 typedef PtrToLNode List; //链表指针类型 struct LNode { ElementType QNumber; //问题编号 ElementType QPassword; //问题密码 PtrToLNode Next; //指向下一个节点的指针 }; typedef struct HblNode* HashTable; //哈希表指针类型 struct HblNode { int TableSize; //散列表大小 List Heads; //链表头节点数组 }; //找到比num大的下一个素数 int NextPrime(int num) { int p = (num % 2) ? (num + 2) : (num + 1); //从num+1或num+2开始判断 int i = 0; while (p<MAXTABLESIZE) //不断增加p直到小于等于最大值 { for (i = (int)sqrt(p); i > 2; i--) //从sqrt(p)到2之间枚举因子 if (p % i == 0)break; //若p有因子，则break if (i == 2)break; //如果没有因子，则i一定等于2，跳出循环 else p += 2; //增加2后重新判断 } return p; } //哈希函数，将问题编号转换为哈希地址 int Hash(ElementType QNumber, int TableSize) { return atoi(QNumber + 3) % TableSize; //将问题编号的后三位转换成整数并对表长取余 } //创建哈希表 HashTable BuildHashTable(int TableSize) { HashTable H = (HashTable)malloc(sizeof(struct HblNode)); //分配哈希表结构体内存 H->TableSize = NextPrime(TableSize); //确定哈希表大小 H->Heads = (List)malloc(H->TableSize * sizeof(struct LNode)); //分配链表头节点数组内存 for (int i = 0; i < H->TableSize; i++) { H->Heads[i].QNumber[0] = '\0'; //初始化问题编号为空字符串 H->Heads[i].QPassword[0] = '\0'; //初始化问题密码为空字符串 H->Heads[i].Next = NULL; //初始化指向下一个节点的指针为空 } return H; } //在哈希表中查找指定问题编号的节点 PtrToLNode Find(ElementType QNumber, HashTable H) { int i = Hash(QNumber,H->TableSize); //计算哈希地址 PtrToLNode P = H->Heads[i].Next; //指向链表的第一个节点 while (P && strcmp(P->QNumber, QNumber)) //依次查找节点，直到找到或遍历完链表 P = P->Next; return P; } //向哈希表中插入新的问题编号和密码节点 void Insert(ElementType QNumber,ElementType QPassword,HashTable H) { PtrToLNode P, NewCell; P = Find(QNumber, H); //查找问题编号是否已存在 if (!P) //如果不存在，则添加新节点 { int i = Hash(QNumber, H->TableSize); //计算哈希地址 NewCell = (PtrToLNode)malloc(sizeof(struct LNode)); //分配新节点内存 strcpy(NewCell->QNumber, QNumber); //复制问题编号 strcpy(NewCell->QPassword, QPassword); //复制问题密码 NewCell->Next = H->Heads[i].Next; //将新节点插入到链表头部 H->Heads[i].Next = NewCell; } } //处理登录操作，验证问题编号和密码是否匹配 void Order_L(HashTable H) { ElementType QNumber; ElementType QPassword; scanf("%s %s", QNumber, QPassword); //读取输入的问题编号和密码 PtrToLNode P = Find(QNumber, H); //查找问题编号对应的节点 if (P) //如果找到，则验证密码是否正确 { if (!strcmp(P->QPassword, QPassword)) printf("Login: OK\n"); //密码正确，输出“Login: OK” else printf("ERROR: Wrong PW\n"); //密码错误，输出“ERROR: Wrong PW” } else printf("ERROR: Not Exist\n"); //未找到对应的问题编号，输出“ERROR: Not Exist” } //处理新增问题操作，判断问题编号是否已存在 void Order_N(HashTable H) { ElementType QNumber; ElementType QPassword; scanf("%s %s", QNumber, QPassword); //读取输入的问题编号和密码 PtrToLNode P = Find(QNumber, H); //查找问题编号对应的节点 if (P) //如果找到，则问题编号已存在，输出“ERROR: Exist” printf("ERROR: Exist\n"); else //如果未找到，则添加新节点并输出“New: OK” { Insert(QNumber, QPassword, H); printf("New: OK\n"); } } //创建哈希表并根据输入的指令进行相应操作 void CreateHashTable() { int N; scanf("%d\n", &N); //读取问题数量 HashTable H = BuildHashTable(N); //构建哈希表 while (N--) { char Order[2]; scanf("%s", Order); //读取指令 switch (Order[0]) //根据指令进行相应操作 { case 'L':Order_L(H); break; case 'N':Order_N(H); break; } } } int main() { CreateHashTable(); return 0; }
R7-2 词频统计
请编写程序，对一段英文文本，统计其中所有不同单词的个数，以及词频最大的前10%的单词。
所谓“单词”，是指由不超过80个单词字符组成的连续字符串，但长度超过15的单词将只截取保留前15个单词字符。而合法的“单词字符”为大小写字母、数字和下划线，其它字符均认为是单词分隔符。
输入格式:
输入给出一段非空文本，最后以符号#结尾。输入保证存在至少10个不同的单词。
输出格式:
在第一行中输出文本中所有不同单词的个数。注意“单词”不区分英文大小写，例如“PAT”和“pat”被认为是同一个单词。
随后按照词频递减的顺序，按照词频:单词的格式输出词频最大的前10%的单词。若有并列，则按递增字典序输出。
输入样例：
This is a test. The word "this" is the word with the highest frequency. Longlonglonglongword should be cut off, so is considered as the same as longlonglonglonee. But this_8 is different than this, and this, and this...# this line should be ignored.
输出样例：（注意：虽然单词the也出现了4次，但因为我们只要输出前10%（即23个单词中的前2个）单词，而按照字母序，the排第3位，所以不输出。）
23 5:this 4:is
#include<iostream> #include<vector> #include<map> #include<string> #include<algorithm> using namespace std; map<string, int> mp; struct Words {//定义了一个word结构体 string str; int count; }; bool cmp(const Words &w1, const Words &w2) {//排序用到的比较函数 if (w1.count > w2.count) { return true; } if (w1.count == w2.count) { return w1.str < w2.str; } return false; } int main() { string word; char c; while (true) { scanf("%c",&c);//一个一个字母往里输入 if (c >= 'A'&&c <= 'Z' || c >= 'a'&&c <= 'z' || c >= '0'&&c <= '9' || c == '_') { if (c >= 'A'&&c <= 'Z') { c = (c - 'A' + 'a');//将大写字母转化为小写字母，统计词频不分大小写 } if (word.length() < 15) { word += c;//如果这个单词长度小于15，就把这个字母加到这个单词的末尾 } } else if (c == '#' || word.length() > 0) { if (!mp[word]) {//如果map里面没有这个单词，就插入这个单词，并把key（单词出现的次数）设为1 mp[word] = 1; } else { mp[word]++;//如果已经有了，就把频率+1 } word.clear();//把word清空，方便下一个单词输入 if (c == '#') { break;//如果输入等于#，则输入结束 } } } map<string, int>::iterator iter;//迭代器 vector<Words> vec;//定义一个Words类型的vector，方便排序 Words w; for (iter = mp.begin(); iter != mp.end(); iter++) {//通过迭代器遍历map //cout << iter->first << " " << iter->second << endl; if (iter->first.length()>0) { w.str = iter->first; w.count = iter->second; vec.push_back(w); } } sort(vec.begin(), vec.end(), cmp);//对vector进行排序 int count = vec.size()*0.1; cout << vec.size() << endl; for (int i = 0; i < count; i++) { cout << vec[i].count << ":" << vec[i].str << endl; } return 0; }
R7-3 新浪微博热门话题
新浪微博可以在发言中嵌入“话题”，即将发言中的话题文字写在一对“#”之间，就可以生成话题链接，点击链接可以看到有多少人在跟自己讨论相同或者相似的话题。新浪微博还会随时更新热门话题列表，并将最热门的话题放在醒目的位置推荐大家关注。
本题目要求实现一个简化的热门话题推荐功能，从大量英文（因为中文分词处理比较麻烦）微博中解析出话题，找出被最多条微博提到的话题。
输入格式:
输入说明：输入首先给出一个正整数N（≤105），随后N行，每行给出一条英文微博，其长度不超过140个字符。任何包含在一对最近的#中的内容均被认为是一个话题，输入保证#成对出现。
输出格式:
第一行输出被最多条微博提到的话题，第二行输出其被提到的微博条数。如果这样的话题不唯一，则输出按字母序最小的话题，并在第三行输出And k more ...，其中k是另外几条热门话题的条数。输入保证至少存在一条话题。
注意：两条话题被认为是相同的，如果在去掉所有非英文字母和数字的符号、并忽略大小写区别后，它们是相同的字符串；同时它们有完全相同的分词。输出时除首字母大写外，只保留小写英文字母和数字，并用一个空格分隔原文中的单词。
输入样例:
4 This is a #test of topic#. Another #Test of topic.# This is a #Hot# #Hot# topic Another #hot!# #Hot# topic
输出样例:
Hot 2 And 1 more ...
#include<bits/stdc++.h> //万能头文件，里面包含了大部分标准库 using namespace std; map<string,int> mp; //定义字符串-整数映射，用于存储每个单词出现的次数 string s; //定义字符串s，用于存储出现次数最多的单词 string set_string(string ss) //定义函数set_string，用于将字符串转换为小写字母、去除标点符号、去除多余空格 { string cnt; //定义字符串cnt，用于存储去除标点符号、多余空格后的结果 bool is_repeat=false; //定义布尔变量is_repeat，用于判断多余空格是否已经去除 for(int i=0; i<ss.length(); i++) //遍历字符串ss的所有字符 { if(ss[i]>='A'&&ss[i]<='Z') //如果是大写字母 { cnt+=(ss[i]-'A'+'a'); //转换为小写字母并添加到cnt中 is_repeat=false; //重置is_repeat为false } else if((ss[i]>='a'&&ss[i]<='z')||(ss[i]>='0'&&ss[i]<='9')) //如果是小写字母或数字 { cnt+=ss[i]; //添加到cnt中 is_repeat=false; //重置is_repeat为false } else if(!is_repeat) //如果是标点符号或多余空格，并且is_repeat为false { cnt+=' '; //添加一个空格到cnt中 is_repeat=true; //设置is_repeat为true } } if(cnt[cnt.length()-1]==' ') //如果cnt末尾是空格 cnt.erase(cnt.end()-1); //删除末尾的空格 return cnt; //返回去除标点符号、多余空格后的字符串 } string cmp(string s1,string s2) //定义函数cmp，用于比较两个字符串大小 { return s1<s2?s1:s2; //返回字典序较小的那个字符串 } int main() { int n; cin>>n; //读取输入的字符串数量 getchar(); //吞掉cin读取的回车符 while(n--) //循环读取每个字符串并统计其中的单词出现次数 { map<string,int> small_map; //定义map类型变量small_map，用于存储当前字符串中每个单词出现的次数 string ss; //定义字符串ss，用于存储从当前字符串中提取的单词 getline(cin,s); //读取当前字符串，注意要使用getline函数，否则会导致读取不完整 for(int i=0; i<s.length(); i++) //遍历当前字符串中的所有字符 { ss=""; //重置ss为空字符串 if(s[i]=='#') //如果当前字符是'#' { i++; //将i向后移动一位 while(s[i]!='#') //将i不断向后移动，并将所有不为'#'的字符添加到ss中 ss+=s[i++]; ss=set_string(ss); //调用set_string函数，将字符串转换为小写字母、去除标点符号、去除多余空格 } if(ss=="") //如果ss为空字符串，则跳过当前单词 continue; small_map[ss]++; //在small_map中增加当前单词的出现次数 } map<string,int>::iterator it; //定义map迭代器it for(it=small_map.begin(); it!=small_map.end(); it++) //遍历当前字符串中的所有单词 { mp[it->first]++; //在mp中增加当前单词的出现次数 } } int maxn=0,repeat=0; //定义maxn和repeat变量，分别表示出现次数最多的单词数量和与之出现次数相同的单词数量 map<string,int>::iterator it; //定义map迭代器it for(it=mp.begin();it!=mp.end();it++) //遍历mp中的所有单词 { if(it->second>maxn) //如果当前单词出现次数大于maxn { maxn=it->second; //更新maxn s=it->first; //更新出现次数最多的单词 repeat=0; //重置repeat为0 } else if(it->second==maxn) //如果当前单词出现次数等于maxn { s=cmp(s,it->first); //比较s和当前单词，更新s为字典序较小的那个字符串 repeat++; //增加repeat的值 } } cout<<(char)(s[0]-'a'+'A'); //将出现次数最多的单词首字母转换为大写，并输出 for(int i=1;i<s.length();i++) cout<<s[i]; //输出出现次数最多的单词剩下的部分 cout<<endl<<maxn<<endl; //输出出现次数最多的单词的出现次数 if(repeat) cout<<"And "<<repeat<<" more ..."<<endl; //如果还有与之出现次数相同的单词，则输出相应信息 }
R7-4 航空公司VIP客户查询
不少航空公司都会提供优惠的会员服务，当某顾客飞行里程累积达到一定数量后，可以使用里程积分直接兑换奖励机票或奖励升舱等服务。现给定某航空公司全体会员的飞行记录，要求实现根据身份证号码快速查询会员里程积分的功能。
输入格式:
输入首先给出两个正整数N（≤105）和K（≤500）。其中K是最低里程，即为照顾乘坐短程航班的会员,航空公司还会将航程低于K公里的航班也按K公里累积。随后N行，每行给出一条飞行记录。飞行记录的输入格式为：18位身份证号码（空格）飞行里程。其中身份证号码由17位数字加最后一位校验码组成，校验码的取值范围为0~9和x共11个符号；飞行里程单位为公里，是(0, 15 000]区间内的整数。然后给出一个正整数M（≤105），随后给出M行查询人的身份证号码。
输出格式:
对每个查询人，给出其当前的里程累积值。如果该人不是会员，则输出No Info。每个查询结果占一行。
输入样例:
4 500 330106199010080419 499 110108198403100012 15000 120104195510156021 800 330106199010080419 1 4 120104195510156021 110108198403100012 330106199010080419 33010619901008041x
输出样例:
800 15000 1000 No Info
#include<iostream> #include<map> using namespace std; map<string,int>p; int main() { int n,m,c,k; char s[100]; scanf("%d %d",&n,&m); for(int i=0;i<n;i++) { scanf("%s %d",s,&k); if(k>=m) p[s]+=k; else p[s]+=m; } scanf("%d",&c); while(c--) { scanf("%s",s); if(p.find(s)!=p.end()) printf("%d\n",p[s]); else printf("No Info\n"); } return 0; }
R7-1 字符串关键字的散列映射
给定一系列由大写英文字母组成的字符串关键字和素数P，用移位法定义的散列函数H(Key)将关键字Key中的最后3个字符映射为整数，每个字符占5位；再用除留余数法将整数映射到长度为P的散列表中。例如将字符串AZDEG插入长度为1009的散列表中，我们首先将26个大写英文字母顺序映射到整数0~25；再通过移位将其映射为3×322+4×32+6=3206；然后根据表长得到3206%1009=179，即是该字符串的散列映射位置。
发生冲突时请用平方探测法解决。
输入格式:
输入第一行首先给出两个正整数N（≤500）和P（≥2N的最小素数），分别为待插入的关键字总数、以及散列表的长度。第二行给出N个字符串关键字，每个长度不超过8位，其间以空格分隔。
输出格式:
在一行内输出每个字符串关键字在散列表中的位置。数字间以空格分隔，但行末尾不得有多余空格。
输入样例1:
4 11 HELLO ANNK ZOE LOLI
输出样例1:
3 10 4 0
输入样例2:
6 11 LLO ANNA NNK ZOJ INNK AAA
输出样例2:
3 0 10 9 6 1
#include<iostream> // 包含输入输出流的头文件 #include<map> // 包含map容器的头文件 using namespace std; map<string, int> p; // 定义一个键为字符串、值为整数的map容器p int main() { int n, m, c, k; // 定义整数变量n、m、c和k char s[100]; // 定义字符数组s，用于存储字符串 scanf("%d %d", &n, &m); // 读取n和m的值 for(int i = 0; i < n; i++) // 循环读取n个数据 { scanf("%s %d", s, &k); // 读取字符串s和整数k if(k >= m) // 如果k大于等于m p[s] += k; // 在map p中，键为s的值增加k else p[s] += m; // 在map p中，键为s的值增加m } scanf("%d", &c); // 读取查询次数c while(c--) // 循环进行c次查询 { scanf("%s", s); // 读取字符串s if(p.find(s) != p.end()) // 在map p中查找键为s的值 printf("%d\n", p[s]); // 输出找到的值 else printf("No Info\n"); // 输出未找到信息 } return 0; }
以上就是本篇的全部内容，在注释中理解思路即可。在下一篇中我们将进行并查集的学习。
