我希望你是我独家记忆

一段永远封存的记忆,随风而去
posts - 263, comments - 31, trackbacks - 0, articles - 3
   :: 首页 :: 新随笔 ::  :: 聚合  :: 管理

PKU——3274——排序

Posted on 2008-08-30 16:08 Hero 阅读(408) 评论(0)  编辑 收藏 引用 所属分类: 代码如诗--ACM
  1 //PKU 3274    Accepted    25688K    938MS    C++    2523B
  2 
  3 //输入一个数--转化为二进制形式保存在bits[]中
  4 //dp[i][j]用于累加前i行前j列的值
  5 
  6 //两列的差值相等转化为两行的递增相等********
  7 
  8 //对递增排序--qsort()
  9 //遍历一遍求出最大maxlen
 10 
 11 //注意问题 : 遍历的时候不要忘了最后一行单独判断
 12 
 13 #include <stdio.h>
 14 #include <stdlib.h>
 15 #include <string.h>
 16 #include <math.h>
 17 
 18 const int size = 100100 ;
 19 
 20 int data[size] ;
 21 int dp[size][32= {0} ;
 22 
 23 struct NODE
 24 {
 25     int sub[32] ;
 26     int num ;
 27 };
 28 struct NODE node[size] ;
 29 
 30 int bits[40] ;
 31 int inn, ink ;
 32 
 33 
 34 void dec2bin( int val, int ti )
 35 {
 36     int i = 0 ;
 37     for( ; val>0; val=val>>1 )
 38     {
 39         bits[i++= val & 1 ;
 40     }
 41 
 42     for( ; i<ink; i++ ) bits[i] = 0 ;
 43 
 44     forint j=0; j<ink; j++ )
 45     {
 46         dp[ti][j] = dp[ti-1][j] + bits[j] ;
 47     }
 48 }
 49 
 50 void input() 
 51 {
 52     memset( dp, 0sizeof(dp) ) ;
 53 
 54     int val ;
 55     forint i=1; i<=inn; i++ ) 
 56     {
 57         scanf( "%d"&val ) ;
 58         dec2bin( val, i ) ;
 59     }
 60 }
 61 
 62 bool equal( int sn, int en )
 63 {
 64     int maxi = ink - 1 ;
 65     forint i=0; i<maxi; i++ )
 66     {
 67         if( node[sn].sub[i] != node[en].sub[i] ) return false ;
 68     }
 69 
 70     return true ;
 71 }
 72 
 73 int cmp( const void *a, const void *b )
 74 {
 75     struct NODE *= (struct NODE *)a ;
 76     struct NODE *= (struct NODE *)b ;
 77 
 78     int maxi = ink - 1 ;
 79     forint i=0; i<maxi; i++ )
 80     {
 81         if( c->sub[i] != d->sub[i] ) return c->sub[i] - d->sub[i] ;
 82     }
 83     return c->num - d->num ; 
 84 }
 85 
 86 void process()
 87 {
 88 
 89     node[0].num = 0 ;
 90     forint i=0; i<=ink; i++ ) node[0].sub[i] = 0 ;
 91 
 92     forint i=1; i<=inn; i++ )
 93     {
 94         node[i].num = i ;
 95         forint j=0; j<ink-1; j++ )
 96         {
 97             node[i].sub[j] = dp[i][j+1- dp[i][0] ;
 98         }
 99     }
100 
101     qsort( node, inn+1sizeof(node[1]), cmp ) ;
102 
103     int sn = 0 ; int maxlen = -1 ; int len ;
104 
105     forint i=1; i<=inn; i++ )
106     {
107         if( equal( i, sn) ) continue ;
108         else
109         {
110             len = node[i-1].num - node[sn].num ;
111             if( len > maxlen )    maxlen = len ;
112             sn = i ;
113         }
114     }
115 
116     if( equal( inn, sn ) )
117     {//最后一行单独判断
118         len = node[inn].num - node[sn].num ;
119         if( len > maxlen ) maxlen = len ;
120     }
121 
122     printf( "%d\n", maxlen ) ;
123 }
124 
125 int main()
126 {
127     freopen( "in.txt""r", stdin ) ;
128 
129     while( scanf( "%d %d"&inn, &ink ) != EOF )
130     {
131         input() ;
132 
133         process() ;
134 
135         //output() ;
136     }
137 
138     return 0 ;
139 }

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