当前位置: 首页 > news >正文

Codeforces Round 1054 (Div. 3)


A. Be Positive

题意:一个数组\(a\),只包含\(-1, 0, 1\)。你每次可以使得一个数加一,求使得数组乘积为正的最少操作次数。

显然只需要操作\(-1\)或者\(0\)\(0\)必须都加一。那么如果\(-1\)是偶数个,不需要操作,否则需要操作一个\(-1\)两次变成\(1\)

点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::vector<int> a(n);for (int i = 0; i < n; ++ i) {std::cin >> a[i];}int cnt0 = std::ranges::count(a, 0);int cnt1 = std::ranges::count(a, -1);int cnt2 = std::ranges::count(a, 1);if (cnt1 == n) {std::cout << cnt1 % 2 * 2 << "\n";} else if (cnt1 & 1) {std::cout << cnt0 + 2 << "\n";} else {std::cout << cnt0 << "\n";}
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}

B. Unconventional Pairs

题意:\(2n\)个数,分成\(n\)对,每对的值为两个数的差的绝对值,这一个分组的价值为所有对的值的最大值。求所有分组里价值最小的。

数组排序后从前往后两个两个分组。这样是最小的。
因为如果交换任意两个数,每

点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::vector<int> a(n);for (int i = 0; i < n; ++ i) {std::cin >> a[i];}std::ranges::sort(a);int ans = 0;for (int i = 0; i < n; i += 2) {ans = std::max(ans, a[i + 1] - a[i]);}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
一对的值都大于原来的对。

C. MEX rose

题意:一个数组,每次将一个数变成任意一个数,求数组\(mex\)变成\(k\)的最小操作数。

对于\([0, k)\)的数,如果没有出现过则拿大于等于\(k\)的元素变,优先拿等于\(k\)的变。
这样\(0\)\(k-1\)有了,只需要把多余的\(k\)变成比\(k\)大的数就行。

点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, k;std::cin >> n >> k;std::vector<int> cnt(n + 1);for (int i = 0; i < n; ++ i) {int x;std::cin >> x;++ cnt[x];}int ans = 0;for (int i = 0; i < k; ++ i) {if (!cnt[i]) {ans += 1;cnt[k] = std::max(0, cnt[k] - 1);}}ans += cnt[k];std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}

D. A and B

题意:一个只包含\(a\)\(b\)的字符串,每次可以交换相邻两个元素。求把某一类字符都合并成一块的最小操作数。

假设把\(a\)合并到一块,可以先把所有\(a\)移到最前面,那么从前往后可以直到每个\(a\)需要移动的次数,用\(cnt_i\)表示有\(cnt_i\)\(a\)需要往前移动\(i\)次。那么现在考虑枚举把整块往后一步一步移,那么如果往右移动了\(k\)步,则需要往前移动\([k, n]\)的都可以少移动一步。对于需要移动\([0, k-1]\)的都需要往后多移动一步。记录前缀和后缀和就可以计算。
\(b\)合并一块同理计算。

点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::string s;std::cin >> s;auto get = [&](std::string s) -> i64 {std::vector<i64> sum(n + 1);i64 v = 0;for (int i = 0, j = 0; i < n; ++ i) {if (s[i] == 'a') {sum[i - j] += 1;v += i - j;++ j;}}std::vector<int> pre(n), suf(n + 1);pre[0] = sum[0];for (int i = 1; i < n; ++ i) {pre[i] = pre[i - 1] + sum[i];}for (int i = n - 1; i >= 0; -- i) {suf[i] = suf[i + 1] + sum[i];}i64 res = v;for (int i = 0; i < n; ++ i) {v -= suf[i + 1];v += pre[i];res = std::min(res, v);}return res;};i64 ans = get(s);for (auto & c : s) {c = c == 'a' ? 'b' : 'a';}ans = std::min(ans, get(s));std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}

E. Hidden Knowledge of the Ancients

题意:给你一个数组\(a\),求有多少子数组,长度在\([l, r]\)之间,且恰好有\(k\)个不同的数。

考虑双指针求对于\(i\)作为左端点时,最小的右端点\(j\)使得\([i, j]\)恰好有\(cnt\)个不同的数。
可以用\(multiset\)维护。
那么求得\(cnt = k, cnt = k + 1\)时的答案,就可以知道恰好有\(k\)个数的右端点的取值区间。

点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, k, l, r;std::cin >> n >> k >> l >> r;std::vector<int> a(n);for (int i = 0; i < n; ++ i) {std::cin >> a[i];}std::multiset<int> s;int cnt = 0;auto add = [&](int x) -> void {if (s.find(x) == s.end()) {++ cnt;}s.insert(x);};std::vector<int> p1(n), p2(n);for (int i = 0, j = 0; i < n; ++ i) {j = std::max(i, j);while (j < n && j - i + 1 <= r && cnt < k) {add(a[j]);++ j;}if (cnt == k) {p1[i] = j - 1;} else {p1[i] = n;}p1[i] = std::max(p1[i], i + l - 1);s.extract(a[i]);if (!s.count(a[i])) {-- cnt;}}s.clear();cnt = 0;++ k;for (int i = 0, j = 0; i < n; ++ i) {j = std::max(i, j);while (j < n && j - i + 1 <= r && cnt < k) {add(a[j]);++ j;}if (cnt == k) {p2[i] = j - 1;} else {p2[i] = j;}s.extract(a[i]);if (s.find(a[i]) == s.end()) {-- cnt;}}i64 ans = 0;for (int i = 0; i < n; ++ i) {ans += std::max(0, p2[i] - p1[i]);}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}

F. Nezuko in the Clearing

题意:需要移动\(d\)步,一开始有\(h\)点血。每次可以移动一步,如果连续移动\(i\)次这一步会使得\(h\)\(i\)。你也可以选择休息一回合,这使得\(h\)加一。任何时候\(h\)都要大于\(0\)。求移动\(d\)步的操作次数。

首先,每次最多连续休息一回合。因为如果多休息一回合,不如让上一次连续移动里少移动一步。
那么如果休息了\(m\)回合,则把\(d\)步分成了\(m+1\)段,一个段长为\(l\)的段需要\(\frac{l(l+1)}{2}\)的血量。我们应该让每一段长度尽可能接近,即\(a = \lfloor \frac{d}{m+1} \rfloor, r = d \% (m + 1)\),那么应该是\(m + 1 - r\)个长度为\(a\)的段,\(r\)个长度为\(a+1\)的段。因为如果有两个段使得其中一段步数比另一段大于等于\(2\),则把多的一段分一些给少的一段更好。
那么只需要\(h + m > (m + 1 - r)\times \frac{a(a+1)}{2} + r\times \frac{(a+1)(a+2)}{2}\)\(m+1\)段就是可以的。
发现\(k\)段能行的话,分比\(k\)多的段也行,则可以二分。

点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {i64 h, d;std::cin >> h >> d;auto check = [&](i64 m) -> bool {i64 a = d / (m + 1), r = d % (m + 1);i64 sum = a * (a + 1) / 2 * (m + 1 - r) + (a + 1) * (a + 2) / 2 * r;return sum + 1 <= h + m;};i64 lo = 1, hi = d;while (lo < hi) {i64 mid = lo + hi >> 1ll;if (check(mid)) {hi = mid;} else {lo = mid + 1;}}i64 ans = std::max(0ll, d * (d + 1) / 2 + 1 - h) + d;std::cout << std::min(ans, d + lo) << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}

G. Buratsuta 3

题意:一个数组,每次问一个区间\([l, r]\)有哪些数出现次数大于\(\lfloor \frac{r-l+1}{3} \rfloor\)

因为一个数需要出现大于\(\lfloor \frac{r-l+1}{3} \rfloor\)次,则这样的数不超过\(2\)个。
可以用Boyer–Moore 投票算法。
假设是求出现次数大于\(\lfloor \frac{r-l+1}{2} \rfloor\)的数,那么这样的数最多有\(1\)个。这个数的出现次数肯定大于其它数,可以从前往后遍历,记\(x = a[l], c = 1\),如果\(a_i = x\),则\(c += 1\),否则\(c -= 1\);如果\(c == 0\),则\(x = a[i]\)。最后\(x\)可能是答案。因为这样相当于两个两个不同的数抵消,最后剩下的一定是出现最多的数。
推广到求出现次数大于\(\lfloor \frac{r-l+1}{k} \rfloor\)的数,那么这样的数不超过\(k-1\)个,可以维护\(k-1\)\(x\)。对于遇到的一个数,如果在这\(k-1\)\(x\)里,则累加次数,否则和所有\(x\)出现的次数一起抵消掉。
然后对于这道题,他每次是求一个区间,我们可以用线段树维护。
然后这里求出的是可能作为答案的数,我们还需要记录它们的出现位置,然后二分求一下\([l, r]\)它们出现了多少次。

点击查看代码
#include <bits/stdc++.h>using i64 = long long;template <class Info>
struct SegmentTree {struct Node {int l, r;Info info;};std::vector<Node> tr;SegmentTree() {};SegmentTree(int n) {init(n);}SegmentTree(std::vector<int> & info) {init(info);}void init(int n) {tr.assign(n << 2, {});build(0, n - 1);}void init(std::vector<int> & info) {int n = info.size();tr.assign(n << 2, {});std::function<void(int, int, int)> build = [&](int l, int r, int u) -> void {tr[u] = {l, r, {}};if (l == r) {tr[u].info.insert(info[l], 1);return;}int mid = l + r >> 1;build(l, mid, u << 1); build(mid + 1, r, u << 1 | 1);pushup(u);};build(0, n - 1, 1);}void pushup(int u) {tr[u].info = tr[u << 1].info + tr[u << 1 | 1].info;}void build(int l, int r, int u = 1) {tr[u] = {l, r, {}};if (l == r) {return;}int mid = l + r >> 1;build(l, mid, u << 1); build(mid + 1, r, u << 1 | 1);pushup(u);}void modify(int p, const Info & info, bool set = false) {int u = 1;while (tr[u].l != tr[u].r) {int mid = tr[u].l + tr[u].r >> 1;if (p <= mid) {u = u << 1;} else {u = u << 1 | 1;}}if (set) {tr[u].info = info;} else {tr[u].info = tr[u].info + info;}u >>= 1;while (u) {pushup(u);u >>= 1;}}Info query(int l, int r, int u = 1) {if (l <= tr[u].l && tr[u].r <= r) {return tr[u].info;}int mid = tr[u].l + tr[u].r >> 1;if (r <= mid) {return query(l, r, u << 1);} else if (l > mid) {return query(l, r, u << 1 | 1);}return query(l, r, u << 1) + query(l, r, u << 1 | 1);}
};struct Info {int x[2], c[2];void insert(int X, int C) {if (c[0] && x[0] == X) {c[0] += C;} else if (c[1] && x[1] == X) {c[1] += C;} else {int min = std::min({c[0], c[1], C});c[0] -= min;c[1] -= min;C -= min;if (!C) {return;;}if (c[0] == 0) {x[0] = X;c[0] = C;} else if (c[1] == 0) {x[1] = X;c[1] = C;}}}
};Info operator + (const Info & l, const Info & r) {Info res{};res.insert(l.x[0], l.c[0]);res.insert(l.x[1], l.c[1]);res.insert(r.x[0], r.c[0]);res.insert(r.x[1], r.c[1]);return res;
}void solve() {int n, q;std::cin >> n >> q;std::vector<int> a(n);for (int i = 0; i < n; ++ i) {std::cin >> a[i];}auto b = a;std::ranges::sort(b);b.erase(std::unique(b.begin(), b.end()), b.end());for (auto & x : a) {x = std::ranges::lower_bound(b, x) - b.begin();}int m = b.size();std::vector<std::vector<int>> pos(m);for (int i = 0; i < n; ++ i) {pos[a[i]].push_back(i);}SegmentTree<Info> tr(a);while (q -- ) {int l, r;std::cin >> l >> r;-- l, -- r;int k = (r - l + 1) / 3;std::vector<int> ans;auto info = tr.query(l, r);for (int i = 0; i < 2; ++ i) {int x = info.x[i], y = info.c[i];if (y == 0) {continue;}int L = std::ranges::lower_bound(pos[x], l) - pos[x].begin();int R = std::ranges::upper_bound(pos[x], r) - pos[x].begin();if (R - L > k) {ans.push_back(b[x]);}}if (ans.empty()) {std::cout << -1 << "\n";} else {std::ranges::sort(ans);for (auto & x : ans) {std::cout << x << " \n"[x == ans.back()];}}}
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
http://www.hskmm.com/?act=detail&tid=17553

相关文章:

  • Python 在自动化与运维中的价值与实践
  • redis 哨兵模式主从数据同步失败
  • 悲观锁,乐观锁和redis分布式锁
  • sql练习笔记
  • 算法练习
  • 数据库基础
  • 【System Beats!】第三章 程序的机器级表示
  • 苍穹外卖-day06(HttpClient) - a
  • Python 虚拟环境管理-学习笔记分享
  • 元人文AI的领域化部署:从哲学构想到实践应用的完整路径
  • 做题记录3
  • oucaiclub_cheapter1
  • navicat
  • 20250925 之所思 - 人生如梦
  • 在CodeBolcks下wxSmith的C++编程教程——在屏幕上绘图和保存绘图
  • 苍穹外卖-day07(缓存菜品,缓存套餐,添加购物车,查看购物车,清空购物车) - a
  • 一次CPU飙升问题排查定位
  • ros2 control 2
  • 基于洞察的智能编程法——从直觉到代码的原型炼成术
  • lc1036-逃离大迷宫
  • 9.25学习笔记
  • 新学期每日总结(第4天)
  • VSCode 升级 C++支持版本
  • 第四天
  • 25.9.25
  • 在electron-vite使用ShadCN
  • 每日博客(补)
  • 如何使用极限网关实现 Elasticsearch 集群迁移至 Easysearch
  • 文档抽取技术:实现金融保险业务流程自动化
  • 算法作业