牛客小白月赛83 解题报告

题目链接：

https://ac.nowcoder.com/acm/contest/72041#question

A题

解题思路

签到

代码

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

int main() {
    int a, b, c, d, e;
    cin >> a >> b >> c >> d >> e;
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    if (a * A + b * B + c * C - d * D > e)
        cout << "YES\n";
    else
        cout << "NO\n";
    
    return 0;
}

B题

解题思路

贪心，很显然，我们应该尽可能将更大的魔法1用于更大的魔法2。
所以先将两个数组从大到小排序。
一个小细节是：如果当前直接使用魔法2就能击败，那么就直接使用魔法2，没必要先使用魔法1。以及如果当前魔法1是1，那么也没必要使用。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 10;
int a[maxn], b[maxn];

void solve() {
    int n, m, x;
    cin >> n >> m >> x;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }

    sort(a + 1, a + 1 + n, greater<int>());
    sort(b + 1, b + 1 + n, greater<int>());

    int cnt = 0, i = 1, j = 1;
    while(j <= n) {
        int f1 = a[i] * b[j];
        int f2 = b[j];
        if (f1 > f2 && x > f2) {
            cnt += 2;
            x -= f1;
            i++;
            j++;
        } else {
            cnt++;
            x -= f2;
            j++;
        }
        if (x <= 0)
            break;
    }
    if (x <= 0)
        cout << cnt << "\n";
    else
        cout << -1 << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(18);

    solve();

    return 0;
}

C题

解题思路

看见题面是Minecraft MITE直接肃然起敬。
根据题意很容易分析出，只有三种方案可以做出铜镐：
1、16个铜粒。
2、12个铜粒+4个银粒。
3、12个铜粒+4个金粒。
将三种方案的概率相加即可。
公式如下：

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 10;
//double PJIN[20], PYIN[20], PTONG[20];

double pow(double b, int e) {
    if (e == 0)return 1;
    if (e == 1)return b;
    double res = pow(b, e / 2);
    if (e % 2 == 0) {
        return res * res;
    }
    else {
        return res * res * b;
    }
}
double Power(double base, int exponent) {
    if (exponent == 0)return 1;
    if (exponent == 1)return base;
    if (exponent < 0) {
        return pow(1 / base, -exponent);
    }
    else {
        return pow(base, exponent);
    }

}

void solve() {
    double a, b, c;
    cin >> a >> b >> c;
    double pTong = a / 16;
    double pYin = b / 16;
    double pJin = c / 16;
    double tongGao = Power(pTong, 12);
    // 方案一：4铜粒（工作台） + 12铜粒（一个铜稿子）
    double f1 = Power(pTong, 4) * tongGao;
    // 方案二：4银粒（工作台) + 12
    double f2 = Power(pYin, 4) * tongGao * 1820;    // C(16, 4) = 1820
    // 方案三：4金粒 + 12
    double f3 = Power(pJin, 4) * tongGao * 1820;
    cout << (f1 + f2 + f3) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(18);

    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

D题

解题思路

n <= 500，所以O(n^3)也是能过的。
考虑找出左端点为ch1，右端点为ch2，长度为k的子序列数量，假设有si == ch1，sj == ch2，那么[i, j]这段子串对于答案的贡献为C(j - i - 1, k - 2)。
因为这相当于在固定了si和sj的情况下，在中间j - i - 1个字符（[i + 1, j - 1]这个子串）中选择k - 2个字符。
我们可以考虑先预处理出答案，暴力枚举，第一层循环枚举左端点，第二层循环枚举右端点，第三层循环枚举子序列长度，统计出数量。对于组合数我们可以先用杨辉三角预处理出来。
详见代码和注释。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 5e2 + 10;
const int INF = 0x3fffffff;
const ll mod = 998244353;
ll c[maxn][maxn];
string s;
int n;
ll ans[300][maxn][maxn];     // 预处理答案，ans[ch1][ch2][k]代表在字符串s中左端点为ch1，右端点为ch2，长度为k的子序列的数量

void initC() {
    for (int i = 0; i <= n; i++) {
        c[i][i] = 1;
        c[i][0] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
        }
    }
}

void init() {
    // 用杨辉三角预处理组合数
    initC();

    // 预处理
    for (int i = 0; i < n; i++) {   // 枚举左端点
        for (int j = i + 1; j < n; j++) {   // 枚举右端点
            for (int k = 2; k <= j - i + 1; k++) {  // 枚举序列长度
                char ch1 = s[i];
                char ch2 = s[j];
                // 当左端点为i右端点为j，能贡献出C(j - i - 1, k - 2)个长度为k的左端点si，左端点sj的子序列
                ans[ch1][ch2][k] += c[j - i - 1][k - 2];    // 将贡献数量加到对应的答案记录
                ans[ch1][ch2][k] %= mod;
            }
        }
    }
}

void solve() {
    cin >> n;
    cin >> s;
    // 预处理
    init();
    
    // 询问查询
    int m;
    cin >> m;
    while (m--) {
        char ch1, ch2;
        cin >> ch1 >> ch2;
        int len;
        cin >> len;
        cout << ans[ch1][ch2][len] << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(18);

    solve();
    return 0;
}