码蹄集 - MT2013 · 饿饿︕饭饭︕ - 解题思路版本

• • 饿饿！饭饭！
  • • 题目描述
    • 输入描述
    • 输出描述
    • 样例一
    • • 输入
      • 输出
• 题目分析
• AC代码
• 拓展：

• 饿饿！饭饭！

时间限制：1秒
空间限制：64M

嗯哼，小码哥在新的一年里不会忘记身为干饭人的初心！

众所周知，小码哥非常不喜欢一直吃同样的东西，但由于理想与现实的差距，食堂在这n天里只会供应k种餐食。

在一天吃3餐的情况下，前w天一共wtimes3w×3顿饭小码哥不希望有任何一顿重复。现在请问食堂有多少种方案可以满足超级可爱乖巧的小码哥的需要。

第一行，三个整数n，k，w表示n天内食堂只会供应k种餐室，w的意义详见题面

输出一行一个数，表示满足小码哥需要的方案数。

5 4 1

24

看题后不禁思索：这个 n n n有啥用呢？食堂提供 n n n天的饭，如果小码哥想吃 w w w天且 w > n w>n w>n的话是不是就没有可行方案了呢？

算了，先骗一波数据吧。

#include 
using namespace std;
int main() {
    int n, k, w;
    cin >> n >> k >> w;
    assert(n >= k);
    return 0;
}

运行结果：

Compile Successfully.

- Test Point #0: Wrong Answer, Time = 2 ms, Memory = 172 KB, Score = 0
- Test Point #1: Wrong Answer, Time = 2 ms, Memory = 0 KB, Score = 0
- Test Point #2: Wrong Answer, Time = 2 ms, Memory = 148 KB, Score = 0
- Test Point #3: Wrong Answer, Time = 2 ms, Memory = 156 KB, Score = 0
- Test Point #4: Wrong Answer, Time = 2 ms, Memory = 148 KB, Score = 0
- Test Point #5: Wrong Answer, Time = 2 ms, Memory = 184 KB, Score = 0
- Test Point #6: Wrong Answer, Time = 2 ms, Memory = 148 KB, Score = 0
- Test Point #7: Wrong Answer, Time = 2 ms, Memory = 216 KB, Score = 0
- Test Point #8: Wrong Answer, Time = 2 ms, Memory = 152 KB, Score = 0
- Test Point #9: Wrong Answer, Time = 2 ms, Memory = 152 KB, Score = 0

Wrong Answer, Time = 20 ms, Memory = 216 KB, Score = 0

喔！没有运行错误耶。也就是说 n n n一定是 ≥ w geq w ≥w的，我们只需要考虑 k k k和 w w w的关系即可。

既然要吃 w w w天，那就要吃 w ∗ 3 w*3 w∗3顿饭。所以输入了 w w w后不妨直接 w ∗ = 3 w*=3 w∗=3

那么题目意思就是：在 k k k种选择种选 w w w（已×3）种有多少种不同的方案。

这不就是典型的排列数吗？公式 A k w = ( k ) × ( k − 1 ) × ⋯ × ( k − w + 1 ) A_k^w = (k) times (k - 1) times cdotstimes(k - w + 1) Akw​=(k)×(k−1)×⋯×(k−w+1)。

因为 k ≤ 12 kleq12 k≤12，且 12 ! = 479 , 001 , 600 < 1 0 9 < I N T _ M A X 12!=479,001,600<10^9 AC代码

#include 
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
int main() {
    int n, k, w;
    cin >> n >> k >> w;
    w *= 3;
    if (k < w) {  // 如果可挑选种类 < 总顿数
        puts("0");
        return 0;
    }
    int ans = 1;
    for (int i = k; i >= k - w + 1; i--)
        ans *= i;
    cout << ans << endl;
    return 0;
}

拓展部分不想看的可以不用看，下面将讲述如果数据范围再小一些如何模拟：

我们可以用一个vector来记录已经模拟的部分的饭的种类。用void check(vector already)来进行模拟。

如果已经模拟了 w w w顿饭了，那么这就是一个合法的模拟，直接 a n s + + ans++ ans++即可。否则就在所有未用到的饭中，任选一个继续模拟。

下面代码只能在更下的数据下通过，可通过版本的代码请移步“AC代码”

#include 
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;

int n, k, w;
int ans = 0;

void check(vector already) {  // 已经模拟过的饭是already
    if (already.size() == w) {  // 如果已经模拟了w顿饭
        ans++;  // 可行方案数+1
        return;
    }
    bool cannot[k] = {0};  // 不可以再使用的饭(已经吃过的饭(不可再出现)将会被标记为true)
    for (int t : already) {  // 已经吃过的饭
        // assert(t < k);
        cannot[t] = true;  // 不能再吃了
    }
    for (int i = 0; i < k; i++) {  // 枚举每一种饭
        if (!cannot[i]) {  // 还没吃过
            vector newVector = already;
            newVector.push_back(i);  // 这顿饭吃i
            check(newVector);  // 继续模拟
        }
    }
}

int main() {
    cin >> n >> k >> w;
    // assert(n >= w);
    w *= 3;
    if (k < w) {
        puts("0");
        return 0;
    }

    check({});  // 从0开始模拟

    cout << ans << endl;
    return 0;
}

如果题目要求输出每种可行的方案数，那么就可以使用上述代码了。

每周提前更新菁英班周赛题解，点关注，不迷路

原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/124850901