[蓝桥杯 2022 省 B] 李白打酒加强版

链接: P8786 [蓝桥杯 2022 省 B] 李白打酒加强版

题目描述

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

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

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

这一路上，他一共遇到店 $N$ 次，遇到花 $M$ 次。已知最后一次遇到的是花，他正好把酒喝光了。

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

注意：壶里没酒（ $0$ 斗）时遇店是合法的，加倍后还是没酒；但是没酒时遇花是不合法的。

输入格式

第一行包含两个整数 $N$ 和 $M$ 。

输出格式

输出一个整数表示答案。由于答案可能很大，输出模 $1000000007$ （即 $10^9+7$ ）的结果。

样例 #1

样例输入 #1

5 10

样例输出 #1

提示

【样例说明】

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

010101101000000
010110010010000
011000110010000
100010110010000
011001000110000
100011000110000
100100010110000
010110100000100
011001001000100
100011001000100
100100011000100
011010000010100
100100100010100
101000001010100
plain

【评测用例规模与约定】

对于 $40 \%$ 的评测用例： $1 \leq N, M \leq 10$ 。

对于 $100 \%$ 的评测用例： $1 \leq N, M \leq 100$ 。

蓝桥杯 2022 省赛 B 组 I 题。

题解

显然我们马上可以思考到dp

现在定义状态:

第 $i$ 次经过酒店, 第 $j$ 次遇到花, 剩下酒为 $k$ 的方案数为 $f[i][j][k]$

有如下状态转移方程:

如果 k 是偶数: $f[i][j][k] = f[i - 1][j][k / 2] + f[i][j - 1][k + 1]$
如果 k 不是偶数, (说明不能是经过店后的状态): $f[i][j][k] = f[i][j - 1][k + 1]$

注意题目要求: 已知最后一次遇到的是花，他正好把酒喝光了 && 没酒时遇花是不合法的

所以我们最终的结果是: $f[n][m - 1][1]$ (第 n 次经过店, 第 m - 1 次经过花, 并且水壶中有酒 1 斗), 这样可以规避 $f[n][m][0] = f[i - 1][j][0] + ...$ 的情况(而外计算了从店来的方案数, 不符合最后一次遇到的是花)

至于 k 为什么最大是 100 ?

因为考虑到它需要花费到为 0, 不然你可能会被开2 << 100的范围给 k, 但是它不合法, 所以也不需要.

再至于为什么 i, j, 在 $f$ 中也是从 0 开始, 并且特判 i, j, 为什么不再 init 的时候赋值 f[0][1][k], f[1][0][k], 然后从 i = 1, j = 1 开始?

因为这样会丢失 f[0][j][k] 和 f[i][0][k] 的数据!

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <tuple>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cmath>
using namespace std;

using ll = long long;

const int inf = 1e9;
const int mod = 1e9 + 7;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<vector<ll>>> f(n + 1, vector<vector<ll>>(m + 1, vector<ll>(100, 0)));
    f[0][0][2] = 1;

    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            for (int k = 0; k < 100; ++k) {
                if (k % 2 == 0 && i)
                    f[i][j][k] += f[i - 1][j][k >> 1];
                
                if (j)
                    f[i][j][k] += f[i][j - 1][k + 1];
                f[i][j][k] %= mod;
            }
        }
    }
    // 已知最后一次遇到的是花
    // 相当于: 第 n 次经过店, 第 m - 1 次 经过花, 并且水壶中有酒 1 斗 
    cout << f[n][m - 1][1] << '\n';
    
    return 0;
}
C++

题目描述​

输入格式​

输出格式​

样例 #1​

样例输入 #1​

样例输出 #1​

提示​

题解