Atcoder beginner contest 249 C-Just K（二进制枚举）

题目大意：给你N个字符串，你可以从中选择任意数量的字符串，请统计在你的字串中，相同字母出现次数正好为K次的字母数。数据保证出现的字母都是小写字母。

1≤N≤15
1 ≤K≤N

一开始读题的时候读错了，读成了至少为k次，就想的暴力选择全部字符串，然后统计字母数，但是在认真读题WA了N发后发现是恰好为K次，所以正确打开方式应该是

用二进制枚举所有选择方案，然后不断更新最大值。

因为每一个字符串在本题中只有两种状态：选（1），不选（0）

所以我们对于所有字符串总共有2^N个方案

我们随意取其中一个例子：20，将其转为二进制：10100

此时表示我们选择第一个和第三个字符串，其余字符串不选择，以这种方法我们可以将2^N次个方案全部枚举一遍，每次都统计出现字母的次数

通过，枚举每个方案

这时我们遇到了第二个问题，在每个方案中我们怎么知道每个字符串是否被选择到

这时就需要‘&’，按位与

1<<x == 2^x，二进制为100....000

1<<1 == 2,二进制为10

1<<2 == 4 二进制为100

1<<3 == 8,二进制为1000

除了第x位以外全是0，所以可以取出当前方案中的每一位，判断是否选择这个字符串，剩下的就是统计出现字母的次数了（map,数组映射都可以）

 1 #include <iostream>

 2 #include <map>

 3 #include <algorithm>

 4 #include <cstring>

 5 #define int long long

 6 #define endl "\n"

 7 using namespace std;

 8 signed main()

 9 {

10     ios::sync_with_stdio(false);

11     cin.tie(0);

12     int n, m;

13     cin >> n >> m;

14     string a[25];

15     int ans = 0;

16     for (int i = 0; i < n; ++i)

17         cin >> a[i];

18     for (int i = 0; i < (1 << n); ++i)

19     {

20         int mp[26] = {0};

21         for (int j = 0; j < n; ++j)

22         {

23             if (i & (1 << j))

24             {

25                 for (int k = 0; k < a[j].length(); ++k)

26                 {

27                     mp[a[j][k] - 'a']++;

28                 }

29             }

30         }

31         int res = 0;

32         for (char j = 0; j < 26; ++j)

33         {

34             if (mp[j] == m)

35             {

36                 res++;

37             }

38         }

39         ans = max(ans, res);

40     }

41     printf("%lld", ans);

42

43     return 0;

44 }

巴特西

Atcoder beginner contest 249 C-Just K（二进制枚举）

最新文章

热门文章