雅礼 2023.12.27 习题课记录
前言
这一场罚时多，都是一些低级错误。
好吧全都是水题。
水题（只放代码）
莫诺卡普参加了一场编程比赛，其中包括 \(26\) 个问题，从
A到Z命名。问题按难度排序。此外，已知莫诺卡普可以在 \(1\) 分钟内解决问题A，在 \(2\) 分钟内解决问题B，\(\dots\)，在 \(26\) 分钟内解决问题Z。比赛结束后，你发现了他的比赛记录 - 一个由大写拉丁字母组成的字符串，其中第 \(i\) 个字母表示莫诺卡普在比赛的第 \(i\) 分钟时正在解决的问题。如果莫诺卡普总共花费了足够的时间来解决一个问题，他就解决了它。请计算莫诺卡普在比赛期间解决的问题数量。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
using namespace std;
using ll = long long;
#define mtest for (cin >> t; t; -- t)
const int kMaxN = 1e5 + 10, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;
int n;
string s;
int a[kMaxN];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
mtest {
for (int i = 1; i <= 26; ++ i) {
a[i] = 0;
}
cin >> n >> s;
for (int i = 0; i < s.size(); ++ i) {
++ a[s[i] - 'A' + 1];
}
int ans = 0;
for (int i = 1; i <= 26; ++ i) {
if (a[i] >= i) {
++ ans;
}
}
cout << ans << '\n';
}
return 0;
}
C - Preparing for the Contest（CF1914B）
输出一个长度为 \(n\) 的序列，使序列中后一个数比前一个数大的次数为 \(k\)。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
using namespace std;
using ll = long long;
#define mtest for (cin >> t; t; -- t)
const int kMaxN = 1e5 + 10, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;
int n, k;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
mtest {
cin >> n >> k;
for (int i = 1; i <= (!k? 0 : k); ++ i) {
cout << i << ' ';
}
int ans = 1;
for (int i = n; ans <= (!k? n : n - k); -- i) {
cout << i << ' ';
++ ans;
}
cout << '\n';
}
return 0;
}
E - Rating Increase（CF1913A）
给定 \(\overline{ab}\)，求任意一种可能的 \(a,b\)，其中 \(0<a<b\) 且 \(a,b\) 无前导零。如果无解，请输出 \(-1\)。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
using namespace std;
using ll = long long;
#define mtest for (cin >> t; t; -- t)
const int kMaxN = 1e5 + 10, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;
string s;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
mtest {
cin >> s;
bool f = 0;
for (int i = 0; i < s.size() - 1; ++ i) {
if (stoi(s.substr(0, i + 1)) < stoi(s.substr(i + 1)) && s[i + 1] != '0') {
cout << s.substr(0, i + 1) << ' ' << s.substr(i + 1) << '\n';
f = 1;
break;
}
}
if (!f) {
cout << -1 << '\n';
}
}
return 0;
}
高级水题
F - Swap and Delete（CF1913B）
有一个只含 \(\texttt{0}\) 和 \(\texttt{1}\) 的字符串 \(s\)，你可以对它进行如下两种操作：耗费一个金币，从 \(s\) 中删除 \(1\) 个字符，将 \(s\) 中任意两字符互换位置（免费）。定义一个字符串 \(t\) 是美的代表对于所有满足 \(1 \le i \le \left|t\right|\) 的 \(i\)，\(s_i \ne t_i\) 。你可以进行任意多次操作，假设 \(s\) 修改后变为了 \(s'\)，问最少花费多少金币能使最终得到的 \(s'\) 是美的。
记录每个 \(s\) 的 \(0\) 和 \(1\) 的数量，然后遍历 \(s\)，\(s\) 串为 \(1\) 则填 \(0\)，为 \(0\) 则填 \(1\)。当无法继续填时输出 \(s\) 的长度减去填的字符总数。因为此时后面的不管怎么填一定会有相同，只能全删。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
using namespace std;
using ll = long long;
#define mtest for (cin >> t; t; -- t)
const int kMaxN = 1e5 + 10, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;
string s;
auto C() {
int zr = 0, one = 0;
for (int i = 0; i < s.size(); ++ i) {
s[i] == '0'? ++ zr : ++ one;
}
return make_pair(one, zr);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
mtest {
cin >> s;
int a = C().first, b = C().second;
string s2 = "";
for (int i = 0; i < s.size(); ++ i) {
if (s[i] == '0') {
if (a > 0) {
s2 += "1";
-- a;
} else {
break;
}
} else {
if (b > 0) {
-- b;
s2 += "0";
} else {
break;
}
}
}
cout << s.size() - s2.size() << '\n';
}
return 0;
}
D - Quests（CF1914C）
有 \(n\) 个任务，在完成 \(i\) 任务时，\(i\) 之前的所有任务都必须完成。同时，可以多次完成某个任务。总共可以做 \(k\) 次任务，第一次完成 \(i\) 任务的贡献为 \(a_i\) ，后面完成 \(i\) 任务的贡献为 \(b_i\) ，求最大贡献。
当 \(k\) 个次数全部用于前 \(i\) 个任务时，当且仅当每个任务都至少做过一遍，且剩余的次数全部用于前 \(i\) 个任务中 \(b\) 花费最大的任务，取到当前情况的最大花费。
最优的策略是选 \(1 \sim i\) 中最大的 \(b_i\)，选 \(k - i\ (1 \le i \le \min(n, k))\) 次，然后把答案加起来。
前缀和预处理。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#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;
int n, k;
struct node {
ll a, b;
} a[kMaxN];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
mtest {
cin >> n >> k;
for (int i = 0; i < n; ++ i) {
cin >> a[i].a;
}
for (int i = 0; i < n; ++ i) {
cin >> a[i].b;
}
ll p = 0, cnt = 0, maxa = 0, ans = 0;
for (int i = 0; i < n && i != k; ++ i) {
maxa = max(maxa, a[i].b), cnt += a[i].a;
p = (k - i - 1) * maxa + cnt, ans = max(ans, p);
}
cout << ans << '\n';
}
return 0;
}
A - Three Activities（CF1914D）
给定三个数组 \(a,b,c\)，找三个互不相同的整数 \(i,j,k\)，使得 \(a_i+b_j+c_k\) 的值最大。
额，出这种题很无聊，洛谷都评了个黄（CSPJ T3 难度左右）。除了码量多了一点还有什么难度？看了洛谷题解，还有用 dp 的……
直接搜索即可。先按照从大到小排好序，然后搜索时搜索前 \(3\) 大的每种排列，取最大值。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
using namespace std;
using ll = long long;
#define mtest for (cin >> t; t; -- t)
const int kMaxN = 1e5 + 10, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;
int n, ans = 0;
bool vis[kMaxN];
struct node {
int w, id;
} a[kMaxN], b[kMaxN], c[kMaxN];
bool cmp(node a, node b) {
return a.w > b.w;
}
void S(int k, int sum) {
if (k > 3) {
ans = max(ans, sum);
return;
}
for (int i = 1; i <= 3; ++ i) {
if (k == 1) {
if (!vis[a[i].id]) {
vis[a[i].id] = 1;
S(k + 1, sum + a[i].w);
vis[a[i].id] = 0;
}
}
if (k == 2) {
if (!vis[b[i].id]) {
vis[b[i].id] = 1;
S(k + 1, sum + b[i].w);
vis[b[i].id] = 0;
}
}
if (k == 3) {
if (!vis[c[i].id]) {
vis[c[i].id] = 1;
S(k + 1, sum + c[i].w);
vis[c[i].id] = 0;
}
}
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
mtest {
cin >> n;
for (int i = 1; i <= n; ++ i) {
cin >> a[i].w;
}
for (int i = 1; i <= n; ++ i) {
cin >> b[i].w;
}
for (int i = 1; i <= n; ++ i) {
cin >> c[i].w;
}
for (int i = 1; i <= n; ++ i) {
a[i].id = b[i].id = c[i].id = i;
}
sort(a + 1, a + n + 1, cmp);
sort(b + 1, b + n + 1, cmp);
sort(c + 1, c + n + 1, cmp);
memset(vis, 0, sizeof vis);
ans = 0;
S(1, 0);
cout << ans << '\n';
}
return 0;
}
正常题
G - Game with Multiset（CF1913C）
你有一个空的多重集，你需要处理若干下列询问：ADD \(x\)：加入一个数值为 \(2^x\) 的元素到该多重集，GET \(w\)：判断是否存在一个该多重集的子集，使得这个子集的所有元素之和等于 \(w\)。
这是唯一一道正常题。
首先我们预处理 \(2^0 \sim 2^{29}\)，存在一个 map 里，\(mp_i = 2^i\)。然后再开另一个 map，名为 mp2。
- ADD
将 \(2^i\) 的元素 \(+1\) 即可。（++ mp2[mp[v]）
- GET
我们从 \(29\) 开始遍历 \(mp\)。每一次 \(w\) 不为 \(0\) 且 \(v \ge mp_i\) 时，如果 \(2^i\) 的个数不为 \(0\)，将 \(w\) 减去 \(\min(v \div \text{mp}_i, \text{mp2}_{\text{mp}_i})\text{mp}_i\)。
如果 \(w\) 最后为 \(0\)，输出 YES，否则输出 NO。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
using namespace std;
using ll = long long;
#define mtest for (cin >> t; t; -- t)
const int kMaxN = 1e5 + 10, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;
ll m;
map<ll, ll> mp, mp2;
void init() {
for (ll i = 0; i < 30; ++ i) {
mp[i] = (1ll << i);
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
cin >> m;
for (; m; -- m) {
int op, v;
cin >> op >> v;
if (op == 1) {
++ mp2[mp[v]];
} else {
for (ll i = 29; i >= 0; -- i) {
if (v != 0 && v >= mp[i]) {
if (mp2.count(mp[i])) {
v -= min(v / mp[i], mp2[mp[i]]) * mp[i];
}
}
}
cout << (!v? "YES" : "NO") << '\n';
}
}
return 0;
}