给定N个字符串,每个字符串全部由小写字母组成,且每个字符串的长度最 多为8,请你判断有多少重组字符串,重组字符串有以下规则: 1.从每个字符串里面都抽取1个字母组成 2.新字符串不能有2个相同的字母 请问总共能组成多少个重组字符串。给出C++代码
时间: 2023-05-29 19:06:41 浏览: 38
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
string *str = new string[n];
int *cnt = new int[1 << 26]; // 使用二进制压缩状态
memset(cnt, 0, sizeof(int) * (1 << 26));
for (int i = 0; i < n; i++)
{
cin >> str[i];
int state = 0;
for (int j = 0; j < str[i].length(); j++)
{
state |= 1 << (str[i][j] - 'a'); // 将每个字符串转化为状态
}
cnt[state]++; // 记录每个状态出现的次数
}
long long ans = 0;
for (int i = 0; i < (1 << 26); i++)
{
if (cnt[i] == 0) continue; // 如果状态出现次数为0,直接跳过
for (int j = i + 1; j < (1 << 26); j++)
{
if (cnt[j] == 0) continue;
if ((i & j) == 0) // 如果两个状态没有交集,说明可以组成重组字符串
{
ans += (long long)cnt[i] * cnt[j];
}
}
}
cout << ans << endl;
delete[] str;
delete[] cnt;
return 0;
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)