牛客寒假训练营(一) 题解 (持续更新中)
A题
思路: 在原字符串中暴力搜索”DFS”和”dfs”,如果搜到D就将指针k(k < 3)直到搜出DFS,如果搜到d将k(k < 3)直到搜出dfs.
官方题解(dfs):
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n;
string str;
cin >> n >> str;
string s[] = {"DFS" ,"dfs"};
for (int i = 0; i < 2; i ++ ) {
int k = 0;
for (int j = 0; j < n && k < 3; j ++ ) {
if (s[i][k] == str[j]) {
k ++;
}
}
cout << (k == 3) << " \n"[i == 1];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t -- ) {
solve();
}
return 0;
}
双指针:
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n;
string s;
cin >> n >> s;
int i = 0, j = 0;
string s1 = "DFS", s2 = "dfs";
for (auto c : s) {
if (i < 3 && s1[i] == c) i ++;
if (j < 3 && s2[j] == c) j ++;
}
cout << (i == 3) << " " << (j == 3) << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t -- ) {
solve();
}
return 0;
}
M题
思路:根据题意可知每6个字母为一次循环,如果n是6的倍数,最多可循环n/6次,如果n不是6的倍数,因为从左往右循环了(n / 6)次,那么从右往左循环一定也是(n / 6).emmm…我太菜不会证明只能凭感觉写了(欢迎各位大神证明ahh).
#include "bits/stdc++.h"
using namespace std;
using i63 = long long;
void solve() {
int n;
cin >> n;
if (n % 6 == 0) cout << n / 6 << '\n';
if (n % 6 != 0) cout << n / 6 * 2 << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t -- ) {
solve();
}
return 0;
}
G题
思路:(贪心)
假设当前坤手里有m元钱,商场搞促销,满a元钱减b元(优惠券可以叠加使用).坤想买某一件商品,商品的总价为x,求x的最大值.
emm…看了一眼样例......
模拟的第一个样例 :
坤手机里有10元钱,商场发放两张优惠券:
1 : 满100减90;
2 :满30减10;
max : x = 110;
两张优惠券叠加的情况下,最高可抵100元钱 此时坤手机里还有10元钱 坤能买到的最大价值的商品一定是 100 + 10 = 110(需要满足当前优惠券的满减 - 当前优惠券叠加优惠 <= 手机钱数).
因此我们可推出:
在所有优惠券都使用的情况下 $x(max) = \sum_{i=1}^{i=n}a_i + m (a_i - sum_b[i] <= m)$
其中x所满足的区间为$[m, \sum_{i=1}^{i=n}b_i + m]$ 我们需要尽量将x往右靠
emm…再次观察公式,$x(max) = \sum_{i=1}^{i=n}a_i + m$
如果当前手机里的钱不够的时候,我们得到的答案一定不是最优解.
我们需要尽力消耗优惠券,用最大的优惠去购买商品得到的答案一定是最大值.
因此需要先把优惠券从小到大排序再去使用优惠券直到我们手中的钱无法满足当前优惠.
AC~~~
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n, m;
cin >> n >> m;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; i ++ ) {
int aa, bb;
cin >> aa >> bb;
a[i] = {aa, bb};
}
sort(a.begin(), a.end());
i64 ans = m;
i64 sum = 0;
for (auto [aa, bb] : a) {
sum += bb;
if (aa - sum <= m) {
ans = max(ans, sum + m);
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t -- ) {
solve();
}
return 0;
}
E题
思路:本题的数据范围m在$[1, 10]$之间,如果枚举三场比赛的结果那么时间复杂度最大为$pow(3, m)$,因此本次可以使用dfs
#include "bits/stdc++.h"
#define x first
#define y second
using namespace std;
using i64 = long long;
typedef pair<int, int> PII;
const int N = 15;
PII beat[N];
int n, m;
vector<int> a(N+1);
int res;
void dfs(int _x) {
if (_x == m) {
int ans = 1;
for (int i = 2; i <= n; i ++ ) {
if (a[i] > a[1]) {
ans ++;
}
}
res = min(res, ans);
return ;
}
for (int i = 0; i < 3; i ++ ) {
if (i == 0) {
a[beat[_x].x] += 3;
dfs(_x + 1);
a[beat[_x].x] -= 3;
}
else if (i == 2) {
a[beat[_x].y] += 3;
dfs(_x + 1);
a[beat[_x].y] -= 3;
}
else {
a[beat[_x].y] ++;
a[beat[_x].x] ++;
dfs(_x + 1);
a[beat[_x].y] --;
a[beat[_x].x] --;
}
}
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 0; i < m; i ++ ) {
int u, v;
cin >> u >> v;
beat[i] = {u, v};
}
res = 15;
dfs(0);
cout << res << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t -- ) {
solve();
}
return 0;
}
C题
思路:根据不满意度公式可推出$\sum_{i=1}^{i=n}d_i$ == $\sum_{i=1}^{i=n}t_i$
例如: $s1 = t1$, $s2 = t1 + t2$, $s3 = t1 + t2 + t3$.....因此我们可以使用前缀和处理前i个人的不满意度之和.
假设$S_c$表示坤坤插队后前n个人的不满意度, $S_{min}$表示工作人员合理分配使得前i个人的最低的不满意度
考虑坤坤插入在哪个人前面使得不满意度差满足$S_c - S_{min} <= m$ 其中$S_c - S_{min}$为不满意度增量
因为坤坤插入的顺序具有单调性因此我们可以考虑使用二分
假设最优解发生在坤坤插入在第x个人之后那么前n - x个人的不满意度都会增加tc
必须满足$(n - x) * tc <= m$ 那么坤坤所花费的最短时间就是$s[l] + tc$;
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
const int N = 1e6 + 10;
int n, q, tc;
i64 m;
int s[N];
void solve() {
cin >> n >> q >> tc;
for (int i = 1; i <= n; i ++ ) {
cin >> s[i];
}
sort(t + 1, t + n + 1);
for (int i = 1; i <= n; i ++ ) {
s[i] += s[i - 1]; // 预处理前i个人的前缀和
}
auto check = [&](int x) {
return (n - x) * tc <= m;
};
while (q -- ) {
cin >> m;
int l = 0, r = n;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << s[l] + tc << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
//cin >> t;
while(t -- ) {
solve();
}
return 0;
}
B题
思路: 如图:
#include "bits/stdc++.h"
#define x first
#define y second
using namespace std;
using i64 = long long;
void solve() {
int n;
cin >> n;
int _l = 2, _r = 2;
map<pair<int, int>, int> mp;
for (int i = 0; i < n; i ++ ) {
int r, c;
cin >> r >> c;
mp[{r, c}] = 1;
if (c >= 0) _r = 1;
if (c <= 0) _l = 1;
}
for (auto t : mp) {
int r = t.x.x, c = t.x.y;
if (c <= 0) continue;
if (mp.count({3 - r, c + 1}) || mp.count({3 - r, c}) || mp.count({3 - r, c - 1})) {
_r = 0;
}
}
for (auto t : mp) {
int r = t.x.x, c = t.x.y;
if (c >= 0) continue;
if (mp.count({3 - r, c + 1}) || mp.count({3 - r, c}) || mp.count({3 - r, c - 1})) {
_l = 0;
}
}
int ans = 3;
if (mp.count({2, 0})) ans --;
if (mp.count({1, -1})) ans --;
if (mp.count({2, 1})) ans --;
cout << min(ans, _l + _r) << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t -- ) {
solve();
}
return 0;
}
写的很不错!!!
哈哈,其余的题还没更新呢