第十三届蓝桥杯C++B组省赛 I 题——李白打酒加强版 (AC)
admin
2024-01-20 22:04:33
0

目录

  • 1.李白打酒加强版
    • 1.题目描述
    • 2.输入格式
    • 3.输出格式
    • 4.样例说明
    • 5.数据规模
    • 6.原题链接
  • 2.解题思路
  • 3.Ac_code

1.李白打酒加强版

1.题目描述

话说大诗人李白, 一生好饮。幸好他从不开车。

一天, 他提着酒壶, 从家里出来, 酒壶中有酒 2 斗。他边走边唱:

无事街上走,提壶去打酒。 逢店加一倍, 遇花喝一斗。

这一路上, 他一共遇到店 NNN 次, 遇到花 MMM 次。已知最后一次遇到的是花,他正好把酒喝光了。

请你计算李白这一路遇到店和花的顺序, 有多少种不同的可能?

注意: 壶里没酒 ( 0 斗) 时遇店是合法的, 加倍后还是没酒; 但是没酒时遇 花是不合法的。

2.输入格式

5 10

3.输出格式

14

4.样例说明

如果我们用 0 代表遇到花,1 代表遇到店,14 种顺序如下:

010101101000000

010110010010000

011000110010000

100010110010000

011001000110000

100011000110000

100100010110000

010110100000100

011001001000100

100011001000100

100100011000100

011010000010100

100100100010100

101000001010100

5.数据规模

1≤N,M≤1001≤N,M≤1001≤N,M≤100

6.原题链接

李白打酒加强版

2.解题思路

比较明显是一道状态机dp的题目,如何定义好状态可以帮助我们更好地初始化和转移以及求解答案,根据题目范围最大为100,比较明显暗示我们做法是一个O(n3)O(n^3)O(n3)的dpdp状态也应该是三维的。定义状态f[i][j][k]f[i][j][k]f[i][j][k] 为已经遇到 iii 次店,jjj次花,还剩 kkk 斗酒的方案数。状态初始化明显是f[0][0][2]=1

对于酒的上限数量,我们应该想好范围,因为花最多只有 mmm 朵,意味着我们最多只能喝 mmm 壶酒,对于 kkk 超过 mmm 的状态都是无效状态我们无需关心。所以剩余酒的上限也就是 kkk 应该也定为 mmm 。

考虑进行状态转移,对于状态f[i][j][k]f[i][j][k]f[i][j][k],假设最后一次遇到的是店,那么此时需要保证 iii 大于0,并且 kkk 是偶数,因为遇到店剩余酒翻倍,kkk 一定不可能为奇数,那么可以得到转移方程
f[i][j][k]=(f[i][j][k]+f[i−1][j][k/2])%modf[i][j][k] = (f[i][j][k] + f[i - 1][j][k / 2]) \% modf[i][j][k]=(f[i][j][k]+f[i−1][j][k/2])%mod

假设最后一次遇到的是花,那么此时只需要保证 jjj 大于 0即可,我们可以获得转移方程f[i][j][k]=(f[i][j][k]+f[i][j−1][k+1])%modf[i][j][k] = (f[i][j][k] + f[i][j - 1][k + 1]) \% modf[i][j][k]=(f[i][j][k]+f[i][j−1][k+1])%mod

我们还得考虑答案输出什么,题目要求最后一次遇到的必须是花,那么我们直接输出 f[n][m][0]f[n][m][0]f[n][m][0] 肯定是错误的答案。 因为这并不能保证最后一次遇到的是花,因为最后是0壶酒,那么在遇到最后一朵花时应该还剩1壶酒,所以我们可以输出 f[n][m−1][1]f[n][m-1][1]f[n][m−1][1] 作为答案。

3.Ac_code

#include
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 110;int n, m;
//已经遇到i次店,j次花,还剩k斗酒的方案数
LL f[N][N][N];
void solve()
{cin >> n >> m;f[0][0][2] = 1;for (int i = 0; i <= n; ++i) {for (int j = 0; j <= m; ++j) {for (int k = 0; k <= m; ++k) {//最后一次遇到店if (i && k % 2 == 0) f[i][j][k] = (f[i][j][k] + f[i - 1][j][k / 2]) % mod;//最后一次遇到花if (j) f[i][j][k] = (f[i][j][k] + f[i][j - 1][k + 1]) % mod;}}}cout << f[n][m - 1][1] << '\n';
}
int main()
{ios_base :: sync_with_stdio(false);cin.tie(nullptr);int t = 1;while (t--){solve();}return 0;
}

相关内容

热门资讯

安卓系统用的华为应用,探索智能... 你知道吗?在安卓系统里,华为的应用可是个宝库呢!它们不仅功能强大,而且使用起来超级方便。今天,就让我...
安卓变ios系统魅蓝 你知道吗?最近有个朋友突然告诉我,他要把自己的安卓手机换成iOS系统,而且还是魅蓝品牌的!这可真是让...
幻书启世录安卓系统,安卓世界中... 亲爱的读者们,你是否曾在某个夜晚,被一本神奇的书所吸引,仿佛它拥有着穿越时空的力量?今天,我要带你走...
电脑安装安卓系统进不去,安卓系... 电脑安装安卓系统后竟然进不去,这可真是让人头疼的问题啊!你是不是也遇到了这种情况,心里直呼“怎么办怎...
用键盘切换控制安卓系统,畅享安... 你有没有想过,用键盘来控制你的安卓手机?是的,你没听错,就是那个我们每天敲敲打打的小玩意儿——键盘。...
小米安卓镜像系统在哪,小米安卓... 你有没有想过,你的小米手机里有一个隐藏的宝藏——安卓镜像系统?没错,就是那个可以让你的手机瞬间变身成...
安卓手机下载排班系统,高效排班... 你有没有想过,每天忙碌的工作中,有没有什么好帮手能帮你轻松管理时间呢?今天,就让我来给你介绍一个超级...
桌面组件如何弄安卓系统,桌面组... 亲爱的桌面爱好者们,你是否曾梦想过将安卓系统搬到你的电脑桌面上?想象那些流畅的动画、丰富的应用,还有...
安卓13系统介绍视频,新功能与... 亲爱的读者们,你是否对安卓13系统充满好奇?想要一探究竟,却又苦于没有足够的时间去研究?别担心,今天...
车机安卓7.1系统,功能升级与... 你有没有发现,现在的车机系统越来越智能了?尤其是那些搭载了安卓7.1系统的车机,简直就像是个贴心的智...
安卓系统下如何读pdf,And... 你有没有遇到过这种情况:手机里存了一大堆PDF文件,可是怎么也找不到一个能顺畅阅读的工具?别急,今天...
安卓系统全国通用的吗,畅享智能... 你有没有想过,为什么你的手机里装的是安卓系统呢?安卓系统,这个名字听起来是不是有点神秘?今天,就让我...
假苹果手机8安卓系统,颠覆传统... 你有没有想过,如果苹果手机突然变成了安卓系统,会是怎样的景象呢?想象那熟悉的苹果外观,却运行着安卓的...
安卓12.0系统vivo有吗,... 你有没有听说最近安卓系统又升级啦?没错,就是那个让手机焕然一新的安卓12.0系统!那么,咱们国内的手...
核心芯片和安卓系统,探索核心芯... 你知道吗?在科技的世界里,有一对“黄金搭档”正悄悄改变着我们的生活。他们就是——核心芯片和安卓系统。...
如何调安卓系统屏幕颜色,安卓系... 亲爱的手机控们,你是否曾觉得安卓系统的屏幕颜色不够个性,或者是因为长时间盯着屏幕而感到眼睛疲劳?别担...
旧台式电脑安装安卓系统,轻松安... 你那台旧台式电脑是不是已经服役多年,性能逐渐力不从心,却又不忍心让它退役呢?别急,今天就来教你怎么给...
美国要求关闭安卓系统,科技霸权... 美国要求关闭安卓系统:一场技术革新还是政治博弈?在数字化时代,智能手机已经成为我们生活中不可或缺的一...
安卓系统日记本 你有没有发现,手机里的安卓系统日记本,简直就是记录生活点滴的宝藏库呢?想象每天忙碌的生活中,有没有那...
安卓手机广告最少的系统,探索安... 你有没有发现,用安卓手机的时候,广告总是无处不在,让人烦得要命?不过别急,今天我要给你揭秘一个秘密—...