调查问卷

传送门 HDU 6344

描述

度度熊为了完成毕业论文,需要收集一些数据来支撑他的论据,于是设计了一份包含 m 个问题的调查问卷,每个问题只有 ‘A’ 和 ‘B’ 两种选项。
将问卷散发出去之后,度度熊收到了 n 份互不相同的问卷,在整理结果的时候,他发现可以只保留其中的一部分问题,使得这 n 份问卷仍然是互不相同的。这里认为两张问卷是不同的,当且仅当存在至少一个被保留的问题在这两份问卷中的回答不同。
现在度度熊想知道,存在多少个问题集合,使得这 n 份问卷在只保留这个集合的问题之后至少有 k 对问卷是不同的。

输入

第一行包含一个整数 T,表示有 T 组测试数据。
接下来依次描述 T 组测试数据。对于每组测试数据:
第一行包含三个整数 n,m 和 k,含义同题目描述。
接下来 n 行,每行包含一个长度为 m 的只包含 ‘A’ 和 ‘B’ 的字符串,表示这份问卷对每个问题的回答。
保证,给定的 n 份问卷互不相同。

输出

对于每组测试数据,输出一行信息 “Case #x: y”(不含引号),其中 x 表示这是第 x 组测试数据,y 表示满足条件的问题集合的个数,行末不要有多余空格。

样例

  • Input
    2
    2 2 1
    AA
    BB
    2 2 2
    AA
    BB
  • Output
    Case #1: 3
    Case #2: 0

题解

  • 可以看到这里问卷长度m最多为10,再加上时间给定6m,我们可以枚举每一种问卷的选择方式,最多也就
  • 如何枚举呢?难道要枚举每一种字符串然后一个一个比对吗?想都不用想,这样必然会炸。所以采用状态压缩的方式,把问卷中的AB当作01,最后形成一个二进制数,然后转换成十进制。比如问卷ABABA,我们可以表示成10101,其十进制为21。这样的话就用一个十进制数代替了一张问卷的答案,并且不会有重复的情况(除非问卷本身就相同)
  • 用数字表示之后怎样才能找到答案呢?很简单,只需要用每一张问卷去合取(&)我们所枚举的那一种状态即可,因为它们的二进制位数相同,所以不同的问卷答案跟相同的值合取得到的答案必不相同
  • 用map存下每次得到的答案的种类和个数,然后凑一下对数,最后凑出的对数大于k则满足情况,计数器+1

Code

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
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
#define LL long long int
#define INIT(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,b,a) for(int i=b-1;i>=a;i--)
//b——0,-1,128,0x3f,127 ,字符
const double Pi = acos(-1);
const double E = exp(1.0);
const LL mod =1e9+7;
const int MAX=0x7fffffff;
const int MIN=-0x7fffffff;
const int INF=0x3f3f3f3f;
using namespace std;
map<int,int> cnt;
int num[10001];
int main()
{
ios::sync_with_stdio(false);
int T;cin>>T;
int n,m,k;
char x;
for(int Num=1;Num<=T;Num++)
{
INIT(num,0);
cin>>n>>m>>k;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>x;
num[i]= x=='A'? num[i]<<1|1:num[i]<<1;
}
}//通过位运算获取当前状态的十进制数
int sum=0,t,he[1001];
for(int sta=1;sta<1<<m;sta++)
{
cnt.clear();INIT(he,0);
for(int i=0;i<n;i++)
{
t=num[i]&sta;
if(cnt[t]==0)cnt[t]=0;
cnt[t]++;
}
t=0;
for(map<int,int>::iterator it=cnt.begin();it!=cnt.end();it++){
if(t==0)he[t]=it->second;
else he[t]=he[t-1]+it->second;
t++;
}//求前缀和,用以计算不同答案的对数
t=0;int Sum=0;
for(map<int,int>::iterator it=cnt.begin();it!=cnt.end();it++){
if(it==cnt.begin())continue;
Sum+=it->second*he[t++];
}
if(Sum>=k)sum++;
}
cout<<"Case #"<<Num<<": "<<sum<<endl;
}
return 0;
}
Donate comment here