MyException - 我的异常网
当前位置:我的异常网» 综合 » 487-3279 UVA 755 其实有三种解法

487-3279 UVA 755 其实有三种解法

www.MyException.Cn  网友分享于:2014-08-05  浏览:0次
487--3279 UVA 755 其实有三种解法

说说:这道题初看挺简单的,题意无非就是将一串字符转化成一个用‘-’隔开的电话号码,然后把出现超过一次的号码按照字典升序输出即可。但是这样样做是会超时的....其实把电话号码中间的‘-’去掉,电话号码其实就是一个整数,有了这个想法那就简单啦。只要设立一个超大的数组包含所有可能的电话号码,然后数组的值是该号码出现的次数,统计完后遍历一遍输出即可。但是第三种相当于把前两种方法法结合起来了。把号码当成一个整数,但是号码存储在一个数组中,号码出现的次数存储在另一个数组中。这样在插入新号码的时候就排序,然后就超时了。总的来说,不能排序,因为数据量比较大,最后肯定会超时的。


题目:

487--3279

Businesses like to have memorable telephone numbers. One way to make a telephone number memorable is to have it spell a memorable word or phrase. For example,

商务人士都喜欢容易记住的电话号码。让号码听起来像一个易记的单词或短语是一种很好的方法。

you can call the University of Waterloo by dialing the memorable TUT-GLOP. Sometimes only part of the number is used to spell a word. When you get back to your hotel

比如你打Waterloo大学的电话就拨TUT-GLOP。有时只有一部分的数字用于组成一个单词。当你在今天晚上回到你的酒店的时候

tonight you can order a pizza from Gino's by dialing 310-GINO. Another way to make  a telephone number memorable is to group the digits in a memorable way. You

你可以拨打310-GINO从GION预订披萨。另一种让电话号码易记的方法是用一种易记的方式组织数字。

could order your pizza from Pizza Hut by calling their ``three tens'' number 3-10-10-10.

你可以从PIZZA HUT预订披萨通过拨打三个十------  3-10-10-10


The standard form of a telephone number is seven decimal digits with a hyphen between the third and fourth digits (e.g. 888-1200). The keypad of a phone supplies the

标准的电话号码形式是七个十进制数,并且在第三个和第四个数之间有一个连字符(例如:888-1200).一个手机的键盘提供了一种从字母到数字的映射

mapping of letters to numbers, as follows:

如下所示:


A, B, and C map to 2

D, E, and F map to 3

G, H, and I map to 4

J, K, and L map to 5

M, N, and O map to 6

P, R, and S map to 7

T, U, and V map to 8

W, X, and Y map to 9


There is no mapping for Q or Z. Hyphens are not dialed, and can be added and removed as necessary.The standard form of TUT-GLOP is 888-4567, the standard form of

其中并没有到Q或Z的映射。连字符在拨号时不必使用,在必要的时候可用可不用。TUT-GLOP的标准形式是888-4567,310-GINO的标准形式是310-4466,3-10-10-10的标准形

310-GINO is 310-4466, and the standard form of 3-10-10-10 is 310-1010.

式是310-1010.


Two telephone numbers are equivalent if they have the same standard form. (They dial the same number.)

如果两个电话号码有同样的标准形式,那么它们就是完全等价的。


Your company is compiling a directory of telephone numbers from local businesses. As part of the quality control process you want to check that no two (or more)

你的公司现在正在编写一部关于本地商业信息的电话号码本。作为质量控制,你现在要确保在电话本中没有两个(或更多)的电话是一样的。

businesses in the directory have the same telephone number.

INPUT

The first line of the input contains the number of data sets in the input. A blank line follows. The first line of each data set specifies the number of telephone numbers in the

第一行的输入是输入数据集的个数。接下来会有一个空白行。每个输入数据集的第一行是一个正数,指明了电话本中电话号码的数目(最大为100,000)。

directory (up to 100,000) as a positive integer alone on the line. The remaining lines list the telephone numbers in the directory, with each number alone on a line. Each

接下来每一行是电话本中的一个号码。

telephone number consists of a string composed of decimal digits, uppercase letters (excluding Q and Z) and hyphens. Exactly seven of the characters in the string will be

每个电话号码由十进位数字,大写字母(除了Q和Z)以及连字符组成且数字和字母的总数刚好是七个。

digits or letters. There's a blank line between data sets.

每个数据集直接有一个空行。

OUTPUT

Generate a line of output for each telephone number that appears more than once in any form. The line should give the telephone number in standard form, followed by a

首先将那些以任何形式出现过一次以上的电话号码以标准形式输出,并且接下来输出一个空格,接着输出电话号码在电话本中出现的次数。

space, followed by the number of times the telephone number appears in the directory. Arrange the output lines by telephone number in ascending lexicographical order. If

而且输出的电话号码必须按字典升序输出。

there are no duplicates in the input print the line:

如果没有重复的电话号码则输出:

No duplicates.

Print a blank line between data sets.

在数据集的输出直接输出一行空行。


SAMPLE INPUT

1

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


源代码:

解法2:(AC过的,但还是要600多毫秒= =)

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAXN 10000000+5

int tel[MAXN];//数组下标是电话号码,数组值是下标对应的号码出现的次数
int N,M,count;
char new_tel[50];

int to_standard(char*);//电话转化为数字
char AtoD(char);//字母转化为数字

int main(){
 int i,pos,val;
 
// freopen("data","r",stdin);
 scanf("%d",&M);

 while(M--){
  scanf("%d",&N);
  count=0;
  memset(tel,0,sizeof(tel));
  for(i=0;i<N;i++){

   scanf("%s",new_tel);
   val=to_standard(new_tel);
   if(tel[val]==0)//号码未出现过
    count++;

   tel[val]++;
  }

  if(count==N)//号码每个都不同
   printf("No duplicates.\n");
  else
   for(i=0;i<MAXN;i++)
    if(tel[i]>1)
     printf("%03d-%04d %d\n",i/10000,i%10000,tel[i]);
   if(M) putchar('\n');
 }

 return 0;
}

int to_standard(char *new_tel){//字符号码转化为整数值
 int i=0;
 int val=0;

 while(new_tel[i]){
  if(isdigit(new_tel[i]))
   val=val*10+new_tel[i++]-'0';
  else if(new_tel[i]=='-'){
   i++;
   continue;
  }
  else
   val=val*10+AtoD(new_tel[i++])-'0';
 }

 return val;
}

char AtoD(char c){//字母转化为数字
 
 if(c>'Q')
 c--;

 return '2'+(c-'A')/3;
}

为了保证文章的长度,另外两种方法就不贴代码啦。嘿嘿~




文章评论

代码女神横空出世
代码女神横空出世
中美印日四国程序员比较
中美印日四国程序员比较
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
10个调试和排错的小建议
10个调试和排错的小建议
编程语言是女人
编程语言是女人
鲜为人知的编程真相
鲜为人知的编程真相
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
我的丈夫是个程序员
我的丈夫是个程序员
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
总结2014中国互联网十大段子
总结2014中国互联网十大段子
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
老程序员的下场
老程序员的下场
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
旅行,写作,编程
旅行,写作,编程
程序员必看的十大电影
程序员必看的十大电影
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
程序员和编码员之间的区别
程序员和编码员之间的区别
每天工作4小时的程序员
每天工作4小时的程序员
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
那些争议最大的编程观点
那些争议最大的编程观点
一个程序员的时间管理
一个程序员的时间管理
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
程序员应该关注的一些事儿
程序员应该关注的一些事儿
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
 程序员的样子
程序员的样子
为什么程序员都是夜猫子
为什么程序员都是夜猫子
程序员的鄙视链
程序员的鄙视链
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
漫画:程序员的工作
漫画:程序员的工作
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
Java程序员必看电影
Java程序员必看电影
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
程序员都该阅读的书
程序员都该阅读的书
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
如何成为一名黑客
如何成为一名黑客
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有