7-11 QQ帐户的申请与登陆
实现QQ新帐户申请和老帐户登陆的简化版功能。最大挑战是：据说现在的QQ号码已经有10位数了。
输入格式:
输入首先给出一个正整数N（≤10
5
），随后给出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
解析
/** * 7-11 QQ帐户的申请与登陆 * 哈希表 分离链接法 */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> /*账号与密码最大长度的定义 它们的最大长度需要比题目所给的大一位 这是因为还需要一个位置来储存'\0'来判断字符串的结尾*/ #define Max_Password_Len 17 #define Max_Account_Len 11 #define MaxTableSize 1000000 /*各种状态的定义 最好用正数表示成功的状态 用负数或0表示失败的状态 这样会让强迫症看了舒服一点*/ #define ERROR_WrongPW -2 #define ERROR_Exist -1 #define ERROR_NOTExist 0 #define New_OK 1 #define Login_OK 2 typedef char AccountType[Max_Account_Len];//账号类型定义 typedef char PasswordType[Max_Password_Len];//密码类型定义 typedef int Index; typedef enum { New, Log } Pattern;//两种模式，新建账号与登入账号 typedef struct { AccountType Account; PasswordType Password; } ElemType;//数据类型的定义，每个对应一个用户，内含用户的账号和密码 //链表指针的定义 typedef struct LNode *PtrToLNode; //链表结点的定义 typedef struct LNode { PtrToLNode Next; ElemType Data; } LNode; typedef PtrToLNode List;//链表的定义 typedef PtrToLNode Position;//哈希表中结点位置的定义 //哈希表的定义 typedef struct TblNode *HashTable; typedef struct TblNode { int TableSize;//哈希表的大小 List Heads;//储存各个列表头节点的数组 } TblNode; int NextPrime(int N)//返回N的下一个素数 { int i, P; P = N % 2 ? N + 2 : N + 1; //P为N之后的第一个奇数 while (P < MaxTableSize) { for (i = (int) sqrt(P); i > 2; i--)//因为只考虑奇数，所以i为2时就结束了 if (P % i == 0) break; if (i == 2) break;//i为2说明P为素数 else P += 2;//i!=2说明P不是素数，则P指向下一个奇数 } return P; } int Hash(int Key, int TableSize) {//返回Key值相对应的哈希值，即其在哈希表中的储存下标 return Key % TableSize; } HashTable CreateTable(int TableSize) { //构造空的哈希表 HashTable H; int i; H = (HashTable) malloc(sizeof(TblNode)); H->TableSize = NextPrime(TableSize); H->Heads = (List) malloc(sizeof(LNode) * H->TableSize); for (i = 0; i < H->TableSize; i++) { H->Heads[i].Data.Account[0] = '\0'; H->Heads[i].Data.Password[0] = '\0'; H->Heads[i].Next = NULL; } return H; } Position Find(HashTable H, ElemType Key) { Position Pos; Index p; if (strlen(Key.Account) > 5) //账号大于5位时取最后5位 p = Hash(atoi(Key.Account + strlen(Key.Account) - 5), H->TableSize); else//账号不大于5位则等于它本身 p = Hash(atoi(Key.Account), H->TableSize); Pos = H->Heads[p].Next; while (Pos && strcmp(Key.Account, Pos->Data.Account)) Pos = Pos->Next; return Pos;//Pos指向用户数据的位置，没有注册就返回NULL } int NewOrLog(HashTable H, ElemType Key, Pattern P) { //返回状态参数 Position Pos, NewPos; Index p; Pos = Find(H, Key); switch (P) { case Log: if (Pos == NULL) return ERROR_NOTExist;//登陆时不存在账号 else if (strcmp(Pos->Data.Password, Key.Password) || (strlen(Key.Password) > 16 || strlen(Key.Password) < 6)) return ERROR_WrongPW; //密码错误或格式错误 else return Login_OK;//账号和密码均正确，可以登录 case New: if (Pos != NULL) return ERROR_Exist; //新建账号时发现已经存在这样的账号了 else { NewPos = (Position) malloc(sizeof(LNode)); strcpy(NewPos->Data.Account, Key.Account); strcpy(NewPos->Data.Password, Key.Password); if (strlen(Key.Account) > 5) p = Hash(atoi(Key.Account + strlen(Key.Account) - 5), H->TableSize); else p = Hash(atoi(Key.Account), H->TableSize); NewPos->Next = H->Heads[p].Next; H->Heads[p].Next = NewPos; return New_OK; //插入新值并返回插入成功 } } } void DestroyTable(HashTable H) { //销毁哈希表 PtrToLNode p, q; int i; for (i = 0; i < H->TableSize; i++) { q = H->Heads[i].Next; while (q) { p = q->Next; free(q); q = p; } } free(H); } int main(void) { int N, i; ElemType Key; char Input; Pattern P; HashTable H; scanf("%d", &N); H = CreateTable(2 * N); for (i = 0; i < N; i++) { scanf("\n%c %s %s", &Input, Key.Account, Key.Password); P = (Input == 'L') ? Log : New; switch (NewOrLog(H, Key, P)) {//最后根据不同返回值输出对应状态即可 case ERROR_Exist: printf("ERROR: Exist\n"); break; case ERROR_NOTExist: printf("ERROR: Not Exist\n"); break; case ERROR_WrongPW: printf("ERROR: Wrong PW\n"); break; case Login_OK: printf("Login: OK\n"); break; case New_OK: printf("New: OK\n"); break; } } DestroyTable(H); return 0; }
7-12 人以群分
社交网络中我们给每个人定义了一个“活跃度”，现希望根据这个指标把人群分为两大类，即外向型（outgoing，即活跃度高的）和内向型（introverted，即活跃度低的）。要求两类人群的规模尽可能接近，而他们的总活跃度差距尽可能拉开。
输入格式：
输入第一行给出一个正整数N（2≤N≤10
5
）。随后一行给出N个正整数，分别是每个人的活跃度，其间以空格分隔。题目保证这些数字以及它们的和都不会超过2
31
。
输出格式：
按下列格式输出：
Outgoing #: N1 Introverted #: N2 Diff = N3
其中N1是外向型人的个数；N2是内向型人的个数；N3是两群人总活跃度之差的绝对值。
输入样例1：
10 23 8 10 99 46 2333 46 1 666 555
输出样例1：
Outgoing #: 5 Introverted #: 5 Diff = 3611
输入样例2：
13 110 79 218 69 3721 100 29 135 2 6 13 5188 85
输出样例2：
Outgoing #: 7 Introverted #: 6 Diff = 9359
解析
/** * 7-12 人以群分 * 排序 */ #include <stdio.h> #include <stdlib.h> int comfunc(const void *elem1, const void *elem2); void sort_character(int *p, int n); int main() { int n, i; int a[100001]; scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &a[i]); qsort(a, n, sizeof(int), comfunc); sort_character(a, n); return 0; } int comfunc(const void *elem1, const void *elem2) { int *p1 = (int *) elem1; int *p2 = (int *) elem2; return *p1 - *p2; } void sort_character(int *p, int n) { int i, j, n1, n2, sum1, sum2, dif, dif1, dif2; sum1 = sum2 = 0; dif = dif1 = dif2 = 0; if (n % 2 == 0) { n1 = n2 = n / 2; for (i = 0; i < n1; i++) sum1 += p[i]; for (i = n1; i < n; i++) sum2 += p[i]; dif = abs(sum2 - sum1); } else { n1 = n2 = n / 2; for (i = 0; i < n1; i++) sum1 += p[i]; for (i = n / 2 + 1; i < n; i++) sum2 += p[i]; dif1 = abs(sum1 + p[n1] - sum2); dif2 = abs(sum2 + p[n2] - sum1); dif = (dif1 > dif2) ? dif1 : dif2; if (dif1 > dif2) n1++; else n2++; } printf("Outgoing #: %d\n", n2); printf("Introverted #: %d\n", n1); printf("Diff = %d\n", dif); }
7-13 寻找大富翁
胡润研究院的调查显示，截至2017年底，中国个人资产超过1亿元的高净值人群达15万人。假设给出N个人的个人资产值，请快速找出资产排前M位的大富翁。
输入格式:
输入首先给出两个正整数N（≤10
6
）和M（≤10），其中N为总人数，M为需要找出的大富翁数；接下来一行给出N个人的个人资产值，以百万元为单位，为不超过长整型范围的整数。数字间以空格分隔。
输出格式:
在一行内按非递增顺序输出资产排前M位的大富翁的个人资产值。数字间以空格分隔，但结尾不得有多余空格。
输入样例:
8 3 8 12 7 3 20 9 5 18
输出样例:
20 18 12
解析
/** * 7-13 寻找大富翁 * 堆排序和选择排序 */ #include <stdio.h> //堆排序； 注意:此算法中，下标从1开始 #define max 1000010 int num[max]; void sift(int *num, int low, int high) //将下标为low位置上的点调到适当位置 { int i, j, temp; i = low; j = 2 * i; //num[j]是num[i]的左孩子结点； temp = num[i]; //待调整的结点 while (j <= high) { if (j < high && num[j] < num[j + 1]) //如果右孩子比较大，则把j指向右孩子，j变为2*i+1； ++j; if (temp < num[j]) { num[i] = num[j]; //将num[j]调整到双亲结点的位置上； i = j; //修改i和j的值，以便继续向下调整； j = i * 2; } else break; //调整结束； } num[i] = temp; //被调整的结点放入最终位置 } int main() { int n, m, i, temp, count = 0; scanf("%d%d", &n, &m); for (i = 1; i <= n; i++) scanf("%d", &num[i]); if (n < m) m = n; //注意，有一个测试点是n小于m的情况，这时，只用排前n个; for (i = n / 2; i >= 1; i--) //所有结点建立初始堆 sift(num, i, n); for (i = n; i >= 2; i--) //进行n-1次循环，完成堆排序 { /*以下3句换出了根节点中的关键字，将其放入最终位置*/ temp = num[1]; num[1] = num[i]; num[i] = temp; count++; if (count == 1) printf("%d", num[i]); else printf(" %d", num[i]); if (count == m) break; //打印前m个； sift(num, 1, i - 1); //减少了1个关键字的无序序列，继续调整。 } if (m == n) printf(" %d", num[1]); //当n<m的特殊情况下，上面只打印了n~2，还有最后一个下标为1的没有打印，故再打印一个。 return 0; }
7-14 PAT排名汇总
计算机程序设计能力考试（Programming Ability Test，简称PAT）旨在通过统一组织的在线考试及自动评测方法客观地评判考生的算法设计与程序设计实现能力，科学的评价计算机程序设计人才，为企业选拔人才提供参考标准（网址http://www.patest.cn）。
每次考试会在若干个不同的考点同时举行，每个考点用局域网，产生本考点的成绩。考试结束后，各个考点的成绩将即刻汇总成一张总的排名表。
现在就请你写一个程序自动归并各个考点的成绩并生成总排名表。
输入格式:
输入的第一行给出一个正整数N（≤100），代表考点总数。随后给出N个考点的成绩，格式为：首先一行给出正整数K（≤300），代表该考点的考生总数；随后K行，每行给出1个考生的信息，包括考号（由13位整数字组成）和得分（为[0,100]区间内的整数），中间用空格分隔。
输出格式:
首先在第一行里输出考生总数。随后输出汇总的排名表，每个考生的信息占一行，顺序为：考号、最终排名、考点编号、在该考点的排名。其中考点按输入给出的顺序从1到N编号。考生的输出须按最终排名的非递减顺序输出，获得相同分数的考生应有相同名次，并按考号的递增顺序输出。
输入样例:
2 5 1234567890001 95 1234567890005 100 1234567890003 95 1234567890002 77 1234567890004 85 4 1234567890013 65 1234567890011 25 1234567890014 100 1234567890012 85
输出样例:
9 1234567890005 1 1 1 1234567890014 1 2 1 1234567890001 3 1 2 1234567890003 3 1 2 1234567890004 5 1 4 1234567890012 5 2 2 1234567890002 7 1 5 1234567890013 8 2 3 1234567890011 9 2 4
解析
/** * 7-14 PAT排名汇总 * 快速排序 */ #include <stdio.h> #include <string.h> struct stu { char id[14]; //考号 int score; //分数 int kc; //考场 }; struct stu a[30000]; int bigger(const char *s1, const char *s2) { for (int i = 0; i < 13; i++) if (s1[i] > s2[i]) return 1; else if (s1[i] < s2[i]) return 0; return 1; } void qsort(int l, int r) { if (l >= r) return; int i = l; int j = r; struct stu t = a[l]; while (i != j) { while (i < j && (a[j].score < t.score || a[j].score == t.score && bigger(a[j].id, t.id))) j--; while (i < j && (a[i].score > t.score || a[i].score == t.score && bigger(t.id, a[i].id))) i++; if (i < j) { struct stu s = a[i]; a[i] = a[j]; a[j] = s; } } a[l] = a[i]; a[i] = t; qsort(l, i - 1); qsort(i + 1, r); return; } void Copy(int *b2, int *b1, int n) { for (int i = 1; i <= n; i++) b2[i] = b1[i]; } int main() { int n, j, i, top = 0; scanf("%d", &n); for (i = 1; i <= n; i++) { int k; scanf("%d", &k); for (j = 0; j < k; j++) { char id[14]; int score; scanf("%s %d", id, &score); a[top].score = score; a[top].kc = i; strcpy(a[top].id, id); top++; } } qsort(0, top - 1); int levall = 1, b1[n + 1], b2[n + 1], score = a[0].score; for (i = 1; i <= n; i++) b1[i] = 1, b2[i] = 1; printf("%d\n", top); printf("%s %d %d %d\n", a[0].id, 1, a[0].kc, 1); int llevall = 1; //上一个总排名 levall = 2; //总排名 Copy(b2, b1, n); b1[a[0].kc]++; for (i = 1; i < top; i++) { if (a[i].score == a[i - 1].score) { printf("%s %d %d %d\n", a[i].id, llevall, a[i].kc, b2[a[i].kc]); levall++; b1[a[i].kc]++; } else { printf("%s %d %d %d\n", a[i].id, levall, a[i].kc, b1[a[i].kc]); llevall = levall; levall++; Copy(b2, b1, n); b1[a[i].kc]++; //考场的排名 } } return 0; }
