Codeforces 336C

这题是大一暑假时候做的，当时没有出，直到今天突然觉得应该把没过的题目再做一边，不然真的是越积越多。

现在能够独立做出来真的是难以表达的兴奋，刚开始的时候就觉得 O（30 * 30 * n）的复杂度有点不安全，不过还是敲了，事实说明实际的负责度没这么高。和去年一样，没有思路，后来仔细一想，真的是数学题。现在感觉爱上了Math...

附上代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 // 保存原始数组
 5 int b[100005];
 6 // a[i][j]表示b[i]的二进制表示法中的各个位上的数值， 而able数组保存的是每一轮中可以选的标记
 7 bool a[100005][32], able[100005];
 8 int n;
 9 
10 int main(void) {
11     while (~scanf("%d", &n) && n) {
12         memset(a, false, sizeof(a));
13         for (int i = 0; i < n; i++) {
14             int x;
15             scanf("%d", &x);
16             b[i] = x;
17             for (int j = 30; j >= 0; j--) {
18                 if ((1 << j) & x)
19                     a[i][30-j] = true;
20             }
21         }
22 
23         int cnt;
24         for (int i = 0; i <= 30; i++) {
25             cnt = 0;
26             memset(able, false, sizeof(able));
27             for (int j = 0; j < n; j++) {
28                 if ( a[j][i] ) {
29                     able[j] = true;
30                     cnt++;
31                 }
32             }
33             if (cnt == 0) continue;
34 
35             int j;
36             for (j = i + 1; j <= 30; j++) {
37                 int f = 0;
38                 for (int k = 0; k < n; k++) {
39                     if ( able[k] ) {
40                         if ( !a[k][j] ) {
41                             f = 1;
42                             break;
43                         }
44                     }
45                 }
46                 if (f == 0)
47                     break;
48             }
49             if (j > 30)
50                 break;
51         }
52         printf("%d
", cnt);
53         int flag = 0;
54         for (int i = 0; i < n; i++) {
55             if ( able[i] ) {
56                 if (flag) 
57                     printf(" ");
58                 flag = 1;
59                 printf("%d", b[i]);
60             }
61         }
62         puts("");
63     }
64 
65     return 0;
66 }