牛客春招刷题训练营-2025.4.8题解
活动地址： 牛客春招刷题训练营 - 编程打卡活动
简单题 字符串字符匹配
开一个 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;
}
困难题 最长公共子序列(一)
动态规划。
设 为
中只包含前
个字符，
中只包含前
个字符的最长公共子序列长度。
- 如果
，则
。
- 否则，则
。
#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;
}
投递百度等公司6个岗位 >
查看17道真题和解析