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

Codeforces Round 1060 (Div. 2)


A. Notelock

题意:一个二进制串,问有多少位置的前\(k-1\)个位置没有\(1\)

从前往后扫,维护一个可以包含的最右位置就行。

点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, k;std::cin >> n >> k;std::string s;std::cin >> s;int ans = 0;for (int i = 0, j = 0; i < n; ++ i) {if (i >= j && s[i] == '1') {++ ans;}if (s[i] == '1') {j = std::max(j, i + 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;
}

B. Make it Zigzag

题意:一个数组,要求偶数位置大于左右两个位置。你可以做两个操作,一种是使得\(a_i\)等于前缀最大值,一种是使得\(a_i\)减一。求第二种操作的最小操作个数。

可以先把每个偶数位置做一次操作\(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];}i64 ans = 0;for (int i = 0, max = 0; i < n; ++ i) {max = std::max(max, a[i]);if (i & 1) {a[i] = max;}}for (int i = 1; i < n; i += 2) {if (a[i - 1] >= a[i]) {ans += a[i - 1] - (a[i] - 1);}if (i + 1 < n && a[i + 1] >= a[i]) {ans += a[i + 1] - (a[i] - 1);a[i + 1] = a[i] - 1;}}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. No Cost Too Great

题意:两个长度为\(n\)的数组\(a, b\)。你每次可以使得\(a_i\)加一,花费\(b_i\)。求使得\(a\)中至少有两个元素的\(gcd\)大于\(1\)的最小花费。

先质数筛一下,然后求出每个数的质因子,如果有两个数有相同的质因子直接就\(ok\)
否则看有没有偶数,如果有的话,那么就只有一个偶数,可以让奇数里花费最小的加一变成偶数。或者把这个偶数变成某个奇数的一个质因子的倍数,枚举质因子计算贡献即可。
如果没有偶数,那么可以拿花费最小的两个奇数加一。然后其它操作如果想小于这个操作,任意两个数的花费肯定大于等于这个花费,那么只有一个数操作一次或者两次的情况可能小于等于这个花费,那么枚举每个数加一次或者两次有没有质因子是其它数有的。最后最小花费的数可以操作多次,这个和前面的偶数情况一样计算贡献即可。

点击查看代码
#include <bits/stdc++.h>using i64 = long long;std::vector<int> minp, primes;void sieve(int n) {minp.assign(n + 1, 0);primes.clear();for (int i = 2; i <= n; ++ i) {if (minp[i] == 0) {minp[i] = i;primes.push_back(i);}for (auto p : primes) {if (i * p > n) {break;}minp[i * p] = p;if (p == minp[i]) {break;}}}
}void solve() {int n;std::cin >> n;std::vector<int> a(n), b(n);for (int i = 0; i < n; ++ i) {std::cin >> a[i];}for (int i = 0; i < n; ++ i) {std::cin >> b[i];}std::map<int, int> cnt;for (auto x : a) {while (x > 1) {int p = minp[x];if (++ cnt[p] > 1) {std::cout << 0 << "\n";return;}while (x % p == 0) {x /= p;}}}i64 ans = 0;if (cnt.contains(2)) {int pos = -1, minv = 2e9;for (int i = 0; i < n; ++ i) {if (a[i] % 2 == 0) {pos = i;} else {minv = std::min(minv, b[i]);}}ans = minv;for (auto & [p, _] : cnt) {if (a[pos] % p != 0) {ans = std::min(ans, (i64)b[pos] * ((i64)(a[pos] + p - 1) / p * p - a[pos]));}}} else {std::vector<std::pair<int, int>> c;for (int i = 0; i < n; ++ i) {c.emplace_back(b[i], a[i]);}std::ranges::sort(c);ans = c[0].first + c[1].first;for (int i = 0; i < n; ++ i) {int x = a[i] + 1;if (b[i] >= ans) {continue;}while (x > 1) {int p = minp[x];if (a[i] % p != 0 && cnt.contains(p)) {ans = b[i];break;}while (x % p == 0) {x /= p;}}}for (int i = 0; i < n; ++ i) {int x = a[i] + 2;if (2 * b[i] >= ans) {continue;}while (x > 1) {int p = minp[x];if (a[i] % p != 0 && cnt.contains(p)) {ans = 2 * b[i];break;}while (x % p == 0) {x /= p;}}}int min = c[0].second, v = c[0].first;for (auto & [p, _] : cnt) {if (min % p != 0) {ans = std::min(ans, (i64)v * ((i64)(min + p - 1) / p * p - min));}}}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;sieve(2e5 + 5);std::cin >> t;while (t -- ) {solve();}return 0;
}

D. Catshock

题意:一棵树,一开始猫在\(1\)点,要去\(n\)点,有两个指令,第一个是让猫随机移动到当前点的一个邻点,一个是把\(u\)的邻边都断掉。给出不超过\(3n\)的指令,使得不管怎样猫最后停留在\(n\)点。第二个指令不能连续使用。

\(1\)出发\(dfs\)一下,求出每个点到\(1\)的距离的奇偶性,和\(1\)\(n\)路径上的点。
用两个大根堆分别存不在路径上的奇数距离和偶数距离的点,按照他们的距离排序。然后按时间奇偶性看,如果当前最大距离的奇偶性不是当前时间的奇偶性,那么猫一定不在当前最远的点上,则可以把这个点删掉,如此循环把所有非路径上的点删掉。
然后只剩下路径上的点,从头到尾一样操作即可。

点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::vector<std::vector<int>> adj(n);for (int i = 1; i < n; ++ i) {int u, v;std::cin >> u >> v;-- u, -- v;adj[u].push_back(v);adj[v].push_back(u);}std::vector<int> path;std::set<int> S;std::vector<int> d(n);auto dfs = [&](auto && self, int u, int fa) -> bool {bool flag = false;for (auto & v : adj[u]) {if (v == fa) {continue;}d[v] = d[u] + 1;if (self(self, v, u)) {flag = true;}}if (u == n - 1 || flag) {path.push_back(u);S.insert(u);return true;}return false;};dfs(dfs, 0, -1);std::priority_queue<std::pair<int, int>> heap[2];for (int i = 0; i < n; ++ i) {if (!S.contains(i)) {heap[d[i] & 1].emplace(d[i], i);}}std::vector<std::pair<int, int>> ans;int cnt = n - S.size();int i = 0;for (; cnt; ++ i) {int x = i % 2 ^ 1;if (heap[x].size()) {if (heap[x ^ 1].size() && heap[x ^ 1].top().first > heap[x].top().first) {} else {int u = heap[x].top().second;heap[x].pop();ans.emplace_back(2, u);-- cnt;}}ans.emplace_back(1, -1);}std::ranges::reverse(path);path.pop_back();int f = 0;for (auto & x : path) {if (f) {ans.emplace_back(1, -1);f = 0;++ i;}while (d[x] % 2 == i % 2) {ans.emplace_back(1, -1);++ i;}ans.emplace_back(2, x);f = 1;}std::cout << ans.size() << "\n";for (auto & [x, u] : ans) {if (x == 1) {std::cout << 1 << "\n";} else {std::cout << 2 << " " << u + 1 << "\n";}}std::cout << "\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;
}
http://www.hskmm.com/?act=detail&tid=34610

相关文章:

  • Luogu P14260 期待(counting) 题解 [ 蓝 ] [ 前缀和 ] [ 组合计数 ]
  • 实现一个自动生成小学四则运算题目的命令行程序
  • EasySQLite 升级到.slnx 格式后的性能优化效果解析
  • golang unique包和字符串内部化
  • 永久暂停window10更新,不想更新到window11
  • 算法第二章作业
  • 102302148谢文杰第一次数据采集作业
  • RaspberryPi 个人服务搭建
  • tryhackme-预安全-网络如何工作-网站如何工作-11
  • 2025塑料托盘优质厂家推荐,力森塑业科技多元化产品满足各类需求!
  • 嵌入式实验3串口通信--任务二USART1通信
  • Drive Snapshot
  • 20232319 2025-2026-1 《网络与系统攻防技术》实验二实验报告
  • 刷题日记—洛谷循环题单
  • 为什么需要学习变异的算法?
  • 今天搞了新的回归,不显著
  • shell编程学习笔记005之until循环
  • shell编程学习笔记006之select循环
  • burpsuite抓取小程序公众号数据包-cnblog
  • 2026 NOI 做题记录(七)
  • esp8266模块开发准备工作
  • 关于本学期我的编码规范与数学之美第一章观后感 - C
  • 线程--线程生命周期、Synchronized
  • C#中Yolo开发环境
  • CF1918F Caterpillar on a Tree
  • tryhackme-预安全-网络如何工作-DNS 详细信息-09
  • Diffusion
  • SP4191 天空代码 分析
  • l2正则化项以及torch.norm
  • 又数据结构