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

Problem Description

度度熊为了完成毕业论文,需要收集一些数据来支撑他的论据,于是设计了一份包含 mm 个问题的调查问卷,每个问题只有 'A' 和 'B' 两种选项。

将问卷散发出去之后,度度熊收到了 n 份互不相同的问卷,在整理结果的时候,他发现可以只保留其中的一部分问题,使得这 n 份问卷仍然是互不相同的。这里认为两张问卷是不同的,当且仅当存在至少一个被保留的问题在这两份问卷中的回答不同。

现在度度熊想知道,存在多少个问题集合,使得这 n 份问卷在只保留这个集合的问题之后至少有 k 对问卷是不同的。

Input

第一行包含一个整数 T,表示有 T 组测试数据。

接下来依次描述 T 组测试数据。对于每组测试数据:

第一行包含三个整数 n,m 和 k,含义同题目描述。

接下来 n 行,每行包含一个长度为 m 的只包含 'A' 和 'B' 的字符串,表示这份问卷对每个问题的回答。

保证

$$ 1 \leq T \leq 100 $$
$$ 1 \leq n \leq 10^3 $$
$$ 1 \leq m \leq 10 $$
$$ 1 \leq k \leq 10^6 $$
​​
给定的 nn 份问卷互不相同。

Output

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

Sample Input

2
2 2 1
AA
BB
2 2 2
AA
BB

Sample Output

Case #1: 3
Case #2: 0

思路 >.<

下午才想起来今天百度之星预选要结束了,上去topcoder看看,随便选个AC率高的吧....

一看题目,懵逼,想了一会,还是用dp吧...

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

那怎么枚举呢?

借助位运算呗,反正题目的要求最多10题,2^10也就1024,用二进制表示,1表示使用题目,0表示去除题目,如 1001 表示 题目4和题目1保留,那么对于答卷,我们只需要把答卷事先用下面的函数转换为数字,然后用数字的与运算计算即可:

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;
}

就用 dpi 表示 第i行,第j题集,有多少个不同的运算对

首先看看:

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;
}

循环太多次了,其实内层k的循环可以存起来,

运算的时候,借助动态规划和填表的方法节省时间,代码如下

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;
                same_cnt[answer] ++;
                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;
}
标签: 百度之星
返回文章列表 文章二维码
本页链接的二维码
打赏二维码