[原创]希望路过的大牛们指出错误

主题：[原创]希望路过的大牛们指出错误

x66f [专家分：10] 发布于 2010-12-03 11:01:00

附件是140万行的测试数据
希望路过的大牛们指出错误
在我的电脑上测试通过，但是不知道为什么在北大ACM平台测试通过不了，总是Wrong Answer，希望路过的大牛们指出错误，O(∩_∩)O谢谢
题目如下：1002号题目 http://poj.org/problem?id=1002&lang=zh-CN&change=true

电话号码的标准格式是七位十进制数，并在第三、第四位数字之间有一个连接符。电话拨号盘提供了从字母到数字的映射，映射关系如下：
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

输入的格式是，第一行是一个正整数，指定电话号码薄中号码的数量。余下的每行是一个电话号码。每个电话号码由数字，大写字母（除了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
/////////////////////////////////////////////////////////////////////////////
我的代码：
[code=c]
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int main(void)
{
    long i,j=0,l=0,n,num;
char c[100]={0},vstr[10];
int *a=(int *)malloc(sizeof(int)*10000000);
memset(a,0,sizeof(int)*10000000);
for (i='0';i<='Z';i++)
switch (i)
{
case 'A':
case 'B':
case 'C':
  c[i]=2;
  break;
case 'D':
case 'E':
case 'F':
  c[i]=3;
  break;
case 'G':
case 'H':
case 'I':
  c[i]=4;
  break;
case 'J':
case 'K':
case 'L':
  c[i]=5;
  break;
case 'M':
case 'N':
case 'O':
  c[i]=6;
  break;
case 'P':
case 'Q':
case 'R':
case 'S':
  c[i]=7;
  break;
case 'T':
case 'U':
case 'V':
  c[i]=8;
  break;
case 'W':
case 'X':
case 'Y':
case 'Z':
  c[i]=9;
  break;
default:
  if(i>='0'&&i<='9')
  c[i]=i-'0';
  break;
}
scanf("%d",&num);
    while(num--)
{
  n=0;
  memset(vstr,0,sizeof(char)*10);
  scanf("%s",vstr);
     for(i=0;vstr[i]!=0;i++)
  {
    if(vstr[i]!='Q'&&(vstr[i]>='0'&&vstr[i]<='9'||vstr[i]>='A'&&vstr[i]<'Z'))
    {
     n=n*10+c[vstr[i]];
    }
  }
  a[n]++;
}
for (i=1000000;i<=9999999;i++)
{
  if (a[i]>1)
  {
      l=i/10000;
   n=i%10000;
      printf("%ld-%ld %d\n",l,n,a[i]);
  }
}
if (l==0)
{
  printf("No duplicates.\n");
}
return 0;
}
[/code]

最后更新于：2010-12-03 15:14:00

本帖地址： http://bbs.pfan.cn/post/357422.html

回复列表（共4个回复）

沙发

bruceteen [专家分：42660] 发布于 2010-12-03 13:12:00

随便写的，用gcc编译测试通过

[code=c]
#include <stdio.h>
#include <malloc.h>
#include <search.h>
#include <stdbool.h>

int main( void )
{
    // 读入行数
    unsigned long n = 0;
    if( scanf("%lu",&n) != 1 )
        return -1;
    scanf("%*c");

    unsigned long* buf = malloc( n*sizeof(unsigned long) );
    for( unsigned long i=0; i!=n; ++i )
    {
        // 读入一行
        char line[16];
        if( scanf("%15[^\n]%*c",line) != 1 )
            return -1;

        // 转化为数字
        unsigned long num = 0;
        unsigned long cn = 0;
        for( char* p=line; *p!='\0'; ++p, ++cn )
        {
            char c = *p;
            if( c == '-' )
            {
                --cn;
                continue;
            }

            if( c>='0' && c<='9' )
                num = num*10 + (c-'0');
            else if( c>='A' && c<='Y' )
                num = num*10 + (c-(c>='Q')-'A')/3+2;
            else
                return -1;
        }
        if( cn != 7 )
            return -1;
        buf[i] = num;
    }

    // 将号码排序
    int __cdecl int_compare( const void*, const void* );
    qsort( buf, n, sizeof(buf[0]), &int_compare );

    printf( "\n" );
    // 搜寻重复号
    bool bfind = false;
    unsigned long num=buf[0], count=1;
    for( unsigned long i=1; i!=n; ++i )
    {
        if( buf[i] == num )
        {
            ++count;
            continue;
        }

        if( count != 1 )
        {
            bfind = true;
            printf( "%03lu-%04lu %lu\n", num/10000, num%10000, count );
        }

        num=buf[i], count=1;
    }
    if( !bfind )
        printf( "%s\n", "No duplicates." );

    return 0;
}

int __cdecl int_compare(const void* a, const void* b )
{
    return *(long*)a - *(long*)b;
}
[/code]

板凳

bruceteen [专家分：42660] 发布于 2010-12-03 13:13:00

靠，忘了free

3 楼

x66f [专家分：10] 发布于 2010-12-03 15:04:00

您随便写的一个效率就很高，很是佩服，但是我想知道的是我的程序问题出在了哪。我的程序在我的电脑上能正确运行（vc6.0和gcc都通过），140万的数据量用时1.78s，内存39M，我牺牲了内存以求的速度，不知为何程序往北大测试平台提交的时候总是wrong answer，还望指正

4 楼

windy0will [专家分：2300] 发布于 2010-12-05 16:06:00

int *a=(int *)malloc(sizeof(int)*10000000);
memset(a,0,sizeof(int)*10000000);
等等和10000000有关的部分都是楼主的代码中比较费时间的。还有，您的代码我编译的时候出现的警告太多，没具体去看代码。
bruceteen大神的代码实在太漂亮了。无论是可读性还是效率。
我也写了一段代码(可能效率要比bruceteen的逊色很多)，把字符串转换为整数是用的查表法；存储数据用的是小根堆的结构。对于输入的数据必须是正确的，否则结果无法预料。下面的代码只能用gcc才能编译。
[code=c]
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

/*
          n = n*10 + b
*/
#define _mul10_add(n,b) ((n) = ((n)<<1) + ((n)<<3) +(b))

/*
         qoutient  = n / m;
         remainder = n % m;
*/
#define _div(n,m,qoutient,remainder) \
    __asm__("divl %4 ":"=a"(qoutient),"=d"(remainder) :"0"(n), "1"(0), "r"(m) )

/*
        获取字符串中的1个数字字符
*/
#define _get_digit(s) ({for(;table[(int)(*s)]<0;++s);  table[(int)(*s++)];})

int  pop_from_heap  (int *);
void push_into_heap (int *, int);

int main (void)
{
  /* 电话拨号盘提供了从字母到数字的映射,映射关系如下： */
  const int table[] = {
    -3, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2,/*  0 ~ 15 */
    -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2,/* 16 ~ 31 */
    -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -1, -2, -2,/* 32 ~ 47 */
     0,  1,  2,  3,  4,  5,  6,  7,  8,  9, -2, -2, -2, -2, -2, -2,/* 48 ~ 63 */
    -2,  2,  2,  2,  3,  3,  3,  4,  4,  4,  5,  5,  5,  6,  6,  6,/* 64 ~ 79 */
     7, -2,  7,  7,  8,  8,  8,  9,  9,  9, -2, -2, -2, -2, -2, -2,/* 80 ~ 95 */
    -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2,/* 96 ~111 */
    -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2,/* 112~127 */
  };
  int n, i;
  int *heap; /*  小根堆 */
  register int n0;

  char line[16], *s;/* line用于获取一行数据，把字符串line转换成整数时,s用来遍历line的各个字符 */

  scanf ("%d",&n);    gets (line);
  if (n < 1)
    return -1;

  /*
  最初的堆一共有0个数据，heap[0] 表示堆中数据的个数，因此要多为它申请一个空间单元
  */
  if ((heap = malloc(sizeof(int) *(n+1))) == NULL)
    return -1;

  heap[0] = 0;


  /*
  输入数据，并分别把数据压入小根堆中，为了简便输入数据，把输入流和文件in关联
  同样，把输出的数据输出到out文件当中去
  */
  i = 0;
  freopen ("in", "r", stdin);
  freopen ("out", "w", stdout);
  while(++i <= n)
    {
    gets (line);
    s = line;
    n0 = _get_digit (s);

    /*
    下面是把循环展开了，由于电话号码只有7个数字，故考虑直接展开
    */
    _mul10_add(n0, _get_digit(s));   _mul10_add(n0, _get_digit(s));
    _mul10_add(n0, _get_digit(s));   _mul10_add(n0, _get_digit(s));
    _mul10_add(n0, _get_digit(s));   _mul10_add(n0, _get_digit(s));

    /*  把数据 n0 压入小根堆heap中  */
    push_into_heap (heap, n0);
    }


  /*
  下面是输出部分
  */
  {
  register int count = 0;
  int bfind=0, n1, n2;
  n0 = 0;

  do {
     n1 = pop_from_heap (heap);

     if (n0 == n1)
       ++count;

     else {
       if (count > 1){
           bfind=1；
           _div (n0, 10000, n0, n2);
           printf ("\n%03d-%04d %d", n0, n2, count);
       }
       count=1;  n0=n1;
     }

   } while (--n > 0);


  if (bfind == 0) printf("\nNo duplicates.");
  }

  free (heap);  heap = NULL;

  puts("\n----exit----");
  return 0;
}

/*  把数据num压入小根堆heap中  */
void
push_into_heap (int *heap, int num)
{
  register int i = ++heap[0];
  /*
  这里是小根堆的插入操作，我只是选折一种比较简单的方法实现小根堆的插入
  不过，可以用折半查找法来提高效率，可以把时间复杂度变成为 O(log log n)。
  */
  while (i > 1)
    {
    if (num > heap[i>>1]) break;

    heap[i] = heap[i>>1];
    i >>= 1;
    }

  heap[i] = num;
}

/* 从小根堆中弹出最小的数据，并返回这个最小的数据 */
int
pop_from_heap (int *heap)
{
  int ret = heap[1];/* 返回小根堆中最小的数据 */
  int n = heap[0]--;
  register int parent=1, child=2;
  register int temp = heap[n];

  /*
  这里是小根堆的删除操作
  */
  while(child <= n)
    {
    if (heap[child + 1] < heap[child]  &&   child < n)
      ++child;

    if (temp <= heap[child])
      break;

    heap[parent] = heap[child];
    parent = child;
    child <<= 1;
    }

  heap[parent] = temp;

  return ret;
}

[/code]

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：[原创]希望路过的大牛们指出错误

回复列表（共4个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：[原创]希望路过的大牛们指出错误

回复列表 （共4个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共4个回复）