Codeforces Round #715 (Div. 2) (A~C 补题记录)
2021/4/17 10:25:16
本文主要是介绍Codeforces Round #715 (Div. 2) (A~C 补题记录),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
补题链接:Here
经典手速场
1509A. Average Height
题意:要找出最大不平衡对序列
先输出奇数,然后输出偶数
void solve() { int n; cin >> n; vector<int> odd, even; for (int i = 0, x; i < n; ++i) { cin >> x; if (x & 1) odd.push_back(x); else even.push_back(x); } for (int x : odd) cout << x << " "; for (int x : even) cout << x << " "; cout << "\n"; }
1509B. TMT Document
题意:给定一个 T
-M
字符串,求问是否能全拆分为 TMT
子序列
思路:
要能组成 TMT
就要是 T、M顺序一定并 cntT = 2 * cntM
和 \(n \% 3== 0\)
void solve() { int n; string s; cin >> n >> s; int ct = 0, cm = 0; bool f = true; for (int i = 0; f && i < n; ++i) { s[i] == 'T' ? ct++ : cm++; if (cm > ct || (ct > 2 * cm + n / 3 - cm)) f = false; } cout << (f && cm * 2 == ct && n % 3 == 0 ? "YES\n" : "NO\n"); }
1509C. The Sports Festival
题意:
学生会要参加接力赛,每位成员跑步速度为 \(a_i\) ,给定定义:
\[d_i = max(a_1,a_2,\dots,a_i) - min(a_1,a_2,\dots,a_i) \]求出最小的 \(\sum_{i = 1}^n d_i\)
思路:
待补。
using ll = long long; ll dp[2005][2005]; int n; int A[2005]; void solve() { cin >> n; for (int i = 1; i <= n; ++i) cin >> A[i]; sort(A + 1, A + n + 1); for (int i = 1; i <= n; ++i) for (int j = i + 1; j <= n; ++j) dp[i][j] = 1e18; for (int i = 1; i <= n; ++i) dp[i][i] = 0; for (int len = 1; len < n; ++len) { for (int i = 1; i + len - 1 <= n; ++i) { int j = i + len - 1; if (j < n) dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + A[j + 1] - A[i]); if (i > 1) dp[i - 1][j] = min(dp[i - 1][j], dp[i][j] + A[j] - A[i - 1]); } } cout << dp[1][n] << '\n'; }
另外一种写法
using ll = long long; void solve() { int n; cin >> n; vector<ll> s(n); for (ll &x : s) cin >> x; sort(s.begin(), s.end()); vector<ll> dp0(n), dp1(n); for (int k = 1; k < n; ++k) { for (int i = k; i < n; ++i) dp1[i] = min(dp0[i - 1], dp0[i]) + s[i] - s[i - k]; swap(dp0, dp1); } cout << dp0[n - 1] << '\n'; }
这篇关于Codeforces Round #715 (Div. 2) (A~C 补题记录)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升