牛客周赛 Round 56 AK

背景

语言艺术

A题：面包店故事

题意

一块面包要x元，加培根要y元，有n元，问能否买到加培根的面包

思路

大水题，gpt秒了

代码

#include <bits/stdc++.h>
using namespace std;
int main() {int x, y, n; cin >> x >> y >> n;if (n >= x + y) cout << "YES";else cout << "NO";return 0;
}

B题： 放课后故事 

题意

小S要折纸飞机，折一只需要k张纸，有n名同学，每名同学会贡献ai张纸，放学后有m个同学留下一起玩，问最多有多少个人拿到纸飞机

思路

大水题，gpt秒了

注：还有他自己

代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {int n, m, k; cin >> n >> m >> k;LL sum = 0;for (int i = 1; i <= n; i ++ ) {int x; cin >> x;sum += x;}cout << min(sum / k, (LL)m + 1) << endl;return 0;
}

C题：异或故事 

题意

给定一个[1,1e9]范围内的整数a，要求在同范围内找出b和c，使得两者的异或值为a

思路

我们将a的每一位拆开来给b和c，在最后如果c为0的情况下，由于异或的缘故，我们可以再在a里面找一个位为0的地方给b和c同时赋值

代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {int tt; cin >> tt;while (tt -- ) {int a; cin >> a;int b = 0, c = 0;int turn = 1;for (int i = 0; i < 31; i ++ ) {if (a >> i & 1) {if (turn) b |= (1ll << i);else c |= (1ll << i);turn ^= 1;}}if (c == 0) {for (int i = 0; i < 31; i ++ ) {if (!(a >> i & 1)) {b |= (1ll << i), c |= (1ll << i);break;}}}cout << b << ' ' << c << endl;}return 0;
}

D题：构造故事 

题意

给定若干个火柴棍，要求构造一个周长最大的三角形

思路

先sort一遍长度，并且一定是连着的三个拿来构造

首先是两边之和大于第三边，两边之差小于第三边

所以我们选连着的三个可以尽可能满足是三角形的条件

其次，如果不是连着的话，如果能构造，那么还可以继续增大第二大的边，然后发现还可以增大第三大的边，达到周长最大

代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {int tt; cin >> tt;while (tt -- ) {int n; cin >> n;map<int, int> cnt;vector<int> a(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i];sort(a.begin() + 1, a.end());LL ans = -1;for (int i = 1; i <= n - 2; i ++ ) {if (a[i] + a[i + 1] > a[i + 2] && a[i + 1] - a[i] < a[i + 2]) {ans = max(ans, (LL)a[i] + a[i + 1] + a[i + 2]);}}cout << ans << endl;}return 0;
}

E题：约会故事 

题意

约会很麻烦，自己看题目qwq

思路

大模拟，

最先考虑的肯定是转化时间，最简单的思路一定是全部转化为分钟

其次，注意给定的快乐时间，题目中没有说一定是在同一天，所以可能出现快乐开始时间大于结束时间的情况，这时候要考虑到第二天。

代码

#include <iostream>
#include <map>
using namespace std;
using LL = long long;
int turn(string s) {int res = 0;res += ((s[0] - '0') * 10 + (s[1] - '0')) * 60 + (s[3] - '0') * 10 + s[4] - '0';return res;
}
int happy[1500];
int main() {int n, m; cin >> n >> m;// 0 ~ 119;for (int i = 0; i < n; i ++ ) {string st, ed;cin >> st >> ed;int s = turn(st), t = turn(ed);if (s == t) happy[0] += 100000;if (s <= t) happy[s] += 1, happy[t + 1] -= 1;else {happy[s] += 1, happy[0] += 1, happy[t + 1] -= 1;}}map<string, bool> like;for (int i = 0; i < m; i ++ ) {string s; cin >> s;like[s] = true;}for (int i = 1; i < 1500; i ++ ) happy[i] += happy[i - 1];int q; cin >> q;while (q -- ) {string s; cin >> s;string st, ed; cin >> st >> ed;string t; cin >> t;int query = turn(s);if (!(query >= 0 && query <= 119 && happy[query])) {cout << "Loser xqq" << endl;continue;}if (turn(st) > turn(ed) || !like[t]) {cout << "Joker xqq" << endl;continue;}cout << "Winner xqq" << endl;}return 0;
}

F题：不是烤串故事 

题意

选定最小的翻转长度来翻转字符串，使得lcp最大 

思路

Z函数

不理解的看洛谷这道题【模板】扩展 KMP/exKMP（Z 函数） - 洛谷

我们对s进行翻转做一遍z函数，这样就可以知道翻转后与前面匹配的长度了，然后如果翻转k个长度，然后又和前面k个刚好一样，还要考虑之后没翻转匹配的情况ok[i]

代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {int tt; cin >> tt;while (tt -- ) {int n; cin >> n;string s, t; cin >> s >> t;vector<int> ok(n + 2);int cur = 0;for (int i = n; i >= 1; i -- ) {if (s[i - 1] == t[i - 1]) cur += 1;else cur = 0;ok[i] = cur;}reverse(s.begin(), s.end());s = ' ' + s, t = ' ' + t;vector<int> z(n + 1);z[1] = n;for (int i = 2, l, r = 0; i <= n; i ++ ) {if (i <= r) z[i] = min(r - i + 1, z[i - l + 1]);while (t[1 + z[i]] == t[i + z[i]]) z[i] += 1;if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1; }vector<int> p(n + 1);for (int i = 1, l, r = 0; i <= n; i ++ ) {if (i <= r) p[i] = min(z[i - l + 1], r - i + 1);while (i + p[i] <= n && 1 + p[i] <= n && s[i + p[i]] == t[1 + p[i]]) p[i] += 1;if (i + p[i] - 1 > r) l = i, r = i + p[i] - 1;}int ans = 0, pos = 1;for (int i = 1; i <= n; i ++ ) {int cur = p[n - i + 1];if (cur == i) {cur += ok[p[n - i + 1] + 1];}if (cur > ans) {ans = cur, pos = i;}}cout << ans << ' ' << pos << endl;}return 0;
}