『acm』程序错再哪？我测试了下输入10w个要3分钟的样子，怎么不给个timelimit(页 1) - 『数据结构与算法』

okayyyy 发表于 2010-8-20 11:18

『acm』程序错再哪？我测试了下输入10w个要3分钟的样子，怎么不给个timelimit

[code][color=#008000]//[/color][color=#008000]---------------------------------------------------------------------------------------------------------
[/color][color=#008000]//[/color][color=#008000]解题步骤：
[/color][color=#008000]//[/color][color=#008000] 1，每输入一个合法的字符串，就转换成标准格式
[/color][color=#008000]//[/color][color=#008000] 2，把格式后的字符串，插入链表
[/color][color=#008000]//[/color][color=#008000]insert函数工作步骤：
[/color][color=#008000]//[/color][color=#008000] 1，判断是否为第一次插入，是则直接插入
[/color][color=#008000]//[/color][color=#008000] 2，维护一个递增链表。
[/color][color=#008000]//[/color][color=#008000] 3，遍历链表，比较t与结点数据域的大小，来决定互换
[/color][color=#008000]//[/color][color=#008000] 4，遍历结束，把最大的元素保存到t，在插入表尾
[/color][color=#008000]//[/color][color=#008000]---------------------------------------------------------------------------------------------------------[/color][color=#008000]
[/color]

[color=#0000FF]#include[/color] [color=#800000]"[/color][color=#800000]stdio.h[/color][color=#800000]"[/color]
[color=#0000FF]#include[/color] [color=#800000]"[/color][color=#800000]string.h[/color][color=#800000]"[/color]
[color=#0000FF]#include[/color] [color=#800000]"[/color][color=#800000]stdlib.h[/color][color=#800000]"[/color]
[color=#0000FF]#include[/color] [color=#800000]<time.h>[/color]  [color=#008000]//[/color][color=#008000]测试程序而添加的头 [/color][color=#008000]
[/color][color=#0000FF]typedef[/color] [color=#0000FF]struct[/color] lnode
{
[color=#0000FF]char[/color] data[[color=#800080]9[/color]];
[color=#0000FF]int[/color] counter;
[color=#0000FF]struct[/color] lnode *next;
}lnode,*linklist;

[color=#0000FF]void[/color] changetostande([color=#0000FF]char[/color]*,[color=#0000FF]char[/color]*);
[color=#0000FF]int[/color] insert(linklist,[color=#0000FF]char[/color]* );
[color=#0000FF]int[/color] main()
{
linklist lodeptr,p;
lnode codelode;
[color=#0000FF]long[/color] i;
[color=#0000FF]int[/color] j;
[color=#0000FF]char[/color] t[[color=#800080]9[/color]],s[[color=#800080]256[/color]];

codelode.next=[color=#800080]0[/color];
p=lodeptr=&codelode;

scanf([color=#800000]"[/color][color=#800000]%d[/color][color=#800000]"[/color],&i);
[color=#0000FF]if[/color] (i>[color=#800080]100000[/color]) [color=#0000FF]return[/color] [color=#800080]0[/color];
[color=#0000FF]while[/color] (i--)
{ [color=#0000FF]int[/color] j=[color=#800080]0[/color];
      [color=#0000FF]while[/color] (j<[color=#800080]8[/color])
      {
         s[j++]= ([color=#0000FF]char[/color])((rand()%[color=#800080]10[/color])+[color=#800080]48[/color]);[color=#808080]///[/color][color=#008000]/测试程序而添加的[/color][color=#808080]
[/color]       }

      changetostande(s,t);[color=#008000]//[/color][color=#008000]转换成标准格式 ***-****
      [/color][color=#008000]//[/color][color=#008000]printf("%s\n",t);          [/color][color=#008000]
[/color]       j=insert(lodeptr,t);[color=#008000]//[/color][color=#008000]在插入链表[/color][color=#008000]
[/color] }
[color=#0000FF]if[/color] (!j)
{
      printf([color=#800000]"[/color][color=#800000]%s\n[/color][color=#800000]"[/color],[color=#800000]"[/color][color=#800000]No duplicates.[/color][color=#800000]"[/color]);
}
[color=#0000FF]while[/color] (p->next)
{
      p=p->next;
      printf([color=#800000]"[/color][color=#800000]%s %d\n[/color][color=#800000]"[/color],p->data,p->counter);
}

[color=#0000FF]return[/color] [color=#800080]0[/color];
}

[color=#0000FF]int[/color] insert(linklist lodeptr,[color=#0000FF]char[/color] *t)
{
linklist p,q,r;
[color=#0000FF]int[/color] i=[color=#800080]0[/color];
[color=#0000FF]static[/color] [color=#0000FF]int[/color] n=[color=#800080]0[/color] ,j=[color=#800080]0[/color];
[color=#0000FF]char[/color] max1[[color=#800080]9[/color]];
p=lodeptr->next;

[color=#0000FF]if[/color] (!n)[color=#008000]//[/color][color=#008000]第一次时，直接插入[/color][color=#008000]
[/color] {
      n=[color=#800080]1[/color];
      q=malloc([color=#0000FF]sizeof[/color](lnode));
      q->next=lodeptr->next;
      q->counter=[color=#800080]0[/color];
      strcpy(q->data,t);
      lodeptr->next=q;
      [color=#0000FF]return[/color] [color=#800080]0[/color];
}
[color=#0000FF]else[/color]
      [color=#0000FF]while[/color] (p)[color=#008000]//[/color][color=#008000]否则遍历链表[/color][color=#008000]
[/color]       {
         i=strcmp(t,p->data);
         [color=#0000FF]if[/color] (i==[color=#800080]0[/color])
         {
            p->counter++;

            [color=#0000FF]return[/color] j=[color=#800080]1[/color];
         }
         [color=#0000FF]else[/color] [color=#0000FF]if[/color](i==[color=#800080]1[/color])
         {
            r=p;
            p=p->next;
         }
         [color=#0000FF]else[/color]
         {
            strcpy(max1,p->data);
            strcpy(p->data,t);
            strcpy(t,max1);
            r=p;
            p=p->next;
         }
      }[color=#008000]//[/color][color=#008000]while 维护一个递增链表把最大的换出来[/color][color=#008000]
[/color]
      q=malloc([color=#0000FF]sizeof[/color](lnode));
      strcpy(q->data,t);
      q->counter=[color=#800080]0[/color];
      q->next=r->next;
      r->next=q;[color=#008000]//[/color][color=#008000]再插到表尾[/color][color=#008000]
[/color]
      [color=#0000FF]return[/color] j;

}
[color=#0000FF]void[/color] changetostande([color=#0000FF]char[/color]* s,[color=#0000FF]char[/color]* t)
{[color=#008000]//[/color][color=#008000]这玩意就没改了，本来想换个比较"0000 1111 2ABC 3DEF 4GHI 5JKL 6NMO 7PRS 8TUV 9WXY",实现功能的。 [/color][color=#008000]
[/color]
[color=#0000FF]int[/color] n=[color=#800080]0[/color];
[color=#0000FF]while[/color] (*s && n<[color=#800080]8[/color])
{
      [color=#0000FF]if[/color] (n==[color=#800080]3[/color])
      {
         *(t++)=[color=#800000]'[/color][color=#800000]-[/color][color=#800000]'[/color];
         n++;
         *(s--);
      }

      [color=#0000FF]else[/color]
      {
      [color=#0000FF]switch[/color] (*s)
         {
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]A[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]B[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]C[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]2[/color][color=#800000]'[/color]: ++n;
         *(t++)=[color=#800000]'[/color][color=#800000]2[/color][color=#800000]'[/color];

         [color=#0000FF]break[/color];
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]D[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]E[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]F[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]3[/color][color=#800000]'[/color]: ++n;
         *(t++)=[color=#800000]'[/color][color=#800000]3[/color][color=#800000]'[/color];

         [color=#0000FF]break[/color];
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]G[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]H[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]I[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]4[/color][color=#800000]'[/color]: ++n;
         *(t++)=[color=#800000]'[/color][color=#800000]4[/color][color=#800000]'[/color];

         [color=#0000FF]break[/color];
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]J[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]K[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]L[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]5[/color][color=#800000]'[/color]: ++n;
         *(t++)=[color=#800000]'[/color][color=#800000]5[/color][color=#800000]'[/color];

         [color=#0000FF]break[/color];
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]N[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]M[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]O[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]6[/color][color=#800000]'[/color]: ++n;
         *(t++)=[color=#800000]'[/color][color=#800000]6[/color][color=#800000]'[/color];

         [color=#0000FF]break[/color];
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]P[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]R[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]S[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]7[/color][color=#800000]'[/color]: ++n;
         *(t++)=[color=#800000]'[/color][color=#800000]7[/color][color=#800000]'[/color];

         [color=#0000FF]break[/color];
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]T[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]U[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]V[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]8[/color][color=#800000]'[/color]: ++n;
         *(t++)=[color=#800000]'[/color][color=#800000]8[/color][color=#800000]'[/color];

         [color=#0000FF]break[/color];
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]W[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]X[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]Y[/color][color=#800000]'[/color]:
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]9[/color][color=#800000]'[/color]: ++n;
         *(t++)=[color=#800000]'[/color][color=#800000]9[/color][color=#800000]'[/color];

         [color=#0000FF]break[/color];
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]0[/color][color=#800000]'[/color]: ++n;
         *(t++)=[color=#800000]'[/color][color=#800000]0[/color][color=#800000]'[/color];

         [color=#0000FF]break[/color];
      [color=#0000FF]case[/color] [color=#800000]'[/color][color=#800000]1[/color][color=#800000]'[/color]: ++n;
         *(t++)=[color=#800000]'[/color][color=#800000]1[/color][color=#800000]'[/color];

         [color=#0000FF]break[/color];
      [color=#0000FF]default[/color]:
         [color=#0000FF]break[/color];

         }[color=#008000]//[/color][color=#008000]switch[/color][color=#008000]
[/color]       }[color=#008000]//[/color][color=#008000]if[/color][color=#008000]
[/color]       *(s++);
}[color=#008000]//[/color][color=#008000]while[/color][color=#008000]
[/color]
*t=[color=#800080]0[/color];
}

[/code]第一次测试，就这么悲惨。。[em09]

acman 发表于 2010-8-21 11:34

你做那个上面的题啊就是以后请教你了啊

页: [1]

『acm』 程序错再哪？我测试了下输入10w个 要3分钟的样子，怎么不给个timelimit

『acm』程序错再哪？我测试了下输入10w个要3分钟的样子，怎么不给个timelimit