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

活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 构造C的歪

答案为 。
注意输出的数不能小于 ，所以构造正数。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    int a, b;
    cin >> a >> b;
    cout << max(a, b) + abs(b - a);
    return 0;
}

中等题 查找两个字符串a,b中的最长公共子串

数据量较小，暴力枚举即可通过。

1. 枚举子串长度。
2. 枚举子串在 中的位置。
3. 枚举子串在 中的位置。
4. 比较两个子串，如果两个子串相等且子串长度大于目前得到的最长子串长度，更新答案。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    string s, t;
    cin >> s >> t;
    if (t.length() < s.length()) swap(s, t);
    int n = s.length(), m = t.length();
    int maxl = 0;
    string ans;
    for (int l = 1; l <= min(n, m); l++) {
        for (int i = 0; i + l - 1 < n; i++) {
            for (int j = 0; j + l - 1 < m; j++) {
                if (s.substr(i, l) == t.substr(j, l) && l > maxl) {
                    maxl = l;
                    ans = s.substr(i, l);
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

困难题 气球谜题

设 为将前 个气球全部涂成颜色 所需的花费。
设三种颜色按 排列，颜色的分界点左侧分别为 ，则花费为 。 显然分别枚举 会超时，可以预处理出前 个位置里最小的 。
然后枚举 ，当前排列的答案为 。
再枚举三种颜色的气球排列，分别对 种排列取最小答案。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1), t(n + 1);
    string s;
    cin >> s;
    s = ' ' + s;
    for (int i = 1; i <= n; i++)
        cin >> t[i];
    ll minans = 1e18;
    for (int i = 1; i <= n; i++)
        a[i] = s[i] - '0';
    vector<array<ll, 3>> pre(n + 1);
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < 3; j++)
            pre[i][j] = pre[i-1][j] + (a[i] != j ? t[i] : 0);
    array<int, 3> per = {0, 1, 2};
    //pre[n][2] - pre[j - 1][2] + pre[j][1] - pre[i - 1][0] + pre[i][0] - pre[0][0]
    do {
        vector<ll> mn(n + 1);
        mn[1] = pre[1][per[0]] - pre[1][per[1]];
        for (int i = 2; i <= n; i++) 
            mn[i] = min(mn[i - 1], pre[i][per[0]] - pre[i][per[1]]);
        for(int i = 0; i <= n; i++)
            minans = min(minans, pre[n][per[2]] - pre[i][per[2]] + pre[i][per[1]] + mn[i]);
    } while (next_permutation(per.begin(), per.end()));
    cout << minans << '\n';
    return 0;
}