雅礼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\)。
#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 = 110, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;
ll n, d, s;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
mtest {
cin >> n;
ll ans = kLInf;
for (int i = 1; i <= n; ++ i) {
cin >> d >> s;
ans = min(ans, d + (s - 1) / 2);
}
cout << ans << '\n';
}
return 0;
}
D - Non-coprime Split（CF1872C）
给出 \(l,r\)，构造一组 \(a,b\) 使满足以下条件：
\(l \le a+b \le r\)
\(\gcd(a,b) \neq 1\)
若有多组解，则输出任意一组。
我们可以发现 \(l \sim r\) 区间内，如果一个数 \(n\) 不是质数。设它的最小因数为 \(x\)，那么 \(\gcd(x,\ n - x) = 1\)。所以我们枚举 \(l \sim r\)，如果 \(i\) 不是质数，那么就输出 \(i\) 的最小因数和 \(i - (i\) 的最小因数\()\)。如果 \(l \sim r\) 区间内没有满足条件的 \(i\)，输出 \(-1\)（无解）。时间复杂度 \(O(t·(r - l + 1)·\sqrt{i})\)。
#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 = 110, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;
ll l, r;
ll M(ll x) { // 求最小因数
for (int i = 2; i * i <= x; ++ i) { // 枚举因数
if (!(x % i)) {
return i;
}
}
return 0;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
mtest {
cin >> l >> r;
bool f = 0;
for (int i = l; i <= r; ++ i) { // 枚举 l~r 区间
int r = M(i); // 求最小因数
if (!r) {
continue;
}
f = 1;
cout << r << ' ' << i - r << '\n';
break;
}
if (!f) {
cout << "-1\n"; // 无解
}
}
return 0;
}
G - United We Stand（CF1859A）
一共 \(t\) 组数据，每组数据给定一个长度为 \(n\) 的数组 \(a\)，将其分为两个数组，使得任意第二个数组中的数不可以整除任意第一个数组中的数。
构造题，这种题最简单。
如果 \(a\) 中所有元素相同，无解。否则，我们把 \(a\) 分割成两个数组，\(a_n\) 为第二个数组，然后把 \(a\) 数组从 \(n - 1\) 个元素从后往前遍历，如果当前数与后一个数相同，把它分给第二个数组，否则停止分割。
#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 = 110, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;
int n, a[kMaxN], ans1[kMaxN], ans2[kMaxN];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
mtest {
memset(ans2, 0, sizeof ans2);
cin >> n;
int l1 = 0, l2 = 0;
for (int i = 1; i <= n; ++ i) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
if (a[1] == a[n]) {
cout << "-1\n";
} else {
ans2[++ l2] = a[n];
for (int i = n - 1; i >= 1; -- i) {
if (a[i] == a[i + 1]) {
ans2[++ l2] = a[i];
} else {
break;
}
}
cout << n - l2 << ' ' << l2 << '\n';
for (int i = 1; i <= n - l2; ++ i) {
cout << a[i] << ' ';
}
cout << '\n';
for (int i = 1; i <= l2; ++ i) {
cout << ans2[i] << ' ';
}
cout << '\n';
}
}
return 0;
}
E - Plus Minus Permutation（CF1872D）
给定三个整数 \(n,x,y(1 \le n \le 10^9, 1 \le x, y \le n)\)，对于 \(n\) 的排列 \(p\)，有
$f(p)=(p_x+p_{2x}+p_{3x}+ \ldots +p_{\lfloor \frac{n}{x}\rfloor \cdot x}) - (p_{y} + p_{2y} + \ldots + p_{\lfloor \frac{n}{y} \rfloor \cdot y}) $。求可能的最大 \(f(p)\)。
数学题。
我们尽量在 \(p_{k_1·x}(1 \le k_1 \le \lfloor \frac{n}{x} \rfloor)\) 放大的数，\(p_{k_2·y}(1 \le k_2 \le \lfloor \frac{n}{y} \rfloor)\) 放小的数。套一些公式即可。
#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 = 110, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;
ll n, x, y;
ll lcm(ll a, ll b) {
return a / __gcd(a, b) * b;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
mtest {
cin >> n >> x >> y;
ll nx = n / x, ny = n / y;
nx -= n / lcm(x, y), ny -= n / lcm(x, y);
ll ans = (2 * n - nx + 1) * nx / 2;
ans -= (ny + 1) * ny / 2;
cout << ans << '\n';
}
return 0;
}
正常题
接下来的题才算正常题。
F - Serval and Toxel's Arrays（CF1789C）
给你一个零时刻的长度为 \(n\) 的数组 \(a_i\)。
时刻 \(i\ (1 \le i \le m)\) 的数组是在时刻 \(i-1\) 的基础上把位置 \(p_i\) 的数改成 \(v_i\) 得到的。
现在让你求出 \(\sum_{i=0}^m \sum_{j=i+1}^m f(i,j)\)，其中 \(f(i,j)\) 的值为时刻 \(i\) 和时刻 \(j\) 的数组拼起来后一共有几种数字。
我们知道对答案 \(x\) 造成贡献有两种情况：
\(a_i\) 含有 \(x\)，但 \(a_j\) 不含有 \(x\)。
\(a_i\) 和 \(a_j\) 都含有 \(x\)。
设 \(f_i\) 为 \(i\) 在第 \(f_i\) 中出现过了，可以算出它们贡献分别为 \(s_x(m - s_x + 1)\)， \(\dfrac{(s_x)^2 - s_x}{2}\)。
\(e^{i\pi}\) 年 OI 一场空，不清空数组见祖宗。
#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 = 4e5 + 40, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;
ll n, m, a[kMaxN], b[kMaxN], c[kMaxN], ans = 0;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
mtest {
ans = 0;
cin >> n >> m;
// 清空数组 清空数组 清空数组
for (int i = 1; i <= n + m; ++ i) {
c[i] = 0;
b[i] = -1;
}
// 清空数组 清空数组 清空数组
for (int i = 1; i <= n; ++ i) {
cin >> a[i];
b[a[i]] = 0;
}
for (ll i = 1, x, y; i <= m; ++ i) {
cin >> x >> y;
if (a[x] != y) {
c[a[x]] += i - b[a[x]];
b[a[x]] = -1;
b[y] = i;
}
a[x] = y;
}
for (ll i = 1; i <= n + m; ++ i) {
c[i] += (m - b[i] + 1) * (b[i] != -1);
}
for (ll i = 1; i <= n + m; ++ i) {
ans += c[i] * (m - c[i] + 1) + c[i] * (c[i] - 1) / 2;
}
cout << ans << '\n';
}
return 0;
}
A - Torn Lucky Ticket（CF1895C）
A 题放压轴，emmmmm……
给出 \(n\) 个长度最多为 \(5\) 的由 \(1\) 到 \(9\) 构成的字符串 \(s\)。求出有多少个 \((i,j)\) 满足 \(s_i + s_j\) 所形成的字符串长度为偶数，并且前半部分的数字之和等于后半部分的数字之和。
我这种做法似乎很稀奇。
我们开一个 map，下标为 pair<long long, long long>，一个存各位数字之和，一个存长度。
每次根据字符串的长度 \(l\) 分类讨论：
\(l = 1\)，只能挑选长度为 \(1\) 的。
\(l = 2\)，只能挑选长度为 \(2\) 的。
\(l = 3\)，既可以挑选长度为 \(3\) 的，又可以挑选长度为 \(1\) 的。
\(l = 4\)，既可以挑选长度为 \(4\) 的，又可以挑选长度为 \(2\) 的。
\(l = 5\)，可以挑选长度为 \(1, 3, 5\) 的。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
using ll = long long;
#define mtest for (cin >> t; t; -- t)
const int kMaxN = 2e5 + 20, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;
ll n, ans = 0;
string s[kMaxN];
map<pair<ll, ll>, ll> mp;
vector<ll> v;
void W(ll i, ll len) {
if (len == 1) {
ans += mp[{v[i - 1], 1}];
} else if (len == 2) {
ans += mp[{v[i - 1], 2}];
} else if (len == 3) {
ans += mp[{v[i - 1], 3}];
ans += mp[{v[i - 1] - 2 * (s[i].back() - '0'), 1}];
ans += mp[{v[i - 1] - 2 * (s[i].front() - '0'), 1}];
} else if (len == 4) {
ans += mp[{v[i - 1], 4}];
ans += mp[{v[i - 1] - 2 * (s[i].back() - '0'), 2}];
ans += mp[{v[i - 1] - 2 * (s[i].front() - '0'), 2}];
} else {
ans += mp[{v[i - 1], 5}];
ans += mp[{v[i - 1] - 2 * (s[i].back() - '0'), 3}];
ans += mp[{v[i - 1] - 2 * (s[i].front() - '0'), 3}];
ans += mp[{v[i - 1] - 2 * ((s[i].front() - '0') + (s[i][1] - '0')), 1}];
ans += mp[{v[i - 1] - 2 * ((s[i].back() - '0') + (s[i][3] - '0')), 1}];
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++ i) {
ll cnt = 0;
cin >> s[i];
for (int j = 0; j < s[i].size(); ++ j) {
cnt += s[i][j] - '0';
}
v.push_back(cnt);
++ mp[{cnt, s[i].size()}];
}
for (int i = 1; i <= n; ++ i) {
W(i, s[i].size());
}
cout << ans << '\n';
return 0;
}