What is the Codeforces Round #XXX problem set like?

本文共计1523个文字，预计阅读时间需要7分钟。

A. 将价格向下取整

AC代码示例def round_down_price(price): return int(price)

A. Round Down the Price AC代码

#include <bits/stdc++.h> #define IOS \ std::ios::sync_with_stdio(false); \ std::cin.tie(0); \ std::cout.tie(0); using PII = std::pair<int, int>; using ll = long long; void solve() { ll n, d = 0; std::cin >> n; for (ll m = n; m; m /= 10) ++d; ll x = (ll)pow(10, d - 1); std::cout << n - x << '\n'; } int main() { IOS; int t; std::cin >> t; while (t--) solve(); return 0; } B. Polycarp Writes a String from Memory AC代码

#include <bits/stdc++.h> #define IOS \ std::ios::sync_with_stdio(false); \ std::cin.tie(0); \ std::cout.tie(0); using PII = std::pair<int, int>; using ll = long long; ll solve() { ll res = 0; std::string s; std::cin >> s; int p = 0, n = s.length(); std::vector<int> hash(27); while (p < n) { int cnt = 0; while (p < n) { if (!hash[s[p] - 'a']) { ++cnt; if (cnt > 3) break; hash[s[p] - 'a'] = 1; } ++p; } ++res; std::fill(hash.begin(), hash.end(), 0); } return res; } int main() { IOS; int t; std::cin >> t; while (t--) std::cout << solve() << '\n'; return 0; } C. Train and Queries AC代码

#include <bits/stdc++.h> #define IOS \ std::ios::sync_with_stdio(false); \ std::cin.tie(0); \ std::cout.tie(0); using PII = std::pair<int, int>; using ll = long long; void solve() { int n, k; std::cin >> n >> k; std::vector<int> a(n + 1); for (int i = 1; i <= n; ++i) std::cin >> a[i]; std::map<int, int> fa, la; // first appear, last appear for (int i = 1; i <= n; ++i) { if (!fa.count(a[i])) fa[a[i]] = i; la[a[i]] = std::max(fa[a[i]], i); } for (int i = 1, u, v; i <= k; ++i) { std::cin >> u >> v; if (!fa.count(u) || !fa.count(v)) { std::cout << "No\n"; continue; } int st = fa[u], ed = la[v]; std::cout << (st < ed ? "Yes" : "No") << "\n"; } } int main() { IOS; int t; std::cin >> t; while (t--) solve(); return 0; } D. Not a Cheap String AC代码

#include <bits/stdc++.h> #define IOS \ std::ios::sync_with_stdio(false); \ std::cin.tie(0); \ std::cout.tie(0); using PII = std::pair<int, int>; using ll = long long; void solve() { std::string s; int p; std::cin >> s >> p; int n = s.length(); ll now = 0, x; std::vector<std::pair<char, int>> a(n + 1); for (int i = 1; i <= n; ++i) { a[i] = {s[i - 1], i}; now += (s[i - 1] - 'a' + 1); } std::sort(a.begin() + 1, a.begin() + n + 1); std::vector<bool> vis(n + 1); for (x = n; x && now > p; --x) { vis[a[x].second] = true; now -= (a[x].first - 'a' + 1); } std::sort(a.begin() + 1, a.begin() + n + 1, [&](std::pair<char, int> lft, std::pair<char, int> rht) { return lft.second < rht.second; }); std::string ans; for (int i = 1; i <= n; ++i) if (!vis[i]) ans.push_back(a[i].first); std::cout << ans << std::endl; } int main() { IOS; int t; std::cin >> t; while (t--) solve(); return 0; } E. Split Into Two Sets 题意

现有 \(n\) 张牌，每张包含 \(1 \sim n\) 的两个整数 \(a_i,b_i\) ，问能否将这 \(n\) 张牌分成两组，使每组中牌上的数均不相同。

题目分析

首先排除以下两种情况：

• 某张牌上的数字相同（即 \(a_i = b_i\) ）
• 存在两张以上的牌包含数 \(x\)

假设现在牌 \(i\) 和 \(j\) 包含数 \(x\) ，我们不妨在点 \(i\) 和点 \(j\) 之间连一条边，然后进行二分图染色判定即可。

AC代码

#include <bits/stdc++.h> #define IOS \ std::ios::sync_with_stdio(false); \ std::cin.tie(0); \ std::cout.tie(0); using PII = std::pair<int, int>; using ll = long long; void solve() { int n, isok = 1; std::cin >> n; std::vector<int> a(n + 1), b(n + 1); std::vector<std::vector<int>> e(n + 1), g(n + 1); for (int i = 1; i <= n; ++i) { std::cin >> a[i] >> b[i]; if (a[i] == b[i]) isok = 0; e[a[i]].push_back(i); e[b[i]].push_back(i); } for (int i = 1; i <= n; ++i) { if (e[i].size() > 2) { isok = 0; break; } if (e[i].size() == 2) { g[e[i][0]].push_back(e[i][1]); g[e[i][1]].push_back(e[i][0]); } } std::vector<int> v(n + 1, -1); std::function<void(int, int)> dfs = [&](int x, int col) { v[x] = col; for (auto y : g[x]) { if (v[y] == -1) dfs(y, col ^ 1); else if (v[y] == col) isok = 0; } }; for (int i = 1; i <= n; ++i) if (v[i] == -1) dfs(i, 1); std::cout << (isok ? "YES\n" : "NO\n"); } int main() { IOS; int t; std::cin >> t; while (t--) solve(); return 0; } G1. Passable Paths (easy version) 题意

定义一个点集为可连通的，当且仅当树上存在某条路径穿过这组顶点，而不经过任何一条边两次（这条路径可以访问该点集外的其它顶点）。

\(q\) 次询问。每次询问某个点集是否为可连通的。

题目分析

观察到简单版本的 \(q\) 很小，先预处理出每个点的父节点与深度， 对每个询问将点集放优先队列中按深度排序，然后不断往上爬，同时记录父节点的子节点数，如果父节点不在队列中就入队。如果最后的根节点的子节点数 \(> 2\) 或是其它节点的子节点数 \(\geq 2\) 则说明不连通，否则连通。

AC代码

#include <bits/stdc++.h> #define IOS \ std::ios::sync_with_stdio(false); \ std::cin.tie(0); \ std::cout.tie(0); using PII = std::pair<int, int>; using ll = long long; int main() { IOS; int n; std::cin >> n; std::vector<std::vector<int>> g(n + 1); std::vector<int> dep(n + 1), pa(n + 1); for (int i = 1, u, v; i < n; ++i) { std::cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } std::function<void(int, int)> getDepth = [&](int u, int fa) { pa[u] = fa, dep[u] = dep[fa] + 1; for (auto v : g[u]) if (v != fa) getDepth(v, u); }; auto solve = [&]() { int k; std::cin >> k; std::vector<int> inq(n + 1), son(n + 1); std::priority_queue<PII, std::vector<PII>> q; for (int i = 1, x; i <= k; ++i) { std::cin >> x; inq[x] = 1; q.push({dep[x], x}); } while (q.size() > 1) { PII t = q.top(); q.pop(); int u = t.second, d = t.first; if (son[u] > 1) return false; int fa = pa[u]; son[fa] += 1; if (inq[fa]) continue; inq[fa] = true; q.push({dep[fa], fa}); } PII t = q.top(); q.pop(); int u = t.second, d = t.first; if (son[u] <= 2) return true; return false; }; getDepth(1, 0); int q; std::cin >> q; while (q--) std::cout << (solve() ? "YES\n" : "NO\n"); return 0; }