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

Codeforces Global Round 29 (Div. 1 + Div. 2) A~E

A - Shortest Increasing Path

思维。

\(y>x\) 时,可以走 \(x\rightarrow y\) 两步即可;\(x \ge y + 2\) 时,可以走 \(1 \rightarrow y \rightarrow y + 1\) 三步即可,其余无解。

点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;void solve() {int x, y;cin >> x >> y;if (y == 1 || y == x) {cout << "-1\n";} else if (y > x) {cout << 2 << "\n";} else {if (x >= y + 2) {cout << 3 << "\n";} else {cout << -1 << "\n";}}}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}

B - Multiple Construction

构造。

打表发现的规律,可以诸如 \(n,n-1,...,1,n,1,2,...,n-2,n-1\) 这样去构造即可。

点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;void solve() {int n;cin >> n;vector<int> pos(2 * n + 1), cnt(n + 1), p(2 * n + 1);auto dfs = [&](auto & self, int idx, int x)->void{if (cnt[x] > 1 && (idx - pos[x]) % x != 0) {return;}if (idx > 2 * n) {for (int i = 1; i <= 2 * n; i += 1) {cout << p[i] << " \n"[i == 2 * n];}return;}pos[x] = idx;for (int i = 1; i <= n; i += 1) {if (cnt[i] > 1) continue;cnt[i] += 1;p[idx] = i;self(self, idx + 1, i);cnt[i] -= 1;}};// for (int i = 1; i <= n; i += 1) {// 	dfs(dfs, 1, i);// }for (int i = n; i >= 1; i -= 1) {cout << i << " ";}cout << n << " ";for (int i = 1; i <= n - 1; i += 1) {cout << i << " \n"[i == n - 1];}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}

C - Rabbits

分类讨论。

之前写的,有点忘了大致就是维护最后一个 \(0\) 是否可以自由选择方向,如果是第一个 \(0\) 或者一长串的 \(0\) 的最后一个,那就都可以自由选,如果是由自由的 \(0\) 转移过来的,那当前 \(0\) 也是可以自由选。

不能自由选的情况就是,左边的没有相隔为 \(2\)\(0\),或者左边的 \(0\) 已经被锁定了,那就只能看右边存不存在合法 \(0\) 去配对。

这题细节有点多,当时写了个对拍一边拍一边改,还好一发过了。

点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;void solve() {int n;cin >> n;string s;cin >> s;s = " " + s;vector<int> pos;for (int i = 1; i <= n; i += 1) {if (s[i] == '0') {pos.push_back(i);}}if (pos.size() == 1) {if (pos[0] == 1 || pos[0] == n) {cout << "YES\n";} else {cout << "NO\n";}return;}int lst = 0;for (int i = 0; i < pos.size(); i += 1) {int j = i;while (j + 1 < pos.size() && pos[j + 1] == pos[j] + 1) {j += 1;}bool f = 0;if (i - 1 >= 0 && pos[i - 1] == pos[i] - 1) {f = 1;}if (j - i + 1 + f > 1) {lst = 1;i = j;continue;} else {if (pos[i] == 1 || pos[i] == n) {lst = 1;continue;}if (i - 1 >= 0 && pos[i] - pos[i - 1] == 2 && lst) {lst = 1;} else if (i + 1 < pos.size() && pos[i + 1] - pos[i] == 2) {i += 1;lst = 0;} else {cout << "NO\n";return;}}}cout << "YES\n";}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}

D - Game on Array

思维。

值为偶数的,显然两边同时加减得到的贡献是一样的,那么想让自己得到的更多,显然是去争取奇数值的,所以可以把奇数取出来按照出现的次数排序,Ailce 和 Bob 轮流取,最后算一下偶数的贡献即可。

点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;void solve() {int n;cin >> n;map<int, int> mp, s;for (int i = 1; i <= n; i += 1) {int x;cin >> x;mp[x] += 1;}vector<array<int, 2>> a;for (auto &[x, y] : mp) {if (x & 1) {a.push_back({y, x});} else {s[x] += y;}}sort(a.begin(), a.end(), greater<>());i64 A = 0, B = 0;for (int i = 0; i < a.size(); i += 1) {auto [y, x] = a[i];if (i % 2 == 0) {A += y;} else {B += y;}if (x - 1 > 0) {s[x - 1] += y;}}for (auto &[x, y] : s) {i64 res = 1LL * x * y / 2;A += res, B += res;}cout << A << " " << B << "\n";}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}

E. Maximum OR Popcount

位运算,贪心。

大部分人应该都能想到只要求出每个一的最小花费,然后对于每次询问,去找能满足多少个一就行了。

但是在求第 \(i\) 位的最小花费时,后面就可能不满足全 \(1\) 的条件了,比如 \(2|1|10|6=1111_2\),把 \(10\) 变成 \(16\) 后,第 \(3\) 位的 \(1\) 就没有了,变成 \(2|1|16|6=10111_2\)。对于这种情况,我们需要继续贪心的往后求每一位都变为 \(1\) 的代价,这才能确保 \(1\) 的个数增加的情况下花费最少。

至于为什么每次都求一遍把 \(i\sim 0\) 全置为 \(1\) 得到增加第 \(i\) 位的代价是最小的,这里有证明[1]

点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;void solve() {int n, q;cin >> n >> q;int d = 0;vector<int> a(n + 1);for (int i = 1; i <= n; i += 1) {cin >> a[i];d |= a[i];}vector<int> b{0};for (int j = 0; j <= 30; j += 1) {if (d >> j & 1) {continue;}int cost = b.back();for (int k = j; k >= 0; k -= 1) {int mi = INT_MAX, ok = 0, t = -1;for (int i = 1; i <= n; i += 1) {if (a[i] >> k & 1) {ok = 1;break;}int p = ((1 << k + 1) - 1) & a[i];int need = (1 << k) - p;if (need < mi) {mi = need, t = i;}}if (ok) {continue;}cost += mi;a[t] >>= k;a[t] <<= k;a[t] |= 1 << k;}b.push_back(cost);}int base = __builtin_popcount(d);while (q--) {int x;cin >> x;int t = 0;while (t + 1 < b.size() && b[t + 1] <= x) {t += 1;}cout << base + t << "\n";}}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}

  1. [https://codeforces.com/blog/entry/146633] ↩︎

http://www.hskmm.com/?act=detail&tid=17332

相关文章:

  • AI 低代码平台:不止于 “快”,解码技术融合的深层逻辑
  • 实用指南:【知识拓展Trip Five】寄存器
  • 计算机视觉(opencv)实战二十七——目标跟踪 - 教程
  • P8367 [LNOI2022] 盒
  • 蓝桥杯 2025 省 B 题:画展布置 - 题解笔记
  • 二维坐标下的运算
  • Polar2025秋季个人挑战赛web-writeup
  • Day4
  • 题解:P12751 [POI 2017 R2] 集装箱 Shipping containers
  • 弱网配置
  • 绘制金融集团监控大屏的地图demo
  • 实用指南:《原神助手》开源神器:游戏体验大升级
  • 9-25
  • AT_agc021_d [AGC021D] Reversed LCS
  • adb shell 常用文件命令
  • Java文件编程
  • 自我介绍与规划
  • 软件工程学习日志2025.9.25
  • 从50ms到30ms:YOLOv10部署中图像预处理的性能优化实践 - 实践
  • redis实现分布式锁1
  • 完整教程:(13)GPS/无GPS转换
  • Transformer自回归关键技术:掩码注意力原理与PyTorch完整实现
  • 第四篇
  • PyTorch图神经网络(六)
  • Qwen多模态系列模型笔记—Qwen-VL
  • go 语法里变量前面增加、*区别
  • 历程回顾-(2024-2025)
  • CF Round 1053(2150 2151) 总结
  • 20250922_QQ_backdoor
  • 实用指南:【Java八股文】13-中间件面试篇