[2018百度之星] 资格赛1001 调查问卷 (状压枚举, 计数)

发表于 | 更新于 | 分类于 ， ， | 评论数： | 阅读次数：

链接：http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=820&pid=1001

没啥好解释的，中文题意。

因为题目最多10道，因此枚举所有题目的组合，然后把每一份问卷的对应答案存出来，对每一类单独统计数目。之后每一类中的问卷答案数$k$与其他问卷答案成的对数为$p×(n-p)$，累加所有问卷答案对数再除以2，跟目标k比较一下就ok。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1010;
int n, m, k;
char s[maxn][11];
int cur[maxn][11];
int f[maxn];
unordered_map<int, int> vis;

signed main() {
  // freopen("in", "r", stdin);
  int T, _ = 0;
  scanf("%d", &T);
  while(T--) {
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 0; i < n; i++) {
      scanf("%s", s[i]);
    }
    int ret = 0;
    int mm = 1 << m;
    for(int i = 1; i < mm; i++) {
      int qq = 0;
      for(int j = 0; j < m; j++) {
        if(i & (1 << j)) {
          for(int l = 0; l < n; l++) {
            cur[l][qq] = s[l][j] - 'A' + 1;
          }
          qq++;
        }
      }
      for(int j = 0; j < n; j++) f[j] = 0;
      for(int j = 0; j < n; j++) {
        for(int l = 0; l < qq; l++) {
          f[j] <<= 1;
          f[j] |= (cur[j][l] == 1 ? 1 : 0);
        }
      }
      vis.clear();
      for(int j = 0; j < n; j++) vis[f[j]]++;
      int tot = n, tmp = 0;
      for(auto p : vis) {
        tmp += (n - p.second) * p.second;
      }
      if(tmp / 2 >= k) ret++;
    }
    printf("Case #%d: %d\n", ++_, ret);
  }
  return 0;
}