[数据结构与算法]【AcWing寒假每日一题2022】今年寒假不学习，学习只刷算法题之--AcWing 1875. 贝茜的报复

题目描述

农夫约翰和奶牛贝茜喜欢在业余时间互相出数学题。
约翰给贝茜出了一道相当难的问题，导致她没能解决。
现在，她希望通过给约翰出一道有挑战性的难题来报复他。
贝茜给了约翰一个表达式 $(B+E+S+S+I+E)(G+O+E+S)(M+O+O)$，其中包含七个变量 $B,E,S,I,G,O,M$（$O$ 是变量，不是零）。
对于每个变量，她给约翰一个列表，表中包含该变量可采用的最多 $20$ 个整数值。
她要求约翰计算，共有多少种给变量赋值的方法可以使得表达式的计算结果为偶数。

输入格式

第一行包含一个整数 $N$。
接下来 $N$行，每行包含一个变量和该变量的一个可能值。
每个变量至少出现 $1$ 次，最多出现 $20$ 次。
同一变量不会重复列出同一可能值。

输出格式

输出可以使得表达式的计算结果是偶数的给变量赋值的方法总数。

数据范围

$7\le N\le 140$ ,
所有变量的可能取值范围$[?300,300]$
本题答案不会超出int范围。

输入样例：

10
B 2
E 5
S 7
I 10
O 16
M 19
B 3
G 1
I 9
M 2

输出样例：

6

样例解释

共有 6 种可能的赋值方式：

(B,E,S,I,G,O,M) = (2, 5, 7, 10, 1, 16, 19) -> 53,244
                = (2, 5, 7, 10, 1, 16, 2 ) -> 35,496
                = (2, 5, 7, 9,  1, 16, 2 ) -> 34,510
                = (3, 5, 7, 10, 1, 16, 2 ) -> 36,482
                = (3, 5, 7, 9,  1, 16, 19) -> 53,244
                = (3, 5, 7, 9,  1, 16, 2 ) -> 35,496

注意，(2, 5, 7, 10, 1, 16, 19) 和 (3, 5, 7, 9, 1, 16, 19)，虽然计算结果相同，但是赋值方式不同，所以要分别计数。

#include <bits/stdc++.h>
using namespace std;

int cnt;
map<char,int> map1,map2,a;
string s = "BESIGOM";

void dfs(int u,int x)
{
    if(u==7) {
        if(/*一个偶数也没有，剪枝且不计数*/(a['B'] + a['I']) % 2 && (a['G'] + a['O'] + a['E'] + a['S']) % 2 && a['M'] % 2) return;
        cnt+=x;
        return ;
    }
    char ch=s[u];
    a[ch]=1,dfs(u+1,map1[ch]*x);
    a[ch]=2,dfs(u+1,map2[ch]*x);
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    int n;cin>>n;
    while(n--) {
        char ch;int x;cin>>ch>>x;
        if(x%2!=0) map1[ch]++;
        else map2[ch]++;
    } 
    dfs(0,1);
    cout<<cnt<<endl;
    return 0;
}