【AcWing寒假每日一题2022】今年寒假不学习,学习只刷算法题之--AcWing 1875. 贝茜的报复
2022/1/24 22:06:58
本文主要是介绍【AcWing寒假每日一题2022】今年寒假不学习,学习只刷算法题之--AcWing 1875. 贝茜的报复,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
农夫约翰和奶牛贝茜喜欢在业余时间互相出数学题。
约翰给贝茜出了一道相当难的问题,导致她没能解决。
现在,她希望通过给约翰出一道有挑战性的难题来报复他。
贝茜给了约翰一个表达式
(
B
+
E
+
S
+
S
+
I
+
E
)
(
G
+
O
+
E
+
S
)
(
M
+
O
+
O
)
(B+E+S+S+I+E)(G+O+E+S)(M+O+O)
(B+E+S+S+I+E)(G+O+E+S)(M+O+O),其中包含七个变量
B
,
E
,
S
,
I
,
G
,
O
,
M
B,E,S,I,G,O,M
B,E,S,I,G,O,M(
O
O
O 是变量,不是零)。
对于每个变量,她给约翰一个列表,表中包含该变量可采用的最多
20
20
20 个整数值。
她要求约翰计算,共有多少种给变量赋值的方法可以使得表达式的计算结果为偶数。
输入格式
第一行包含一个整数
N
N
N。
接下来
N
N
N行,每行包含一个变量和该变量的一个可能值。
每个变量至少出现
1
1
1 次,最多出现
20
20
20 次。
同一变量不会重复列出同一可能值。
输出格式
输出可以使得表达式的计算结果是偶数的给变量赋值的方法总数。
数据范围
7
≤
N
≤
140
7≤N≤140
7≤N≤140 ,
所有变量的可能取值范围
[
−
300
,
300
]
[−300,300]
[−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; }
这篇关于【AcWing寒假每日一题2022】今年寒假不学习,学习只刷算法题之--AcWing 1875. 贝茜的报复的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升