Posted on 2008-08-30 16:08
Hero 閱讀(421)
評論(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 for( int 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, 0, sizeof(dp) ) ;
53
54 int val ;
55 for( int 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 for( int 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 *c = (struct NODE *)a ;
76 struct NODE *d = (struct NODE *)b ;
77
78 int maxi = ink - 1 ;
79 for( int 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 for( int i=0; i<=ink; i++ ) node[0].sub[i] = 0 ;
91
92 for( int i=1; i<=inn; i++ )
93 {
94 node[i].num = i ;
95 for( int 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+1, sizeof(node[1]), cmp ) ;
102
103 int sn = 0 ; int maxlen = -1 ; int len ;
104
105 for( int 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 }