[第五届蓝桥杯省赛C++B组]李白打酒
C++ 蓝桥 省赛 第五届
2023-09-11 14:18:49 时间
来源:第五届蓝桥杯省赛C++B组
算法标签:dfs
题目描述:
话说大诗人李白,一生好饮。幸好他从不开车。
一天,他提着酒壶,从家里出来,酒壶中有酒2斗。他边走边唱:
无事街上走,提壶去打酒。
逢店加一倍,遇花喝一斗。
这一路上,他一共遇到店5次,遇到花10次,已知最后一次遇到的是花,他正好把酒喝光了。
请你计算李白遇到店和花的次序,可以把遇店记为a,遇花记为b。则:babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢?请你计算出所有可能方案的个数(包含题目给出的)。
注意:通过浏览器提交答案。答案是个整数。不要书写任何多余的内容。
题目答案:
14
题目思路:
变量单位有:花 、店、酒
且我们得到信息逢店加一倍,遇花喝一斗。这一路上,他一共遇到店5次,遇到花10次,已知最后一次遇到的是花,他正好把酒喝光了。
则表明如果遇到店,酒*2,如果遇到花,酒-1,当到了第15次选择完毕之后退出。
由此我们可以利用暴搜抓出每一个状态找出符合条件的次数。
题目代码:
dfs
#include<iostream>
using namespace std;
int cnt;
void dfs(int a,int b,int sum,int u,int flag)//分别表示 店 花 酒量 位置 最后一个位置表示
{
if(u==15)
{
if(a==5&&b==10&&sum==0&&flag==0)
{
cnt++;
return;
}
}
else
{
dfs(a+1,b,sum*2,u+1,1);//下一个遇到店
dfs(a,b+1,sum-1,u+1,0);//下一个遇到花
}
}
int main()
{
dfs(0,0,2,0,0);
cout<<cnt;
return 0;
}
二进制
int ans = 0;
for (int i = 0; i < (1<<14); ++i) {
int tot_1 = 0;
int tot_0 = 0;
int num = 2;
for (int j = 0; j < 14; ++j) {
if (i&(1 << j)) { // 这里判断二进制 i 从右数第 j + 1 位是否为 1
tot_1++;
num = num * 2;
} else {
tot_0++;
num = num - 1;
}
}
if (tot_1 == 5 && tot_0 == 9 && num == 1) {
++ans; // 记录合法方案数
}
}
相关文章
- C++11时代的标准库快餐教程(3) - 排序
- 第十一届蓝桥杯省赛第一场C++A/B组真题(节选)
- 【思特奇杯·云上蓝桥-算法训练营】第十一届蓝桥杯大赛第二场省赛试题C&C++ 大学B组真题
- 蓝桥杯官网 试题 PREV-229 历届真题 子串分值和【第十一届】【决赛】【研究生组】【C++】【C】【Java】【Python】四种解法
- 蓝桥杯官网 试题 PREV-255 历届真题 蓝肽子序列【第十一届】【决赛】【研究生组】【C++】【Java】【Python】三种解法
- 蓝桥杯官网 试题 PREV-260 历届真题 重复字符串【第十一届】【决赛】【研究生组】【C++】【C】【Java】【Python】四种解法
- 蓝桥杯官网 试题 PREV-267 历届真题 异或数列【第十二届】【省赛】【研究生组】【C++】【Java】两种解法
- 蓝桥杯官网 试题 PREV-281 历届真题 时间显示【第十二届】【省赛】【研究生组】【C++】【C】【Java】【Python】四种解法
- C++11:noexcept关键字
- [C/C++标准库]_[0基础]_[交集和补集]
- C++ json库jsoncpp 吐槽
- atitit.软件开发GUI 布局管理优缺点总结java swing wpf web html c++ qt php asp.net winform
- C++ 容器:顺序性容器、关联式容器和容器适配器
- C++ 鼠标模拟程序
- HeadFirst设计模式 之 C++实现(二):Observer(观察者模式)
- PAT 1140 C++ 版
- 第十三届蓝桥杯省赛 C++ A 组 F 题、Java A 组 G题、C组 H 题、Python C 组 I 题——青蛙过河(AC)
- 第十三届蓝桥杯国赛 C++ C 组 Java A 组 C 组 Python C 组 E 题——斐波那契数组(三语言代码AC)
- 第十三届蓝桥杯省赛 C++ C 组 E 题、Python B组 D题、PythonC组 D 题—— 数位排序(AC)
- 第十三届蓝桥杯省赛C++A组 D 题、C++C组 F 题、Java C 组 F 题——选数异或 (AC)
- 第十三届蓝桥杯Java、C++、Python组国赛真题——环境治理(三语言AC)
- 第十三届蓝桥杯B组C++(试题B:顺子日期)
- 第十三届蓝桥杯B组C++(试题A:九进制转十进制)
- C++算法之搜索算法一 深度优先搜索