A(模拟)B(模拟)C(位运算)D(贪心)E(模拟)F(Z函数)
背景
语言艺术
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函数
我们对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;
}