Solution from problem setter.
语法场
A. Ocean睡大觉
题意
给定一个时间段，去掉这个时间段后，给定一个结束时刻 \(E\)，确定最大的开始时刻 \(S\)，使 \(S\) 到 \(E\) 这段时间的时长至少为 \(8\) 小时。
开始时刻 \(S\) 不能超过给定时间段的开始时间。
思路
直接模拟。
因为题面给的是小时和分钟，那么如果我们将其转化为分钟，显然这就转化为数轴上的问题了（比如说，\(3:40 \rightarrow 220\)）。
那么，你可以画个图，把边界情况都列出来，然后问题自然就迎刃而解了。
当然，题面是有坑的。如果你仔细看题了，不难发现，最后答案是要和比赛开始时间取一个最小值的，不然有可能出现只需睡一个阶段的情况，从而刚好挂掉 \(1\) 个点。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int hs, ms, he, me, ht, mt;
cin >> hs >> ms >> he >> me >> ht >> mt;
int len = (he * 60 + me) - (hs * 60 + ms), ed = (ht * 60) + mt;
int time = min(hs * 60 + ms, ed - len - 8 * 60);
if(time < 0) cout << "ipmama" << '\n';
else cout << "sleep" << '\n' << (time / 60) << ' ' << (time % 60) << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
}睡了吗，如睡
B. Ocean不是OP
题意
对于 \(n\) 个怪，在 \(a\) 秒内连续两次使用技能后，技能会锁定 \(b\) 秒。判断能否对所有怪使用技能。
思路
显然，因为使用技能的时间是固定的，那么我们直接模拟就好了。
我们可以把使用技能的时间都存到数组里，那么每次我们只需比较 当前时间和上一次使用技能的时间 的差值就好了。
我们记这个差值为 \(d\)。
显然，题面中有一个类似于"锁定"的状态，如果状态是锁定的，并且 \(d \leq b\)，那么这个时候技能就使用不了了，我们直接判定答案就好。
对于状态的设定，我们只要判断 \(d \leq a\) 是否满足就好了，如果满足，那么我们就可以标记锁定了，否则，我们就取消标记锁定。
如上，解毕。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, a, b;
cin >> n >> a >> b;
vector<int> x(n + 1);
for(int i=1;i<=n;i++) cin >> x[i];
bool f = true, lock = false;
for(int i=2;i<=n;i++) {
if(lock && x[i] <= x[i - 1] + b) f = false;
lock = x[i] <= x[i - 1] + a;
}
cout << (f ? "tilennnb\n" : "wasted\n");
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
}OP
C. Ocean不是铁P
题意
怪物最初有 \(h\) 血量，定义技能为：
\(n\) 段伤害，每段伤害扣除怪物的血量一定值；
具有初始值 \(x\)，该值为默认伤害；
若怪物血量低于原血量的 \(50\%\)，那么伤害变为初始值的 \(1.5\) 倍并向上取整
输出可以让怪物在释放一次技能后被击杀的最小初始伤害 \(x\)。
思路
Part1. 二分
显然，数据范围大到无法暴力扫答案。
我们进行下面的观察：
当初始伤害越大，最后需要使用的段数就会减小，否则就会增大，且增大到一定值后就不能一击必杀了。
可以发现，上面的关系满足单调性，即 需要使用的段数随 \(x\) 递增而递减。
因而，我们考虑对 \(x\) 二分，即二分答案。
如果没有学过二分答案，你可以先完成 oj 的对应题单再来看这题。
你可以通过画图来加深对其的理解。
Part2. check
首先，我们需要注意到题目中的 "低于 \(50\%\)"。
我们可以将答案分成两部分计算，也就是先算普通攻击，再算暴击。我们将两种攻击需要的段数加起来，和 \(n\) 比较即可。
下面给出一个计算流程，供参考（\(\lceil x \rceil\) 表示向上取整）：
计算普通攻击需要的段数 \(\displaystyle cnt1 = \lceil \frac{\frac{h}{2} + 1}{x} \rceil\)；
计算还剩下多少血量 \(left = cnt1 \cdot x\)；
计算暴击需要的段数 \(\displaystyle cnt2 = \lceil \frac{left}{\lceil{1.5x}\rceil} \rceil\)。
至于第一个式子为什么要 \(+1\)，因为我们需要低于 \(50\%\) 后才能使用暴击，所以我们的普通攻击一定要至少把怪物血量减少到 \(50\% \cdot h - 1\)。
注意检查答案的时候的边界问题，以及取整的问题。
当然，请注意，本题卡 \(int\)。
时间复杂度：\(O(\log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int h, n;
cin >> h >> n;
auto check = [&](int x){
int cnt1 = (h / 2 + 1 + (x - 1)) / x,
left = h - cnt1 * x,
kick = (x * 3 + 1) / 2,
cnt2 = (left + (kick - 1)) / kick;
return cnt1 + cnt2 <= n;
};
int l = 1, r = h, mid;
while(l < r){
mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << l << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
}铁P
D. Ocean的Minecraft之旅
题意
给定 \(n + 1\) 个不同的三维坐标点，从 \(0\) 开始编号。第 \(0\) 个点为家 \((0, 80, 0)\)，剩下 \(n\) 个点会给出。
在半径 \(r\) 给定的条件下，遍历每个点为球心，从第 \(1 - n\) 个点中找出位于球内和球上的点的个数（不包含球心），并输出最大值对应的编号最小的点的编号，以及这个最大值。
思路
看懂题就简单了，我们直接暴力检查答案，然后更新结果即可。
具体来说，我们枚举每一个点作为球心，然后暴力检查，统计点数。
当然，在检查 \(\sqrt{d} \leq r\) 的时候，我们不妨两边平方，变成 \(d \leq r ^ 2\)，这样可以避免根号运算的精度问题（看到好几个被卡掉了）。
其余就是对边界情况的处理了。
当然，这题也卡 \(int\)，但好心的出题人并没有想卡掉 \(long\ long\)。
但好心的出题人不小心把 \(java\) 做法的 \(O(n^2 log n)\) 卡掉了，属实意料之外。
时间复杂度：\(O(n ^ 2)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, r;
cin >> n >> r;
vector<array<int, 3>> p(n + 1);
for(int i=1;i<=n;i++) cin >> p[i][0] >> p[i][1] >> p[i][2];
array<int, 3> home = {0, 80, 0};
auto check = [&](array<int, 3> o, array<int, 3> a){
return (a[0] - o[0]) * (a[0] - o[0]) + (a[1] - o[1]) * (a[1] - o[1]) + (a[2] - o[2]) * (a[2] - o[2]) <= r * r;
};
int at = 0, ans = 0;
for(int i=1;i<=n;i++){
if(check(home, p[i])) ans ++;
}
for(int i=1;i<=n;i++){
int cnt = 0;
for(int j=1;j<=n;j++){
if(i == j) continue;
if(check(p[i], p[j])) cnt ++;
}
if(cnt > ans) at = i, ans = cnt;
}
cout << at << ' ' << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
}McP
E. Ocean与Hello World
题意
给定分别包含了 \(n, m\) 个单词的两组单词，求出所有可能的组合（保证左边的单词一定从左边那组单词里取，右边同理）中，在不区分大小写的条件下，不为 \(Hello\ World\) 的方案数。
思路
答案就是 方案总数 \(-\) 组合为 \(Hello\ World\) 的方案数。
那么，我们统计左边为 \(Hello\) 的取法个数 \(a\)，右边为 \(World\) 的取法个数 \(b\)，答案就是 \(n \cdot m - a \cdot b\)。
至于不区分大小写，你可以直接写一个函数判断，又或者调用自带的函数（具体怎么使用自行百度）。
时间复杂度：\(O(单词总长度)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, m;
cin >> n >> m;
int cnt1 = 0, cnt2 = 0;
string first = "hello", second = "world";
for(int i=1;i<=n;i++){
string s;
cin >> s;
//转换为小写 func：转换（开始地址，结束地址，放结果的开始地址，操作）
transform(s.begin(), s.end(), s.begin(), ::tolower);
if(s == first) cnt1 ++;
}
for(int i=1;i<=m;i++){
string s;
cin >> s;
transform(s.begin(), s.end(), s.begin(), ::tolower);
if(s == second) cnt2 ++;
}
cout << (n * m - cnt1 * cnt2) << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
}至少不是输出 \(hello\ world\) （（
F. Ocean的自白书
题意
输出 \(ocean\)。
思路
不会写这题的请自裁（x
怎么真的有人挂了啊，我哭死。
时间复杂度：\(O(1)?\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
cout << "ocean" << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
}别大写别大写（（
G. Ocean说这是一道博弈，我也不知道是不是
背景
题目来自 Codeforces Round 884 (Div. 1 + Div. 2) A题，难度 \(800\)。
题意
给定两个人之间的博弈：每个人可以选择拿走 \(a\) 或 \(b\) 个原石。
输出后手有必胜策略的原石的总数。
思路1
如果先手拿走 \(x\) 个石头后，后手都能拿走 \(n - x\) 个石头，那么后手必胜。
那么，\(n = a + b\) 是一定正确的，因为对方拿掉 \(a\) 或者 \(b\) 后，我都可以拿掉对应的 \(b\) 或者 \(a\)，使原石被用完，从而先手无法操作。
当然，输出 \(a + b\) 的任意整数倍都是可以的，因为每一轮都是后手有必胜策略。
思路2
我们可以直接让先手一开始就无法操作，那么如果最小值是大于 \(1\) 的，我们直接输出 \(n = 1\)，即可达到目的。
否则，我们可以输出 \(b + 1\)，这和思路 \(1\) 是一样的。
思路3
同思路2，区别是，当 \(a = 1\) 的时候，我们再做一个分类讨论：
\(b \geq 3\)，那么输出 \(n = 2\)，这样可以让先手只能拿 \(1\)，从而后手再拿 \(1\) 之后，刚好拿完石头；
\(b = 2\)，那么输出 \(n = 1 + 2 = 3\)，这和思路 \(1\) 是一样的。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int a, b;
cin >> a >> b;
cout << a + b << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t --) solve();
}A + B Problem
H. Ocean与奇怪的数列
题意
定义数组 \(a\) 前三项为 \(6, 1, 6\)，从第四项开始，每一项都是前三项分别乘上系数后相加，然后对 \(998244353\) 取模。
关于系数，\(a_i = 61 \times a_{i - 1} + 11 \times a_{i - 2} + 16 \times a_{i - 3}\)。
回答 \(q\) 个询问，每次询问给定一个下标，输出下标对应的数。
思路
注意数据范围，我们不可以对每一个询问都计算答案，因而我们考虑预处理。
我们先预处理好整个数组，然后回答询问即可。
注意，因为取模的值是 \(998244353\)，乘上一个十位数是一定超过 \(int\) 范围的，所以记得开 \(long\ long\)。
至于推导，如果会取模的话，把式子直接套进去就好了。
但我都把取模式子放在最后了，你不是可以直接改一下字母套进来么（x
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10, mod = 998244353;
int a[N];
void init() {
a[1] = 6, a[2] = 1, a[3] = 6;
for(int i=4;i<=2e5;i++){
a[i] = (61 * a[i - 1] % mod + 11 * a[i - 2] % mod + 16 * a[i - 3] % mod) % mod;
}
}
void solve() {
int q;
cin >> q;
while(q --){
int i;
cin >> i;
cout << a[i] << '\n';
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
init();
solve();
}斐波那契plus
I. Ocean与"大模拟"
背景
来自 HNOI 2005。
题意
设计一个程序完成题面所指的算法。
太模拟了，建议看原题自己阅读理解（
思路
本题不详细解释，建议你可以留着，等到之后学了 \(stl\) 之后来补题。
一道逻辑很清楚但是不好写的 模拟题。
我们很明显能发现，不可以暴力，会寄，想想有序性，不难发现可以用 堆 来维护。
我们需要存一下当前某一页的状态，方便找空页，我们可以用 \(\mathtt{Map}\)。
模拟即可
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, m;
cin >> n >> m;
map<int, pair<int, int>> data;
set<array<int, 3>> least; //cnt, time, query
int ans = 0;
for (int i = 0; i < m; i++) {
int query;
cin >> query;
if(data.count(query)){
auto [cnt, time] = data[query];
least.erase({cnt, time, query});
least.insert({cnt + 1, time, query});
data[query] = {cnt + 1, time};
ans ++;
}else if(data.size() < n){
data[query] = {1, i};
least.insert({1, i, query});
}else{
data.erase((*least.begin())[2]);
least.erase(least.begin());
data[query] = {1, i};
least.insert({1, i, query});
}
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
}如果用 C 写估计会很头大，但你正式打比赛的时候难道写纯 C 吗