Greedy

Canine poetry tutorial 观察长度为偶数的回文字符串，只需要把中间两个字符破坏掉就可以了。长度为奇数的回文串只需要把中间三个字符组成的回文破坏掉。所以只需要考虑长度为 2 和 3 的回文。对于当前字符 $a_i$，只需要检查 $a_{i - 1}, a_i$ 和 $a_{i - 2}, a_{i - 1}, a_i$ 是否是回文，如果是回文，在 $i$ 这个位置打一个标记。 // Date: Sun Dec 17 22:51:25 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) template <typename t> istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif int t; string s; int main(void) { #ifdef _DEBUG freopen("1466c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> s; int n = SZ(s), res{}; For(i, 1, n) { if (s[i] == s[i - 1] && s[i - 1] != '-') { s[i] = '-'; res++; } else if (i - 2 >= 0 && s[i] == s[i - 2] && s[i - 2] != '-') { s[i] = '-'; res++; } } cout << res << '\n'; } return 0; }

Strange Birthday Party tutorial 设最优答案中 $k_i$ 和 $k_j$ 收到的礼物价值为 $c_i$ 和 $c_j$，并且 $k_i > k_j, c_i > c_j$。此时把 $c_j$ 给 $k_i$，如果 $c_i > c_{k_j}$，此时 $k_j$ 收到 $c_{k_j}$ 美元，答案更优；如果 $c_i < c_{k_j}$，答案不变。因此把礼物价值小的给尽量大的 $k_i$ 是更优策略。所以按照 $k_i$ 从大到小排序依次送礼物，如果当前礼物下标 $j$ 大于 $c_{k_i}$，此时这个人应该收到 $c_{k_i}$ 的美元，因为此时 $c_{k_i} < c_j$。 // Date: Sun Dec 17 21:46:52 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define all1(a, n) a + 1, a + 1 + n #define SZ(a) int((a).size()) template <typename t> istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 300010; int k[N], c[N], t, n, m; int main(void) { #ifdef _DEBUG freopen("1470a.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> m; For1(i, 1, n) cin >> k[i]; sort(all1(k, n), greater<int>()); For1(i, 1, m) cin >> c[i]; ll res = 0; int j = 1; For1(i, 1, n) { if (j < k[i]) { res += c[j++]; if (j > m) j = m; } else { res += c[k[i]]; } } cout << res << '\n'; } return 0; }

Get an Even String 对于中间未成对的字母，当找到一个成对的之后，当前遇到的未成对的全部删除，开始找下一对，这样是最优的。 // Date: Sat Dec 16 22:14:35 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 200010; int t; string s; int main(void) { #ifdef _DEBUG freopen("1660c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> s; bool vis[26]{false}; int res = 0; int n = SZ(s); For(i, 0, n) { int idx = s[i] - 'a'; if (vis[idx]) { For(j, 0, 26) { if (j == idx) continue; else if (vis[j]) res++; } memset(vis, false, sizeof vis); } else { vis[idx] = true; } } For(j, 0, 26) { if (vis[j]) res++; } cout << res << '\n'; } return 0; }

Getting Zero tutorial 由于 $32768 = 2^{15}$，所以答案的上界是 15，猜想先对数字进行加，然后再乘，这样是最优的。假设某次乘操作之后，进行了两次加：$v \to 2v \to 2v + 1 \to 2v + 2$，此时可以替换成 $v \to v + 1 \to 2v + 2$，也就是乘操作之后，不能进行连续的两次加。乘操作之后再紧接着进行一次加操作不是最优的，因为我们得到的数字需要被 $2^{15}$ 整除，加操作破坏了整除性。因此只能先进行连续的加操作，然后是连续的乘操作。设加操作次数是 $i$，乘操作次数是 $j$，那么有 $(x + i) \times 2^{j} \bmod 2^{15} = 0$，$i, j \le 15$。 // Date: Sat Dec 16 20:56:23 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 400010, M = 32768; int bfs(int x) { int res = 15; For1(i, 0, 15) { For1(j, 0, 15) { ll tmp = (x + i) * (1 << j) % M; if (tmp == 0) { res = min(res, i + j); } } } return res; } int a[N], b[N]; int main(void) { #ifdef _DEBUG freopen("1661b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; while (cin >> n) { For1(i, 1, n) { cin >> a[i]; } For1(i, 1, n) { b[i] = bfs(a[i]); } For1(i, 1, n) { cout << b[i] << ' '; } cout << '\n'; } return 0; }

Game with Reversing 可以观察到 Bob 操作的奇偶性，如果 Bob 操作奇数次，那么两个字符串使用逆序比较；如果 Bob 操作偶数次，那么两个字符串使用正序比较。Alice 和 Bob 轮流操作，Alice 先操作，只需要统计正序比较和逆序比较两个字符串不同字符的个数，确定 Alice 的操作次数，然后再根据奇偶性确定 Bob 操作次数。 // Date: Sat Dec 16 08:36:02 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif int tc, n; string s, t; int main(void) { #ifdef _DEBUG freopen("1834c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> tc; while (tc--) { cin >> n >> s >> t; int cnt = 0, cnt1 = 0; For(i, 0, n) { if (s[i] != t[i]) cnt++; } for (int i = 0, j = n - 1; i < n; i++, j--) { if (s[i] != t[j]) cnt1++; } int res = INF; if (cnt & 1) { if (cnt > 0) res = min(res, cnt - 1 + cnt); } else { res = min(res, cnt + cnt); } if (cnt1 & 1) { res = min(res, cnt1 + cnt1); } else { if (cnt1 > 0) res = min(res, cnt1 - 1 + cnt1); else res = min(res, 2); } cout << res << '\n'; } return 0; }

Social Distance 从左往右扫描维护上一次遇到 $1$ 的位置，如果当前位置 $i$ 是 $0$，并且距离上一次 $1$ 的位置 $pre$ 的距离大于 $k$ 那么这个点可能是可行的，如果后面的 $1$ 和 $i$ 的距离不大于 $k$，再把 $k$ 点变成不可行的，这样找到的可行的点都是尽量靠左的。 // Date: Tue Dec 12 23:08:09 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 200010; int t, n, k; string s; bool vis[N]; int main(void) { #ifdef _DEBUG freopen("1367c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> k >> s; memset(vis, false, sizeof vis); int pre = -1; For(i, 0, n) { if (s[i] == '1') { if (pre != -1 && i - pre <= k) { vis[pre] = false; } pre = i; } else { if (pre == -1 || i - pre > k) { vis[i] = true; pre = i; } } } int res{}; For(i, 0, n) { if (vis[i]) res++; } cout << res << '\n'; } return 0; }

Knapsack How to get started with solving Ad-Hoc tasks on codeforces 一道挺有意思的题目，思路推荐上面的博客。 要在数组中找到一些数字，使得它们的和在范围 $[\frac{w}{2}, w]$ 内。首先把 $a_i > w$ 的数字去掉；如果某个数字就在给定的范围内，那么它就是一个解。接下来只需要考虑所有 $a_i < \frac{w}{2}$ 的数字，可以先排序，从小到大考虑累加，如果前缀和能到 $[\frac{w}{2}, w]$ 范围内，那么这个前缀就是一个解。 为什么这么做是对的呢？假设 $a_i + a_{i + 1} \lt \frac{w}{2}$，同时 $a_i + a_{i + 1} + a_{i + 2} > w$，可以得到 $a_{i + 2} > \frac{w}{2}$，这和 $a_{i+2} < \frac{w}{2}$ 矛盾。 // Date: Mon Dec 11 21:10:36 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 200010; int t, n; pair<ll, int> a[N], b[N]; ll w; int main(void) { #ifdef _DEBUG freopen("1446a.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> w; For1(i, 1, n) { cin >> a[i].f1; a[i].f2 = i; } int len = 0; sort(a + 1, a + n + 1); ll top = (w + 1) / 2; VI res; For1(i, 1, n) { if (a[i].f1 > w) continue; if (a[i].f1 <= w && a[i].f1 >= top) { res.pb(a[i].f2); break; } b[++len] = a[i]; } if (nonempty(res)) { cout << SZ(res) << '\n'; for (auto x : res) { cout << x << ' '; } cout << '\n'; continue; } bool flag = false; ll sum = 0, right = -1; For1(i, 1, len) { sum += b[i].f1; if (sum <= w && sum >= top) { flag = true; right = i; break; } } if (!flag) cout << "-1\n"; else { cout << right << '\n'; using PLI = pair<ll, int>; sort(b + 1, b + right + 1, [&](const PLI &x, const PLI &y) { return x.f2 < y.f2; }); For1(i, 1, right) { cout << b[i].f2 << ' '; } cout << '\n'; } } return 0; }

Box Fitting 对于每一行，从大到小放是收益最大的。由于每个矩形的长度都是 2 的幂，所以从大到小循环 2 的幂即可，直到把所有的矩形都放完。 // Date: Sun Dec 10 12:25:53 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 100010; int t, n, w, a[N]; int main(void) { #ifdef _DEBUG freopen("1498b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> w; map<int, int> m; For1(i, 1, n) { cin >> a[i]; m[a[i]]++; } int res = 0; while (nonempty(m)) { res++; int rem = w; int len = SZ(m); Rof1(i, 0, 31) { int x = (1 << i); if (!rem) break; if (!has(m, x) || rem < x) continue; int cnt = m[x]; int hold = rem / x; if (hold >= cnt) { m.erase(x); rem -= cnt * x; } else { m[x] -= hold; if (!m[x]) m.erase(x); rem -= hold * x; } } } cout << res << '\n'; } return 0; }

Longest Strike 找到符合要求的数字，排序之后寻找最长连续的子数组。注意考虑长度是 1 的边界情况。 // Date: Sun Dec 10 11:26:31 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 200010; int a[N], t, n, k; int main(void) { #ifdef _DEBUG freopen("1676f.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> k; map<int, int> m; For1(i, 1, n) { cin >> a[i]; m[a[i]]++; } VI b; for (auto &[x, y] : m) { if (y >= k) b.pb(x); } sort(all(b)); int len = SZ(b); if (!len) { cout << "-1\n"; continue; } int res = 1, cur = 0, l = 0, r = -1; int resl = b[0], resr = b[0]; For(i, 1, len) { if (b[i] == b[i - 1] + 1) { r = i; cur = r - l + 1; if (cur > res) { res = cur; resl = b[l]; resr = b[r]; } } else { l = i; } } if (res != 0) { cout << resl << ' ' << resr << '\n'; } else { cout << "-1\n"; } } return 0; }

Olya and Game with Arrays tutorial 一道有趣的题目。因为只能从每个数组中拿出一个数字，所以每个数组有用的数字只有从小到大排序之后的前两个数字。另外一个性质是：如果往一个数组里面加入数字，那么这个数组的贡献不会变大。当从一个数组中取出一个数字之后，这个数字并不会消失，它会出现在其它数组中，也就是说所有数组的最小值最终一定会贡献给最终答案。综合这几点，就可以发现，我们可以把从每个数组中取出的数字放到同一个数组 $A$ 中，这个数组的最终贡献就是所有数组的最小值。剩下的数组的贡献是原先每个数组的第二小的值。由于数组 $A$ 的贡献是固定的，要让最终的结果最大，只需要让 $A$ 等于所有数组中第二小的值最小。 // Date: Sat Dec 9 21:17:37 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 50010; int t, n; PII a[N]; int main(void) { #ifdef _DEBUG freopen("1859b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; int cnt, mb = 1e9 + 10; For1(i, 1, n) { cin >> cnt; VI tmp(cnt, 0); For(j, 0, cnt) { cin >> tmp[j]; } sort(all(tmp)); a[i].f1 = tmp[0]; a[i].f2 = tmp[1]; mb = min(mb, a[i].f1); } sort(a + 1, a + n + 1, [&](const PII &x, const PII &y) { if (x.f2 < y.f2) return true; else if (x.f2 > y.f2) return false; return x.f1 < y.f1; }); ll res = mb; For1(i, 2, n) { res += a[i].f2; } cout << res << '\n'; } return 0; }

Hamon Odyssey 很有意思的一道题。要求分组之后的和最小，同时，分组的个数要尽量多。首先发现如果某一组的强度是 $0$，那么所有组的强度之后最坏应该是 $0$（因为此时所有元素的按位与一定是 $0$）。又要求分组尽量多，所以就需要找到尽量多的子数组，使得这个子数组的按位与是 $0$，对于其中剩下的那些按位与不是 $0$ 的元素，把它们分到相邻的任意一个合法的组即可。如果找不到任何一个组的强度是 $0$，那么最终的解是整个数组，因为任何一个子数组的强度都是正数，分开之后强度和会更大。 // Date: Sat Dec 9 20:25:47 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 200010; int t, a[N], n; int main(void) { #ifdef _DEBUG freopen("1847b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; For1(i, 1, n) { cin >> a[i]; } int res = 0; ll cur = 0; bool flag = true; For1(i, 1, n) { if (flag) { cur = a[i]; flag = false; } else { cur = cur & a[i]; } if (cur == 0) { res++; flag = true; } } if (!res) res = 1; cout << res << '\n'; } return 0; }

Best Binary String tutorial 选择任意一个区间逆序是一个操作。 从后往前扫描，后缀的 $?$ 可以全部替换成 $1$ 如果遇到 $0$，那么可能会需要一次操作（如果 $0$ 的前面都是 $0$ 或者 $?$，那么就不需要） $0$ 之后紧接的 $?$ 可以替换成 $0$，这样结果不会更差 如果遇到 $1$，那么就找到了这次操作的左端，同时 $1$ 左边紧接的 $1$ 可以算作一次操作，如果遇到 $?$ 那么可以替换成 $1$ 之后再遇到 $0$ 就是新的一轮操作 // Date: Sat Dec 9 16:41:32 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 300010; int t, d0[N], d1[N]; string s; int main(void) { #ifdef _DEBUG freopen("1837c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> s; int n = SZ(s), cnt = 0; For(i, 0, n) { if (s[i] == '?') cnt++; } if (!cnt) { cout << s << '\n'; continue; } bool flag = false; Rof(i, 0, n) { if (s[i] == '?') { if (!flag) s[i] = '1'; else { s[i] = '0'; } } else if (s[i] == '1') { if (!flag) continue; else { flag = false; } } else { if (!flag) flag = true; } } cout << s << '\n'; } return 0; }

Astrophysicists tutorial 观察可以发现可以让前面的 $n - 1$ 个人每人的分配数量是 $\frac{g - 1}{2}$，这样前面 $n-1$ 个人什么都得不到。剩下的硬币全部给一个人，判断余数即可。 // Date: Fri Dec 8 21:06:31 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif ll t, n, k, g; int main(void) { #ifdef _DEBUG freopen("1836b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> k >> g; ll res = 0, tot = k * g, sum = 0, x; if (g & 1) { x = g / 2; } else { x = g / 2 - 1; } For(i, 1, n) { sum += x; res += x; } if (sum >= tot) { cout << tot << '\n'; continue; } ll v = (tot - sum) % g; if (v <= x) { res += v; } else { res -= (g - v); } cout << res << '\n'; } return 0; }

Maximum Strength 按位考虑，从高位到低位找到第一个不相同的位置，这个位置的贡献是 $abs(a[i] - b[i])$，其它位置的贡献都是 9。 // Date: Fri Dec 8 20:34:42 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif int t; int main(void) { #ifdef _DEBUG freopen("1834b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { string a, b; cin >> a >> b; int lena = SZ(a), lenb = SZ(b), res = 0; if (lena == lenb) { int idx = -1, len = 0; For(i, 0, lena) { if (a[i] != b[i]) { idx = i; len = lena - (idx + 1); break; } } if (idx != -1) res = 9 * len + abs(a[idx] - b[idx]); } else { res = 9 * (lenb - 1) + abs(b[0] - '0'); } cout << res << '\n'; } return 0; }

Sort the Subarray 先从两侧确定最小的左右边界，然后对 $b$ 数组，在保证有序的情况下，向两边扩展得到最大的左右边界。 // Date: Fri Dec 8 20:00:02 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 200010; int n, a[N], b[N], t; int main(void) { #ifdef _DEBUG freopen("1821b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; For1(i, 1, n) { cin >> a[i]; } For1(i, 1, n) { cin >> b[i]; } int l = 1, r = n; For1(i, 1, n) { if (a[i] != b[i]) { l = i; break; } } Rof1(i, 1, n) { if (a[i] != b[i]) { r = i; break; } } while (l > 1 && b[l - 1] <= b[l]) --l; while (r < n && b[r + 1] >= b[r]) ++r; cout << l << ' ' << r << '\n'; } return 0; }