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

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

简单题 字符串字符匹配

开一个 set 包含 字符串中的所有字符，遍历 中字符时检查字符是否在 set 中。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s, t;
    cin >> s >> t;
    set<char> st(t.begin(), t.end());
    for (auto it : s)
        if (!st.count(it)) {
            cout << "false\n";
            return 0;
        }
    cout << "true\n";
    return 0;
}

中等题 小红的区间构造

先检查 内是否有 个数为 的倍数。
如果不满足，则平移区间至 ，这个区间内 的倍数的数字个数不少于 区间，再次检查。
都不满足则输出 。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int n, k, x;
    cin >> n >> k >> x;
    int l = 1, r = k;
    if (r / x == n) {
        cout << l << " " << r << "\n";
        return 0;
    }
    l = x, r = x + k - 1;
    if (r / x == n) {
        cout << l << " " << r << "\n";
        return 0;
    }
    cout << -1;
    return 0;
}

困难题 最长公共子序列(一)

动态规划。
设 为 中只包含前 个字符， 中只包含前 个字符的最长公共子序列长度。

1. 如果 ，则 。
2. 否则，则 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    s = ' ' + s;
    t = ' ' + t;
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (s[i] == t[j])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    cout << dp[n][m] << '\n';
    return 0;
}