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

Codeforces Round 1098 (Div. 2)

news 2026/5/22 7:03:59

A. Marisa Steals Reimu's Takeout

Marisa Steals Reimu's Takeouthttps://codeforces.com/contest/2228/problem/A

贪心计算

统计数组中 0、1、2 三种数字的个数，然后按照以下规则计算最大“可配对或合并”的数量：

每个 0 本身就是一个“独立有效项”，直接全部计入结果res（res = t[0]）。
1 和 2 可以两两配对（一个 1 加一个 2 形成一组），取它们数量的较小值加给res，并把配对的那些从t[1]和t[2]中减去。
剩下的 1 或 2（哪种还有剩余）每 3 个相同的数字可以形成一组（比如三个 1 或三个 2），每组再加到res中。

#include <iostream> #include <vector> #include <set> #include <functional> #include <algorithm> #define int long long #define forn(i,n) for(int i = 0;i < (int)n;i++) #define endl "\n" using namespace std; void solve(); signed main() { int T; cin >> T; while (T--)solve(); return 0; } void solve() { int n; cin >> n; vector<int> arr(n); for (auto& e : arr)cin >> e; int t[3] = { 0,0,0 }; for (auto e : arr)t[e]++; int res = t[0]; int m = min(t[1], t[2]); res += min(t[1], t[2]); t[1] -= m; t[2] -= m; res += t[1] / 3; res += t[2] / 3; cout << res << endl; }

B. Remilia Plays Soku

Remilia Plays Sokuhttps://codeforces.com/contest/2228/problem/B

先计算环上两点 x1 和 x2 的最短距离 d0，若总点数 n ≤ 3 则直接输出 1，否则输出 d0 + k。

#include <iostream> #include <vector> #include <set> #include <functional> #include <algorithm> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { long long n, x1, x2, k; cin >> n >> x1 >> x2 >> k; long long d0 = min(abs(x1 - x2), n - abs(x1 - x2)); if (n <= 3) { cout << 1 << "\n"; } else { cout << d0 + k << "\n"; } } return 0; }

C1. Cirno and Number (Easy Version)

Cirno and Number (Easy Version)https://codeforces.com/contest/2228/problem/C1

他和后面的hard版本都是一个思路，就是找到大于他的最小的数和找到小于他最大的数字

但是这个版本只有两个数字，所以会更好些一些

设置两个字符里面大的为a,小的为b，设置t为str[i] - '0'

找到比他小的数字的最大的一个，对于t来说t>=a>b 放a 如果t > a后面全部放a

a>t>=b直接使用b 如果t > b后面全部放a

a>b>t就回溯到上一个放a的位置设置b后面全部设置a

找到比他大的数字的最小的一个，对于t来说a>b>=t 放b 如果 t > b后面全部放b

a>=t>b 放a 如果 t > a后面全部放b

t>a>b就回溯到上一个放b的位置设置a后面全部设置b

之后比较两个差值的绝对值

#include <iostream> #include <string> #include <algorithm> #include <climits> using namespace std; using ull = unsigned long long; string find_le(const string& s, char small, char large) { int sm = small - '0'; int lg = large - '0'; int n = s.size(); string res(n, ' '); bool equal_prefix = true; for (int i = 0; i < n; ++i) { int d = s[i] - '0'; if (!equal_prefix) { res[i] = large; } else { if (d >= lg) { res[i] = large; if (lg < d) equal_prefix = false; } else if (d >= sm) { res[i] = small; if (sm < d) equal_prefix = false; } else { int j = i - 1; while (j >= 0) { if (res[j] == large) { res[j] = small; for (int k = j + 1; k < n; ++k) res[k] = large; return res; } --j; } return ""; } } } return res; } string find_ge(const string& s, char small, char large) { int sm = small - '0'; int lg = large - '0'; int n = s.size(); string res(n, ' '); bool equal_prefix = true; for (int i = 0; i < n; ++i) { int d = s[i] - '0'; if (!equal_prefix) { res[i] = small; } else { if (d <= sm) { res[i] = small; if (sm > d) equal_prefix = false; } else if (d <= lg) { res[i] = large; if (lg > d) equal_prefix = false; } else { int j = i - 1; while (j >= 0) { if (res[j] == small) { res[j] = large; for (int k = j + 1; k < n; ++k) res[k] = small; return res; } --j; } return ""; } } } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { ull a; int n; cin >> a >> n; int d1, d2; cin >> d1 >> d2; if (d1 > d2) swap(d1, d2); char small = char('0' + d1); char large = char('0' + d2); if (a == 0) { if (d1 == 0) cout << "0\n"; else cout << d1 << "\n"; continue; } string s = to_string(a); int len = s.size(); ull ans = ULLONG_MAX; if (d1 == 0) ans = min(ans, a); if (len > 1) { string short_str(len - 1, large); ull b_short = stoull(short_str); ans = min(ans, a - b_short); } char first = (d1 > 0) ? small : large; string long_str = first + string(len, small); ull b_long = stoull(long_str); ans = min(ans, b_long - a); string le_str = find_le(s, small, large); if (!le_str.empty()) { ull b_le = stoull(le_str); ans = min(ans, a - b_le); } string ge_str = find_ge(s, small, large); if (!ge_str.empty()) { ull b_ge = stoull(ge_str); ans = min(ans, b_ge - a); } cout << ans << "\n"; } return 0; }

C2. Cirno and Number (Hard Version)

Cirno and Number (Hard Version)https://codeforces.com/contest/2228/problem/C2

这个题目和上一个思路基本一直只不过多了几个数，其实只需要管和str[i] - '0'比他大的最小数和比他小的最大数字就行，用二分找一下就行

#include <iostream> #include <vector> #include <set> #include <functional> #include <algorithm> #include <string> using namespace std; using ull = unsigned long long; string find_le(const string& s, const vector<int>& dig) { int len = s.size(); int max_d = dig.back(), min_d = dig[0]; string res(len, ' '); bool tight = true; for (int i = 0; i < len; i++) { int d = s[i] - '0'; if (!tight) { res[i] = '0' + max_d; } else { auto it = upper_bound(dig.begin(), dig.end(), d); if (it != dig.begin()) { --it; res[i] = '0' + *it; if (*it < d) tight = false; } else { int j = i - 1; while (j >= 0) { int cur = res[j] - '0'; auto iter = lower_bound(dig.begin(), dig.end(), cur); if (iter != dig.begin()) { --iter; res[j] = '0' + *iter; tight = false; for (int k = j + 1; k < len; k++) res[k] = '0' + max_d; return res; } --j; } return ""; } } } return res; } string find_ge(const string& s, const vector<int>& dig) { int len = s.size(); int max_d = dig.back(), min_d = dig[0]; string res(len, ' '); bool tight = true; for (int i = 0; i < len; i++) { int d = s[i] - '0'; if (!tight) { res[i] = '0' + min_d; } else { auto it = lower_bound(dig.begin(), dig.end(), d); if (it != dig.end()) { res[i] = '0' + *it; if (*it > d) tight = false; } else { int j = i - 1; while (j >= 0) { int cur = res[j] - '0'; auto iter = upper_bound(dig.begin(), dig.end(), cur); if (iter != dig.end()) { res[j] = '0' + *iter; tight = false; for (int k = j + 1; k < len; k++) res[k] = '0' + min_d; return res; } --j; } return ""; } } } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { ull a; int n; cin >> a >> n; vector<int> dig(n); for (int i = 0; i < n; i++) cin >> dig[i]; sort(dig.begin(), dig.end()); int min_d = dig[0], max_d = dig.back(); if (a == 0) { cout << (min_d == 0 ? 0 : min_d) << "\n"; continue; } string s = to_string(a); int len = s.size(); ull ans = ULLONG_MAX; if (min_d == 0) ans = min(ans, a); if (len > 1) { string short_str(len - 1, '0' + max_d); if (short_str[0] != '0' || len - 1 == 1) { ans = min(ans, a - stoull(short_str)); } } { int first_d = -1; for (int d : dig) if (d > 0) { first_d = d; break; } if (first_d == -1) first_d = 0; string long_str = to_string(first_d) + string(len, '0' + min_d); ans = min(ans, stoull(long_str) - a); } string le = find_le(s, dig); if (!le.empty()) ans = min(ans, a - stoull(le)); string ge = find_ge(s, dig); if (!ge.empty()) ans = min(ans, stoull(ge) - a); cout << ans << "\n"; } return 0; }

查看全文

http://www.jsqmd.com/news/862868/