http://poj.org/problem?id=1002
Description
企业喜欢用容易被记住的电话号码。让电话号码容易被记住的一个办法是将它写成一个容易记住的单词或者短语。例如,你需要给滑铁卢大学打电话时,可以拨打TUT-GLOP。有时,只将电话号码中部分数字拼写成单词。当你晚上回到酒店,可以通过拨打310-GINO来向Gino's订一份pizza。让电话号码容易被记住的另一个办法是以一种好记的方式对号码的数字进行分组。通过拨打必胜客的“三个十”号码3-10-10-10,你可以从他们那里订pizza。
电话号码的标准格式是七位十进制数,并在第三、第四位数字之间有一个连接符。电话拨号盘提供了从字母到数字的映射,映射关系如下:
A, B, 和C 映射到 2
D, E, 和F 映射到 3
G, H, 和I 映射到 4
J, K, 和L 映射到 5
M, N, 和O 映射到 6
P, R, 和S 映射到 7
T, U, 和V 映射到 8
W, X, 和Y 映射到 9
Q和Z没有映射到任何数字,连字符不需要拨号,可以任意添加和删除。 TUT-GLOP的标准格式是888-4567,310-GINO的标准格式是310-4466,3-10-10-10的标准格式是310-1010。
如果两个号码有相同的标准格式,那么他们就是等同的(相同的拨号)
你的公司正在为本地的公司编写一个电话号码薄。作为质量控制的一部分,你想要检查是否有两个和多个公司拥有相同的电话号码。
Input
输入的格式是,第一行是一个正整数,指定电话号码薄中号码的数量(最多100000)。余下的每行是一个电话号码。每个电话号码由数字,大写字母(除了Q和Z)以及连接符组成。每个电话号码中只会刚好有7个数字或者字母。
Output
对于每个出现重复的号码产生一行输出,输出是号码的标准格式紧跟一个空格然后是它的重复次数。如果存在多个重复的号码,则按照号码的字典升序输出。如果输入数据中没有重复的号码,输出一行:
"No duplicates. "
Sample Input
12
4873279
ITS-EASY
888-4567
3-10-10-10
888-GLOP
TUT-GLOP
967-11-11
310-GINO
F101010
888-1200
-4-8-7-3-2-7-9-
487-3279
Sample Output
310-1010 2
487-3279 4
888-4567 3
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;
char map[] = {"2223334445556667777888999"}; //简洁的映射
struct str{
char s[50];
}x[100005];
bool cmp (const str &a, const str &b)
{
return strcmp (a.s, b.s) < 0; //按字典序对结构进行排序
}
int main()
{
char s1[50];
bool flag;
int i, n, k, j, len, num;
//scanf ("%d", &t);
while (scanf ("%d", &n) != EOF)
{
for (i = 0; i < n; i++)
{
k = 0;
scanf ("%s", s1);
len = strlen(s1);
for (j = 0; j < len; j++)
{
if (s1[j] == '-')
continue;
if (isalpha(s1[j]))
x[i].s[k++] = map[s1[j]-'A'];
else x[i].s[k++] = s1[j];
if (k == 3)
x[i].s[k++] = '-'; //中间加上‘-’便于输出
}
x[i].s[k] = 0; //封死字符串
}
sort (x, x+n, cmp); //sort不可直接排字符串数组,但是可以把它先放到结构体中实现
/*cout << endl;
for (i = 0; i < n; i++)
cout << x[i].s << endl;*/
num = 1;
flag = false;
strcpy (x[n].s, "0"); //添加结束标志
for (i = 1; i <= n; i++) //不可漏掉i==n,否则无法输出最后一个符合情况的字符串
{
if (!strcmp (x[i].s, x[i-1].s))
num++;
else if (num > 1)
{
flag = true;
printf ("%s %d\n", x[i-1].s, num);
num = 1;
}
}
if (!flag)
puts ("No duplicates.");
}
return 0;
}
分享到:
相关推荐
北大POJ1002-487-3279【Hash+Qsort】 解题报告+AC代码
这是北大在线测试的第1002题,方便记忆的电话号码的解题例程,题目中有一个列表,记录着许多方便记忆的电话号码。不同的方便记忆的电话号码可能对应相同的标准号码,这个程序的任务就是找到它们
East Central North America 1999。50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50...
487-3279 Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 102808 Accepted: 17241 Description Businesses like to have memorable telephone numbers. One way to make a telephone number ...
业余爱好。所以,算法不一定好,CODING也不一定佳,效率不一定高,只是能通过online judge而已。
2遍dp poj_3613解题报告 poj_3613解题报告
如题所示,亲测可用。电话号码查重,不会的同学可以参考下,会做的同学可以给挑挑毛病!大家以代码会友!
Time Limit: 1000ms Memory limit: 65536kB 题目描述 有9个时钟,排成一个3*3的矩阵。 现在需要用最少的移动,将9个时钟的指针都拨到12点的位置。共允许有9种不同的移动。如右表所示,每个移动会将若干个时钟的...
poj题目2775文件子目录源代码,递归经典题目,
poj典型题目解题思路详解 包含源代码和解题时应注意的问题及题目陷阱设计分析
poj 1699的代码和方法说明,个人原创
C_(POJ_1854)(分治).cpp
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了
D_(POJ_1723)(思维)(sort).cpp
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
D_(POJ_1723)(思维)(第k大数).cpp
POJ 3131 双向BFS解立体八数码问题
O(nlogn)凸包问题 poj2187
poj两道题的c++实现。已经测试过可以通过oj