2023年11月22日雅礼习题课内容有哪些？
摘要：雅礼信奥 (2023.11.22) 习题课记录 都是 CF 题，不如 AT。 A - Yarik and Array（CF1899C） dp 题，作为学 OI (3) 年的萌新 OIer，后面才想到 dp 真是太蒟蒻了，时间复杂度
雅礼信奥 \(2023.11.22\) 习题课记录
都是 CF 题，不如 AT。
A - Yarik and Array（CF1899C）
dp 题，作为学 OI \(3\) 年的萌新 OIer，后面才想到 dp 真是太蒟蒻了，时间复杂度 \(O(tn)\)。
初始 \(f_1 = 1\)，其他为 \(0\)。
状态转移方程：
\(\begin{cases} \text{if} & \text{abs}(a_{i - 1}) \bmod 2 + \text{abs}(a_i) \bmod 2 = 1 & f_i = \max(a_i,\ f_{i - 1} + a_i) \\ \text{if} & \text{abs}(a_{i - 1}) \bmod 2 + \text{abs}(a_i) \bmod 2 \neq 1 & f_i = a_i \end{cases}\)
\(\max(f_1, f_2, \cdots, f_n)\) 即为答案。
罚时 \(1\) 次。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stack>
using namespace std;
using ll = long long;
const int kMaxN = 2e5 + 20, kInf = (((1 << 30) - 1) << 1) + 1;
ll n, a[kMaxN], f[kMaxN], ans = 0;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
for (cin >> t; t; -- t) {
cin >> n;
for (int i = 1; i <= n; ++ i) {
cin >> a[i];
f[i] = 0;
}
f[1] = a[1];
ans = f[1];
for (int i = 2; i <= n; ++ i) {
if (abs(a[i - 1]) % 2 + abs(a[i]) % 2 == 1) {
f[i] = max(a[i], f[i - 1] + a[i]);
ans = max(ans, f[i]);
} else {
f[i] = a[i];
ans = max(ans, f[i]);
}
}
cout << ans << '\n';
}
return 0;
}
B - Game with Integers（CF1899A）
一眼题 + 面向样例题，\(n \bmod 3 = 0\) 输出 Second，否则 First，时间复杂度 \(O(t)\)。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stack>
using namespace std;
using ll = long long;
const int kMaxN = 2e5 + 20, kInf = (((1 << 30) - 1) << 1) + 1;
int x;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
for (cin >> t; t; -- t) {
cin >> x;
cout << (!(x % 3)? "Second" : "First") << '\n';
}
return 0;
}
C - 250 Thousand Tons of TNT（CF1899B）
枚举题。
首先，\(k\) 必定是 \(n\) 的因数，所以我们只需要枚举 \(n\) 的因数即可，时间复杂度不确定，好像是 \(O(tn\sqrt{n})\)。
罚时 \(3\) 次，因为不开 long long 见祖宗。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stack>
using namespace std;
using ll = long long;
const int kMaxN = 2e5 + 20, kInf = (((1 << 30) - 1) << 1) + 1;
ll n, a[kMaxN], b[kMaxN], idx = 0, mini = 1e18, maxa = -1e18, ans = -1e18, sum = 0;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
for (cin >> t; t; -- t) {
cin >> n;
idx = 0, ans = -1e18;
for (int i = 1; i <= n; ++ i) {
cin >> a[i];
}
for (ll i = 1; i * i <= n; ++ i) {
if (n % i) {
continue;
}
b[++ idx] = n / i;
mini = 1e18, maxa = -1e18;
for (ll j = 1; j <= n; ++ j) {
sum += a[j];
if (!(j % i)) {
mini = min(mini, sum);
maxa = max(maxa, sum);
sum = 0;
}
}
ans = max(ans, maxa - mini);
}
sum = 0;
for (ll i = 1; i <= idx; ++ i) {
mini = 1e18, maxa = -1e18;
for (ll j = 1; j <= n; ++ j) {
sum += a[j];
if (!(j % b[i])) {
mini = min(mini, sum);
maxa = max(maxa, sum);
sum = 0;
}
}
ans = max(ans, (b[i] == n? 0 : maxa - mini));
}
cout << ans << '\n';
}
return 0;
}
D - Yarik and Musical Notes（CF1899D）
成为一个合法的一对 \((i, j)\) 必须满足 \(a_i = a_j\) 或 \(a_i = 1\)，\(a_j = 2\) 或 \(a_i = 2\)，\(a_j = 1\)，所以我们建立一个哈希表 \(mp\)（一定要开 map，unoredered_map 被卡了！），如果 \(a_i = 1\)，答案加 \(mp_2\)，如果 \(a_i = 2\)，答案加 \(mp_1\)，然后每次答案加 \(mp_{a_i}\)。时间复杂度 \(O(n)\)。
罚时 \(5\) 次，因为 unoredered_map 啊啊啊啊啊！
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <unordered_map>
using namespace std;
using ll = long long;
const int kMaxN = 2e5 + 20, kInf = (((1 << 30) - 1) << 1) + 1;
ll n, a[kMaxN], ans = 0;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
for (cin >> t; t; -- t) {
unordered_map<ll, ll> mp;
ans = 0;
cin >> n;
for (int i = 1; i <= n; ++ i) {
cin >> a[i];
if (a[i] == 1) {
ans += mp[2];
}
if (a[i] == 2) {
ans += mp[1];
}
ans += mp[a[i]];
++ mp[a[i]];
}
cout << ans << '\n';
}
return 0;
}
E - Treasure Chest（CF1895A）
分类讨论题，只需稍微推一下就可以。
\(\begin{cases} \text{if} & x > y & x \\ \text{if} & x < y \text{ and } y - (k + x) \ge 0 & y \\ \text{if} & x < y \text{ and } y - (k + x) < 0 & x + k + (y - (k + x) \times 2) \end{cases}\)
当初还以为是搜索。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stack>
using namespace std;
using ll = long long;
const int kMaxN = -1, kInf = (((1 << 30) - 1) << 1) + 1;
int x, y, k;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
for (cin >> t; t; -- t) {
cin >> x >> y >> k;
if (x > y) {
cout << x << '\n';
} else {
if (y - (k + x) <= 0) {
cout << y << '\n';
} else {
cout << x + k + (y - (k + x) << 1) << '\n';
}
}
}
return 0;
}
F - Queue Sort（CF1899E）
首先，我们定义一个 \(ans\) （存最小值）和 \(cnt\)（用来记录答案）。每次把 \(ans\) 赋值为 \(10^{18}\)，\(cnt\) 赋值为 \(0\)。遍历一遍数组，\(cnt\) 记录最小值的下标。如果 \([cnt + 1, n]\) 区间内有 \(a_i < a_{i - 1}\) 的情况，输出 \(-1\)，否则输出 \(cnt - 1\)。
罚时 \(1\) 次。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stack>
using namespace std;
using ll = long long;
const int kMaxN = 2e5 + 20, kInf = (((1 << 30) - 1) << 1) + 1;
ll n, a[kMaxN], ans = 1e18, cnt = 0;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
for (cin >> t; t; -- t) {
cin >> n;
ans = 1e18, cnt = 0;
for (int i = 1; i <= n; ++ i) {
cin >> a[i];
if (a[i] < ans) {
ans = a[i];
cnt = i;
}
}
for (int i = cnt + 1; i <= n; ++ i) {
if (a[i] < a[i - 1]) {
cnt = -1;
}
}
cout << (cnt == -1? -1 : cnt - 1) << '\n';
}
return 0;
}
G - Points and Minimum Distance（CF1895B）
当初还以为是最短路，所以放在后面，结果发现 G 好简单。
将输入的数据排好序，然后遍历 \([1, n - 1]\)，每次把距离加 \(\text{abs}(a_i - a_{i + 1}) + \text{abs}(a_{i + n} - a_{i + n + 1})\)，遍历完后输出。然后我们定义两个指针 \(i, j\)，\(i = 1\)，\(j = n \times 2\)，每次 \(i\) 加 \(1\)，\(j\) 减 \(1\)，\(a_i, a_j\) 即是我们要输出的坐标。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
using ll = long long;
const int kMaxN = 2e5 + 20, kInf = (((1 << 30) - 1) << 1) + 1;
ll n, ans = 0, a[kMaxN];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
for (cin >> t; t; -- t) {
ans = 0;
cin >> n;
for (int i = 1; i <= (n << 1); ++ i) {
cin >> a[i];
}
sort(a + 1, a + (n << 1) + 1);
for (int i = 1; i <= n - 1; ++ i) {
ans += labs(a[i] - a[i + 1]) + labs(a[i + n] - a[i + n + 1]);
}
cout << ans << '\n';
for (int i = 1, j = (n << 1); i <= j; ++ i, -- j) {
cout << a[i] << ' ' << a[j] << '\n';
}
}
return 0;
}