算法1
dfs
时间复杂度
O(2^14)
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
unordered_map<char,int> h1,h2;//h1奇数 h2偶数
char ch[7]={'B','E','S','I','G','O','M'};
vector<int> path;
int check()
{
int B=path[0],E=path[1],S=path[2],I=path[3],G=path[4],O=path[5],M=path[6];
return !((B+E+S+S+I+E)*(G+O+E+S)*(M+O+O)&1);
}
int dfs(int u,int x)
{
if(u==7)
{
if(check())
{
return x;
}
return 0;
}
int res=0;
path.push_back(1);//推一个奇数
res+=dfs(u+1,x*h1[ch[u]]);
path.pop_back();
path.push_back(2);//推一个偶数
res+=dfs(u+1,x*h2[ch[u]]);
path.pop_back();
return res;
}
int main()
{
int n;
cin>>n;
while (n -- )
{
char c;
int x;
cin>>c>>x;
if(x&1) h1[c]++;
else h2[c]++;
}
cout<<dfs(0,1);
return 0;
}