## 百度之星2018-资格赛-调查问卷

### Input

$$1 \leq T \leq 100$$
$$1 \leq n \leq 10^3$$
$$1 \leq m \leq 10$$
$$1 \leq k \leq 10^6$$
​​

2
2 2 1
AA
BB
2 2 2
AA
BB

Case #1: 3
Case #2: 0

### 思路 >.<

dp怎么做呢，枚举所有的题目可能呗....

int bit_trans(char * str, int length){
int s = 0;
for (int i = 0; i < length; i ++) {
s <<= 1;
s |= (str[i] -'A');
}
return s;
}



### TLE（超时）的代码

int main(){
int testCase = 1,n,m,k;
int T;
cin >> T;
char temp[10+1];
while (testCase <= T ) {
cin >> n >> m >> k;
memset(dp, 0, sizeof(dp));
for (int  i = 1; i <= n ;  i ++ ) {
cin >> temp;
seq[i] = bit_trans(temp, m);
}
int max_move = 1 << m;

for (int i = 1 ; i <= n; i ++ ) {
for (int j = 0 ; j < max_move ; j++ ) {
int S = seq[i] & j;
int diff = 0;
for (int k = 1; k <= i ; k ++) {
if( ( seq[k]  & j ) == S ){
diff ++;
}
}
dp[i][j] = dp[i-1][j] + i - diff;
}
}
int ans = 0;
for (int  i = 0; i < max_move;  i ++) {
if(dp[n][i] >= k ){
ans ++;
}
}
cout<<"Case #"<<testCase<<": "<<ans<<endl;
testCase ++;
}
return 0;
}


### AC的代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include <iostream>

#define MAXN 1000 + 1
#define MAXM (1 << 10) + 1
#define LL long long

using namespace std;
int same_cnt[MAXM];
int seq[MAXN];
LL dp[MAXN][MAXM];

int bit_trans(char * str, int length){
int s = 0;
for (int i = 0; i < length; i ++) {
s <<= 1;
s |= (str[i] -'A');
}
return s;
}

int main(){
int testCase = 1,n,m,k;
int T;
cin >> T;
char temp[10+1];
while (testCase <= T ) {
cin >> n >> m >> k;
for (int  i = 1; i <= n ;  i ++ ) {
cin >> temp;
seq[i] = bit_trans(temp, m);
}
int max_move = 1 << m;

memset(dp, 0, sizeof(dp));
for (int j = 0 ;  j <= max_move; j ++) {
memset(same_cnt, 0, sizeof(same_cnt));
for (int i = 1 ; i <= n; i ++ ) {
int answer = seq[i] & j;
dp[i][j] = dp[i-1][j] + i - same_cnt[answer];
}
}

int ans = 0;
for (int  i = 0; i < max_move;  i ++) {
if(dp[n][i] >= k ){
ans ++;
}
}

cout<<"Case #"<<testCase<<": "<<ans<<endl;
testCase ++;
}
return 0;
}