第十三届蓝桥杯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;
}

相关内容

热门资讯

汽车导航安卓系统更新吗,优化驾... 你有没有发现,你的汽车导航系统最近是不是有点儿“慢吞吞”的?别急,让我来给你揭秘汽车导航安卓系统到底...
安卓系统提示网页缓存,网页缓存... 手机屏幕上突然跳出个提示,说是安卓系统检测到网页缓存,这可真是让人有点摸不着头脑。别急,让我来给你详...
安卓系统怎么下载商品,一键操作... 你有没有想过,在安卓系统上下载商品竟然也能变得如此简单?没错,就是那种一键操作,轻松搞定的事情。今天...
安卓手机简易操作系统,探索安卓... 你有没有发现,现在安卓手机的可玩性越来越强了?这不,我就来给你详细介绍一下安卓手机的简易操作系统,让...
安卓系统限制安卓其它app怎么... 你是不是也遇到了这样的烦恼?手机里安装了安卓系统,但是有些APP却因为权限限制而无法正常使用。别急,...
玩客云换安卓系统,开启智能存储... 你有没有想过,家里的玩客云设备也能换上安卓系统,变成一个全能的小助手呢?没错,就是那个曾经只用来存储...
安卓监管系统官网,构建和谐网络... 你有没有听说最近安卓监管系统官网更新啦?没错,就是那个我们平时手机上不可或缺的小助手,现在变得更加智...
能运行安卓的linux系统,技... 你有没有想过,你的手机操作系统其实可以像电脑一样,拥有无限的可能?没错,就是能运行安卓的Linux系...
安卓系统如何连宝马互联,开启智... 你有没有想过,你的安卓手机和宝马车之间也能来个亲密接触呢?没错,就是那种无缝连接的感觉,让你的宝马互...
安卓平板刷锤子系统 你有没有想过,你的安卓平板可以焕然一新,变成一个全新的操作系统呢?没错,就是那个传说中的锤子系统!今...
老安卓平板系统卡顿,揭秘原因与... 你有没有发现,家里的老安卓平板最近变得有点“慢吞吞”的?是不是也觉得它像只乌龟,跑得越来越慢了?别急...
宾果消消消安卓系统,畅快体验指... 你有没有发现,最近手机游戏界又掀起了一股热潮?没错,就是那款让人停不下来的“宾果消消消安卓系统”游戏...
康佳非安卓系统下载,下载新体验... 你有没有发现,家里的康佳电视突然变得有点儿不按套路出牌了?别急,别急,让我来给你揭秘康佳非安卓系统下...
安卓系统如何设置net模式,安... 你有没有想过,你的安卓手机里那个神秘的“net模式”到底是个啥?别急,今天就来给你详细揭秘怎么设置这...
安卓o系统是什么字体,揭秘其独... 你有没有发现,自从你的安卓手机升级到了O系统,字体好像有点不一样了呢?是不是好奇这背后的秘密?别急,...
安卓系统无法用手机充电,为何充... 最近是不是你也遇到了这样的烦恼:安卓手机充电时,电量却怎么也充不上去?别急,今天就来给你详细解析一下...
安卓手机window系统重装,... 你那安卓手机是不是突然间卡得跟蜗牛似的,连个微信消息都发不出去?别急,今天就来教你一招,让你的安卓手...
安卓手机检查系统更新,系统更新... 亲爱的手机控们,你是不是也和我一样,时不时地会好奇自己的安卓手机是不是已经更新到了最新的系统呢?毕竟...
苹果系统王者简单吗安卓,简单易... 你有没有想过,为什么苹果系统和安卓系统在手机市场上如此火爆?它们各有各的特色,但要说哪个更简单易用,...
腾讯中国象棋安卓系统 你知道吗?在手机上玩中国象棋,竟然也能这么过瘾!今天,就让我带你深入了解一下腾讯中国象棋安卓系统的那...