2018百度之星资格赛___1001调查问卷 —— 状态压缩

本文主要是介绍2018百度之星资格赛___1001调查问卷 —— 状态压缩，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

补题链接：传送门

题目大意：

  有$T$组样例，$n$份问卷，每份问卷有$m$个问题，答案由A或B组成(相当于$n$条长度为$m$的01序列)，在这$m$个问题中任意选取一部分，要使这新的零散问卷互不相同，且至少有k对，问这样选取一共有多少种方案？？？

解题思路：

  因为$m<=10$，所以一共只有$2^{10}$种状态，用状态压缩即可解决，还有一点就是$k$种互不相同的状态的存储问题（当时因为这一点想了很久），看代码即可

代码思路：

  暴力枚举每种状态即可，设A为0，只需要判断是否为B即可

核心：考虑状态的可行性和互不相同的判断方法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char ch[1010][15];
int dp[1<<11], binary[1005];int main() {int cas=1, T;scanf("%d", &T);while(T--) {int n, m, k;scanf("%d%d%d", &n, &m, &k);getchar();for(int i=1; i<=n; i++) scanf("%s",ch[i]);if(n*(n-1)/2<k) {printf("Case #%d: 0\n", cas++);continue;}int ans=0;for(int i=1; i<(1<<m); i++) {int num=0;memset(dp, 0, sizeof(dp));for(int j=1; j<=n; j++) {int tot=0;for(int t=0; t<m; t++) {if(i&(1<<t) && ch[j][t]=='B')tot += (1<<t);}binary[j] = tot;}for(int j=1; j<=n; j++) {int k = ++dp[ binary[j] ];num += (j-k);}if(num>=k) ans++;}printf("Case #%d: %d\n", cas++, ans);}
}

这篇关于2018百度之星资格赛___1001调查问卷 —— 状态压缩的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---