May the force be with you!
posts - 52,  comments - 33,  trackbacks - 0
    下午HDU的比赛,做得不好。一是有一个题目题意没读清楚,还有就是犯了两个错误,在1006卡死了。

    题目地址:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1006&cid=103

    题意比较简单,然后我想到一个对每个frosh的课程排序,然后对所有的排序,再计算。

    开始写了个得到TLE,我觉得不太可能有更好的算法,然后重写,还是TLE,无奈我把数字转换成字符串,一直WA。

    结果我就卡在这个题目上两个多小时,直到最后也没做出来。

    刚刚终于找到了错误:

第一个程序TLE是因为数组范围开小了,结果没有RE,只是TLE,诡异呀~~

第二个程序是排序用的qsort,然后比较函数开始照着字符串数组排序打的,然而字符串在结构体里面,居然可以比较而且跟我想的一样,在我的机器上没问题,交上去就WA了。


下面是两个方法AC后的程序(用注释标记了错误的地方):

  1 # include <iostream>
  2 using namespace std;
  3 
  4 //开始一直TLE,都是因为N的范围小了——开始定为5555
  5 # define N 10010
  6 
  7 typedef struct node {
  8     int no[5];
  9 };
 10 
 11 node man[ N ];
 12 int n;
 13 
 14 int cmp1( const void *a, const void *b)
 15 {
 16     return (*(int *)a - *(int *)b);
 17 }
 18 
 19 void init()
 20 {
 21     for ( int i = 0; i < n; i ++ )
 22     {
 23         for ( int  j = 0; j < 5; j ++ )
 24         {
 25             scanf( "%d"&man[i].no[j] );
 26 
 27         }
 28         qsort(man[i].no, 5, sizeof(man[i].no[0]), cmp1);
 29 //        cout << man[i].no[0] << endl; ///
 30     }
 31 }
 32 
 33 int cmp2( const void *a, const void *b )
 34 {
 35     node *aa = (node *)a;
 36     node *bb = (node *)b;
 37     if ( aa->no[0!= bb->no[0] )
 38     {
 39         return aa->no[0> bb->no[0? 1-1;
 40     }
 41     if ( aa->no[1!= bb->no[1] )
 42     {
 43         return aa->no[1> bb->no[1? 1-1;
 44     }
 45     if ( aa->no[2!= bb->no[2] )
 46     {
 47         return aa->no[2> bb->no[2? 1-1;
 48     }
 49     if ( aa->no[3!= bb->no[3] )
 50     {
 51         return aa->no[3> bb->no[3? 1-1;
 52     }
 53     return aa->no[4- bb->no[4];
 54 }
 55 
 56 inline bool is_same( int a, int b )
 57 {
 58     for ( int i = 0; i < 5; i ++ )
 59     {
 60         if (man[a].no[i] != man[b].no[i]) return false;
 61     }
 62     return true;
 63 }
 64 
 65 void solve()
 66 {
 67     qsort(man, n, sizeof(man[0]), cmp2);
 68     int ans = 1, max = 1;
 69     int tmp = 1, t = 1;
 70     bool flag;
 71     for (int i = 1; i < n; i ++ )
 72     {
 73         if ( is_same(i, i-1) ) tmp++;
 74         else
 75         {
 76         //    cout << tmp << endl; ///
 77             if (tmp > max)
 78             {
 79                 max = tmp;
 80                 t = tmp;
 81                 ans = max; //
 82             }
 83             else if (tmp == max)
 84             {
 85                 t += tmp;
 86                 if ( t > ans ) ans = t;
 87             }
 88             tmp = 1;
 89         }
 90     }
 91     if ( n > 1 && is_same(n-1, n-2) )
 92     {
 93         if (tmp > max)
 94         {
 95             max = tmp;
 96             ans = max; //
 97         }
 98         else if (tmp == max)
 99         {
100             t += tmp;
101             if ( t > ans ) ans = t;
102         }
103     }
104     printf("%d\n", ans);
105 }
106 
107 int main()
108 {
109     while ( true )
110     {
111         scanf("%d"&n);
112         if ( n == 0 ) break;
113         init();
114         solve();
115     }
116     return 0;
117 }
118 

代码二:
  1 # include <iostream>
  2 using namespace std;
  3 
  4 # define N 10010
  5 
  6 typedef struct node {
  7     int no[5];
  8     char s[16];
  9 };
 10 
 11 node man[ N ];
 12 int n;
 13 
 14 int cmp1( const void *a, const void *b)
 15 {
 16     return (*(int *)a - *(int *)b);
 17 }
 18 
 19 void to_string(int a)
 20 {
 21     man[a].s[0= man[a].no[0]/100 + '0';
 22     man[a].s[1= man[a].no[0]%100/10 + '0';
 23     man[a].s[2= man[a].no[0]%10 + '0';
 24     
 25     man[a].s[3= man[a].no[1]/100 + '0';
 26     man[a].s[4= man[a].no[1]%100/10 + '0';
 27     man[a].s[5= man[a].no[1]%10 + '0';
 28     
 29     man[a].s[6= man[a].no[2]/100 + '0';
 30     man[a].s[7= man[a].no[2]%100/10 + '0';
 31     man[a].s[8= man[a].no[2]%10 + '0';
 32     
 33     man[a].s[9= man[a].no[3]/100 + '0';
 34     man[a].s[10= man[a].no[3]%100/10 + '0';
 35     man[a].s[11= man[a].no[3]%10 + '0';
 36     
 37     man[a].s[12= man[a].no[4]/100 + '0';
 38     man[a].s[13= man[a].no[4]%100/10 + '0';
 39     man[a].s[14= man[a].no[4]%10 + '0';
 40     
 41     man[a].s[15= '\0';
 42 }
 43 
 44 void init()
 45 {
 46     for ( int i = 0; i < n; i ++ )
 47     {
 48         scanf( "%d%d%d%d%d"&man[i].no[0], &man[i].no[1],&man[i].no[2], &man[i].no[3], &man[i].no[4]);
 49         qsort(man[i].no, 5, sizeof(man[i].no[0]), cmp1);
 50         to_string(i);
 51     //    cout << man[i].s << endl; ////
 52     }
 53 }
 54 /*
 55 int cmp2(const void *a,const void *b)
 56 {
 57     return(strcmp((char*)a,(char*)b));
 58 }
 59 */
 60 int cmp2(const void *a,const void *b) //一直WA都是因为这个函数写错了,见上
 61 {
 62     node *aa = (node *)a;
 63     node *bb = (node *)b;
 64     return(strcmp(aa->s,bb->s));
 65 }
 66 
 67 void solve()
 68 {
 69     qsort(man, n, sizeof(man[0]), cmp2); ///
 70 
 71     int ans = 1, max = 1;
 72     int tmp = 1, t = 1;
 73     bool flag;
 74     for (int i = 1; i < n; i ++ )
 75     {
 76         if ( strcmp( man[i].s, man[i-1].s ) == 0 ) tmp++;
 77         else
 78         {
 79             if (tmp > max)
 80             {
 81                 max = tmp;
 82                 t = tmp;
 83                 ans = max; //
 84             }
 85             else if (tmp == max)
 86             {
 87                 t += tmp;
 88                 if ( t > ans ) ans = t;
 89             }
 90             tmp = 1;
 91         }
 92     }
 93     if ( n > 1 && strcmp( man[n-1].s, man[n-2].s ) == 0 )
 94     {
 95         if (tmp > max)
 96         {
 97             max = tmp;
 98             ans = max; //
 99         }
100         else if (tmp == max)
101         {
102             t += tmp;
103             if ( t > ans ) ans = t;
104         }
105     }
106             
107     printf("%d\n", ans);
108 }
109 
110 int main()
111 {
112     while ( true )
113     {
114         scanf("%d"&n);
115         if ( n == 0 ) break;
116         init();
117         solve();
118     }
119     return 0;
120 }
121 


posted on 2008-01-24 19:14 R2 阅读(1058) 评论(0)  编辑 收藏 引用 所属分类: Memo

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


你是第 free hit counter 位访客




<2008年1月>
303112345
6789101112
13141516171819
20212223242526
272829303112
3456789

常用链接

留言簿(4)

随笔分类(54)

随笔档案(52)

文章档案(1)

ACM/ICPC

技术综合

最新随笔

搜索

  •  

积分与排名

  • 积分 - 61526
  • 排名 - 357

最新评论

阅读排行榜

评论排行榜