20. 电话号码

商业单位需要容易记忆的电话号码，有一些方法可以让电话号码变得更容易记忆。譬如，可以把电话号码写成单词或短语，如 MON-GLOP 可以代表滑铁卢大学的电话。有时仅仅是把号码的一部分写成单词，如打 310-GINO 便可向 GINO 比萨饼店定购比萨。另一种让电话号码容易记忆的方法是将数字用一种容易记的方式组合起来，譬如 3-10-10-10 也可以代表 GINO 比萨饼店。

电话号码的标准形式是七位十进制数字，在它的第三位和第四位之间用连字符连接(例如：666-1200)。电话的键盘提供了字符与数字之间的映射关系，如下所示：

Q 和 Z 没有映射到键盘，而连字符不需要被拨打并且可以根据需要添加和删除。MON-GLOP 的标准形式是 666-4567，310-GINO 的标准形式是310-4466，3-10-10-10的标准形式也是 310-1010。如果两个电话号码有相同的标准形式，那么这两个电话号码是相同的。

现在请你编辑一本商业单位的电话簿，作为质量控制流程的一部分，你需要确认在该电话簿中有没有错误的电话号码，以及有没有两个(或两个以上的)商业单位使用相同的电话号码。由于当地只使用了 3 和 6 两个区段，因此电话号码的第一个数字应当永远是 3 或者 6，如果出现了其它数字，就表示这个电话号码错了。此外，如果电话号码中出现了 Q 和 Z，也说明这个电话错了。

输入

一次输入为一个样例。每个号码一行，每行的字符不会超过 20 个。每次输入的数据不超过 3000000 个电话号码。假设输入中可能会出现重复的电话号码不超过 1500 个，每个号码重复的次数不超过 1000 次。

输出

输出包括两个部分，第一个部分是错误的电话号码，对于这些号码应当按照输入的顺序以原始的形式输出。在输出错误电话号码前输出“Error:”，随后输出这些号码，如果没有错误的电话号码，则输出“Not found.”。

第二部分是重复的电话号码，对每一个在电话簿中以任何形式出现一次以上的电话号码，生成一行输出。这一行应以标准形式给出电话号码，其后跟随一个空格，空格后跟随电话号码在电话簿中出现的次数。所有重复的电话号码输出行应以号码的升序排列（小号码在前）。在输出重复电话号码前输出“Duplication”，随后按照上述格式输出号码，如果在输入中没有重复的电话号码，则输出：“Not found.”。

//这题感觉好难想到还有那么巧的方法
//看了网上大佬的思路，有一种叫位图法的思想
//用一个unsigned char型的数组或是unsigned int型的数组来存储，如果用char来存储
//先将电话号码判断之后转化为一个百万大小的数字，然后由于首位不是3就是6，所以取后面的6位进行存储即可
//假设这个数是i，那么就可以用c[i/8]=c[i/8]|1<<i%8来进行标记，可以通过判断c[i/8]&1<<i%8是否大于0来判断这个电话是否存在
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h>struct node {int num;int count; }; struct node TelStr[1505];int cmp(const void *a, const void *b) {return ((struct node*)a)->num - ((struct node*)b)->num; }int main() {unsigned char Num3[250005] = { 0 }, Num6[250005] = { 0 };//Num3储存3开头，Num6储存6开头int flag1 = 0, flag2 = 0, flag3 = 0;//flag1标记是否有错误输入，flag2标记,flag3标记输入的串中是否有Q和Zchar IN_Tel[25] = { '\0' };int T_count = 0;int ch;printf("Error:\n");while (1){flag3 = 0;//数据输入，用getchar()会快一点memset(IN_Tel, '\0', sizeof(IN_Tel));int len = 0;ch = getchar();if (ch < 0)break;else{IN_Tel[len++] = ch;while (1){ch = getchar();if (ch == 10)break;else IN_Tel[len++] = ch;}}int per = 0;while (IN_Tel[per] == '-')per++;if (IN_Tel[per] != '3'&&IN_Tel[per] != 'D'&&IN_Tel[per] != 'E'&&IN_Tel[per] != 'F') //电话号码的首位必为3/6if (IN_Tel[per] != '6'&&IN_Tel[per] != 'M'&&IN_Tel[per] != 'N'&&IN_Tel[per] != 'O'){printf("%s\n", IN_Tel);flag1 = 1;continue;}for (int i = 0; i < len; i++)//电话号码中不能出现Q和Zif (IN_Tel[i] == 'Q' || IN_Tel[i] == 'Z'){printf("%s\n", IN_Tel);flag3 = 1;flag1 = 1;break;}if (flag3)continue;for (int i = 0; i < len; i++)//全部转成标准型if (IN_Tel[i] == 'A' || IN_Tel[i] == 'B' || IN_Tel[i] == 'C')IN_Tel[i] = '2';else if (IN_Tel[i] == 'D' || IN_Tel[i] == 'E' || IN_Tel[i] == 'F')IN_Tel[i] = '3';else if (IN_Tel[i] == 'G' || IN_Tel[i] == 'H' || IN_Tel[i] == 'I')IN_Tel[i] = '4';else if (IN_Tel[i] == 'J' || IN_Tel[i] == 'K' || IN_Tel[i] == 'L')IN_Tel[i] = '5';else if (IN_Tel[i] == 'M' || IN_Tel[i] == 'N' || IN_Tel[i] == 'O')IN_Tel[i] = '6';else if (IN_Tel[i] == 'P' || IN_Tel[i] == 'R' || IN_Tel[i] == 'S')IN_Tel[i] = '7';else if (IN_Tel[i] == 'T' || IN_Tel[i] == 'U' || IN_Tel[i] == 'V')IN_Tel[i] = '8';else if (IN_Tel[i] == 'W' || IN_Tel[i] == 'X' || IN_Tel[i] == 'Y')IN_Tel[i] = '9';int GroupW = 0;//控制组位，前3个一组，后4个一组，***-****不能用数组变量计，有‘-’会干扰int Group1 = 0,Group2 = 0;for (int i = 0; i < len; i++)if (IN_Tel[i] != '-'){GroupW++;if (GroupW < 4)Group1 += (IN_Tel[i] - '0')*pow(10.0, 3 - GroupW);elseGroup2 += (IN_Tel[i] - '0')*pow(10.0, 7 - GroupW);}int sum = 10000 * Group1 + Group2;if (sum<4000000 && sum>2999999)//处理首位为3的电话号码{int GetPoint = sum % 3000000;//为了得到位图法的位点if ((Num3[GetPoint / 4] & 1 << (GetPoint % 4)) != 0){int flagg = 0;for (int i = 0; i < T_count; i++)if (TelStr[i].num == sum){TelStr[i].count++;flagg = 1;break;}if (!flagg){TelStr[T_count].num = sum;TelStr[T_count].count = 1;T_count++;}}elseNum3[GetPoint / 4] = Num3[GetPoint / 4] | 1 << GetPoint % 4;}else if (sum>5999999 && sum<7000000)//处理首位为6的电话号码{int GetPoint = sum % 6000000;if ((Num6[GetPoint / 4] & 1 << (GetPoint % 4)) > 0){int flagg = 0;for (int i = 0; i < T_count; i++)if (TelStr[i].num == sum){TelStr[i].count++;flagg = 1;break;}if (!flagg){TelStr[T_count].num = sum;TelStr[T_count].count = 1;T_count++;}}elseNum6[GetPoint / 4] = Num6[GetPoint / 4] | 1 << GetPoint % 4;}}if (!flag1)printf("Not found.\n");printf("\nDuplication:\n");qsort(TelStr, T_count, sizeof(struct node), cmp);for (int i = 0; i < T_count; i++)if (TelStr[i].count > 0){flag2 = 1;TelStr[i].count++;printf("%03d-%04d %d\n", TelStr[i].num / 10000, TelStr[i].num % 10000, TelStr[i].count);}if (!flag2)printf("Not found.\n");return 0; }