Codeforces Round 1098 (Div. 2)

A. Marisa Steals Reimus TakeoutMarisa Steals Reimus Takeouthttps://codeforces.com/contest/2228/problem/A贪心计算统计数组中 0、1、2 三种数字的个数然后按照以下规则计算最大“可配对或合并”的数量每个 0 本身就是一个“独立有效项”直接全部计入结果resres 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; vectorint 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 SokuRemilia 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来说tab 放a 如果t a后面全部放aatb直接使用b 如果t b后面全部放aabt就回溯到上一个放a的位置设置b后面全部设置a找到比他大的数字的最小的一个对于t来说abt 放b 如果 t b后面全部放batb 放a 如果 t a后面全部放btab就回溯到上一个放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 vectorint 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 vectorint 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; vectorint 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; }