雅礼2023.12.20习题课有哪些重点内容讲解？
摘要：雅礼 (2023.12.20) 习题课记录 前言 Always CF，Never AT。 又双是 CF 题，只能说“水”，AK 了。 水题（只放代码） B - Two Vessels（CF1872A) 有分别装有 (a, b) 单位
雅礼 \(2023.12.20\) 习题课记录
前言
Always CF，Never AT。
又双是 CF 题，只能说“水”，AK 了。
水题（只放代码）
B - Two Vessels（CF1872A)
有分别装有 \(a, b\) 单位水的两个杯子，容量无限大。现在有一个勺子，容量为 \(c\)，每次可以从一个杯子里舀一勺不超过 \(c\) 单位的水（\(c\) 可以不是整数），放入另一个杯子中。请问最少需要多少次操作才能使两个杯子里的水量相同。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
using ll = long long;
#define mtest for (cin >> t; t; -- t)
const int kMaxN = 5e4 + 50, kMaxM = 1.8e5 + 18, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;
ll a, b, c;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
mtest {
cin >> a >> b >> c;
ll ans = 0;
if (a < b) {
swap(a, b);
}
for (; a > b; ++ ans) {
a -= c, b += c;
}
cout << ans << '\n';
}
return 0;
}
高级水题 & 低级正常题
C - The Corridor or There and Back Again（CF1872B)
有若干个房间排成一行，其中有 \(n\) 个房间有陷阱，对于这 \(n\) 个房间，它们有两个属性：\(d_i\) 和 \(s_i\)，分别代表标号和陷阱形成的时间，即若你第 \(t\) 秒第一次到达 \(i\) 号房间，\(t+s_i\) 秒时陷阱就会在此房间形成，此后你无法通过此房间。每秒你可以走到与当前房间标号相邻的房间。你需要从 \(1\) 号房间走到 \(k\) 号房间，并且再从 \(k\) 号房间走回 \(1\) 号房间。求 \(k\) 最大是多少。
我们可以发现，当碰到机关时，你最多可以往后走 \((s_i - 1) \div 2\) 个房间了。所以我们的答案就是 \(\min_{i = 1}^{n} d_i + (s_i - 1) \div 2\)。