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})\)。