牛客练习赛93 A-B题解

发布于 2021-12-11  455 次阅读


内容纲要

A 牛牛排队

题目大意:

牛牛希望排队通过一扇门。牛牛离门 x 米,他每走一米需要 y 分钟。由于门口有保安查健康码,牛牛需要耗费 a 分钟掏出手机,b 分钟打开健康码,c 分钟扫码过门。
他想知道,对于不同的 x,y,a,b,cx,y,a,b,cx,y,a,b,c,他需要几分钟才能通过这扇门。
一边行走,一边掏手机或者打开健康码。

题解:

签到,给自己整服了,看错题罚了三次

代码:

#include<bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin>>t;
    while(t--){
        long long x,y,a,b,c;
        cin>>x>>y>>a>>b>>c;
        long long k;
        k = max(x * y, a + b);
        printf("%lld\n", k + c);
    }
}

B 斗地主

题目大意:

牛牛一个人在打牌(他失去了牛妹),他有 m 种类型的牌,每种牌的分值是 a1,a2…a_{m}

第 0 回合时牛牛的分值为 0。每回合他都会打出一张牌,然后新的分值就是上一回合得分值加上这张牌的分值再对 k 取模 。

牛牛喜欢一个数字,当且仅当数字中含有 7 或者含有 9。请你告诉他 n 轮后他分值会是他所"喜欢"的方案数。

我们认为两种方案不同,当且仅当存在某一个回合牛牛打出的牌不同。

由于答案可能非常大,你只需要输出其对于 10^{9}+7取模的结果。

数据范围:
$$1≤n≤100,1≤m,k≤50,0≤a_{m}<k$$

题解:

最开始写了一个DFS,hhhhhhhhh.....

其实一看就超时,就算m = 2 ,当n = 100 的时候也有2^{100} 种情况= =,更何况这里m最大是50

后面问了一下是dp,才写出的dp,但是又是没交上去,考完后几分钟就ac了(早知道我就不吃面了,中间感觉凉了就去泡面了回来发现好像还能写hhhhhhh)....佛...

其实就是每一轮只依赖于上一轮的结果,然后只要按轮数去推就好了,然后就是MOD的分配律,加法和乘法都适用。直接计算下一轮中数MOD k的情况就好了。

代码:

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
long long n, m, k;
long long nums[300];
long long ls[] = {7, 17, 27, 37, 47, 9, 19, 29, 39, 49};
long long f[300][300];

int main() {
    cin >> n >> m >> k;
    for (long long i = 1; i <= m; i++) {
        scanf("%lld", &nums[i]);
    }
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (long long i = 1; i <= n; i++) {
        for (long long j = 0; j < k; j++) {
            for (long long o = 1; o <= m; o++) {
                f[i][(nums[o] + j) % k] = (f[i][(nums[o] + j) % k] + f[i - 1][j]) % MOD;
            }
        }
    }
    long long ans = 0;
    for (int i = 0; i < k; i++) {
        if (i % 10 == 7 || i % 10 == 9) {
            ans = ( ans + f[n][i] ) % MOD;
        }
    }
    printf("%lld", ans);
    return 0;
}

总结

这把打得太差了,有点玉玉。希望今天的CF和At能好点吧= =
C题听wljss大佬说是换根dp,嗯又是我没听过的。
等学会了再来补C的题解


不爱嘉然小姐十年了。十年里,爱过的每个人都像她。