POJ 2436 二进制枚举+位运算

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <cstdio>
 5 using namespace std;
 6 #define maxn 1005
 7 int n, d, k;
 8 int cow[maxn];
 9 
10 int ok(int a)
11 {
12     int ret = 0;
13     while (a)
14     {
15         ret += (a & 1);
16         a >>= 1;
17     }
18     return ret == k;///如果a转换成二进制有k个1,返回k,否则返回0
19 }
20 
21 int main()
22 {
23     scanf("%d%d%d", &n, &d, &k);
24     for (int i = 0; i < n; i++)
25     {
26         int a, b;
27         scanf("%d", &a);
28         for (int j = 0; j < a; j++)
29         {
30             scanf("%d", &b);
31             cow[i] |= (1 << (b - 1));
32             cout<<cow[i]<<endl;
33             ///cow[i]表示牛得病的2进制表示，然后转换为十进制
34             ///如果1 2的话，就是010（cow[i] = 2），第二个位置是1
35             ///如果2 1 2的话，就是011（cow[i] = 3），第一二个位置是1
36         }
37     }
38     int s = (1 << k) - 1;
39     int e = s << (d - k);///即s*(2^(d-k))
40     int ans = 0;
41     for (int i = s; i <= e; i++)
42     {
43         if (ok(i))///如果该牛有k种病，进下一关
44         {
45             int temp = 0;
46             for (int j = 0; j < n; j++)///枚举每头牛，符合的加1
47             {
48                 ///不明白if
49                 if ((i & cow[j]) == cow[j])///都转化为2进制，按位与，二进制数只要小于i就满足
50                     temp++;
51             }
52             ans = max(ans, temp);
53         }
54     }
55     printf("%d\n", ans);
56     return 0;
57 }