AcWing 1875. 贝茜的报复
打卡
这题的dfs太妙了。
#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
typedef long long ll;
const int N=1e5+10;
map<char,int>ji,ou,mp;
//存某个字母变量的奇偶个数
//mp存枚举的是奇数还是偶数 1代表奇数 2代表偶数
int n;
string str="BESIGOM";
int ans;
//B+I G+O+E+S M
void dfs(int u,int sum)
{
if(u==7)
{
if((mp['B']+mp['I'])%2&&(mp['G']+mp['O']+mp['E']+mp['S'])%2&&mp['M']%2) return;
ans+=sum;
return;
}
char ch=str[u];
mp[ch]=1;dfs(u+1,sum*ji[ch]);//选这个字母的奇数
mp[ch]=2;dfs(u+1,sum*ou[ch]);//偶数
}
int main()
{
cin>>n;
while(n--)
{
char ch;int t;cin>>ch>>t;
if(abs(t)%2) ji[ch]++;
else ou[ch]++;
}
dfs(0,1);
cout<<ans;
return 0;
}