牛客春招刷题训练营-2025.5.12题解

简单题小红的魔法药剂

记 $red_i,blue_i$ 为获得第 $i$ 种红色、蓝色版本魔法药剂的花费。
红色药剂只能直接购买： $red_i=a_i$ 。
蓝色药剂需要合成： $blue_i=a_{b_i}+a_{c_i}$ 。
答案 $ans=\sum_{i=1}^{n}\min(red_i,blue_i)$ 。
时间复杂度 $\mathcal{O}(n)$ 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> red(n + 1), blue(n + 1);
    for (int i = 1; i <= n; i++)cin >> red[i];
    for (int i = 1; i <= n; i++) {
        int b, c;
        cin >> b >> c;
        blue[i] = red[b] + red[c];
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++)
        ans += min(red[i], blue[i]);
    cout << ans << '\n';
    return 0;
}

中等题游游的字母翻倍

$q$ 不算大，且最终字符串不超过 $2\times 10^6$ ，所以能直接模拟。
每次模拟时开辅助字符串 $s_2$ ，遍历 $s$ 时如果 $i∈[l,r]$ 则给 $s_2$ 添加 $2$ 个 $s_i$ ，否则添加 $1$ 个 $s_i$ ，每一轮结束后将 $s_2$ 赋值给 $s$ 。
时间复杂度 $\mathcal{O}(q\times N)$ ， $N$ 可看作 $10^6$ 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, q;
    cin >> n >> q;
    string s1, s2;
    cin >> s1;
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        s2 = "";
        for (int i = 0; i < s1.length(); i++) {
            if (l <= i && i <= r) {
                s2 += s1[i];
                s2 += s1[i];
            } else s2 += s1[i];
        }
        s1 = s2;
    }
    cout << s1;
    return 0;
}

考虑到 $x$ 不会很大，最大值只能取到 $13$ ，因为 $13!=6,227,020,800$ ，所以只需暴力枚举 $x$ ，算出当前的 $x$ 下使原式最小的 $y$ 。
当 $x=1$ 时，发现原式恒等于 $n$ 。
当 $x\neq1$ 时，我们将原式变换一下，即最小化 $|y-\frac{n}{x!-1}|$ 。
记 $f(y)=y-\frac{n}{x!-1}$ 。
$f(y)$ 是随 $y$ 单调递增的，而我们知道一个使得 $f(y) \leq 0$ 最大的 $y$ ，等于 $\lfloor\frac{n}{x!-1}\rfloor$ 。
所以使得 $|f(y)|$ 最小的 $y$ 的取值只能是 $y_1=\lfloor\frac{n}{x!-1}\rfloor$ 或 $y_2=\lfloor\frac{n}{x!-1}\rfloor+1$ 。
如果计算出的 $y_1$ 或 $y_2$ 不为 $2$ ，则将 $y_1$ 或 $y_2$ 代入原式，如果计算值比当前存储的原式最小值小，则更新 $x,y$ 的答案且更新原式最小值。
时间复杂度 $\mathcal{O}(1)$ ，其实可以看作一个很大的常数。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll frac(int n) {
    ll res = 1;
    for (int i = 2; i <= n; i++)res *= i;
    return res;
}
ll calc(int x, int y, int n) {
    return abs(frac(x) * y - y - n);
}
int main() {
    int n;
    cin >> n;
    int ansx = 1, ansy = 1;
    ll minabs = n;
    for (int x = 3; x <= 13; x++) {
        int y = n / (frac(x) - 1);
        if (y != 2) {
            ll nowabs = calc(x, y, n);
            if (nowabs < minabs) {
                ansx = x;
                ansy = y;
                minabs = nowabs;
            }
        }
        if (y + 1 != 2) {
            ll nowabs = calc(x, y + 1, n);
            if (nowabs < minabs) {
                ansx = x;
                ansy = y + 1;
                minabs = nowabs;
            }
        }
    }
    cout << ansx << ' ' << ansy << '\n';
    return 0;
}