AcWing 1875. 贝茜的报复
原题链接
简单
二进制写法
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 150;
int n;
int res;
int main()
{
cin >> n;
// 这个哈希表保存了字母是奇数或者偶数的所有选法
unordered_map<char, int> cnt[2];
while (n -- )
{
int x;
char c;
cin >> c >> x;
cnt[abs(x) % 2][c] ++;
}
char str[] = "BESIGOM";
// 该哈希表用来保存枚举到的状态的字母是奇数还是偶数
unordered_map<char, int> v;
// 整个思路就是枚举所有情况,判断当前情况是否合法,如果合法就统计总数
for (int i = 0; i < 1 << 7; i ++)
{
for (int j = 0; j < 7; j ++)
{
// 保存当前情况的七个字母是奇数还是偶数
v[str[j]] = i >> j & 1;
}
// (B+E+S+S+I+E)(G+O+E+S)(M+O+O) 由于我们是对2取余数,所以可以化简为(B+I)(G+O+E+S)M
// 如果当前枚举到的情况是合法的话,就统计方案数
if ((v['B'] + v['I']) * (v['G'] + v['O'] + v['E'] + v['S']) * v['M'] % 2 == 0)
{
int sum = 1;
for (int j = 0; j < 7; j ++)
{
// cnt[i >> j & 1][str[j]] 表示当前枚举到的字母选择奇数或者偶数的所有选法,根据乘法原理,乘起来即可
sum *= cnt[i >> j & 1][str[j]];
}
res += sum;
}
}
cout << res << endl;
return 0;
}
DFS
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 150;
int n;
int ans;
char str[] = "BESIGOM";
int path[10];
// 这个哈希表保存了字母是奇数或者偶数的所有选法
unordered_map<char, int> cnt[2];
void dfs(int u, int sum)
{
if (u == 7)
{
if ((path[0] + path[3]) * (path[4] + path[5] + path[1] + path[2]) * path[6] % 2 == 0)
{
ans += sum;
}
return;
}
path[u] = 1;
dfs(u + 1, sum * cnt[1][str[u]]);
path[u] = 0;
dfs(u + 1, sum * cnt[0][str[u]]);
}
int main()
{
cin >> n;
while (n -- )
{
int x;
char c;
cin >> c >> x;
cnt[abs(x) % 2][c] ++;
}
dfs(0, 1);
cout << ans << endl;
return 0;
}