CodeForces

Add, Divide and Floor tutorial 因为操作不会影响元素的顺序，所以可以把数组排序，经过一系列操作，使得最小值和最大值相等。设最小值和最大值分别是 $a, b$，考虑 $b - a$ 的值经过一次操作后的变化 $\lfloor\frac{b + x}{2}\rfloor - \lfloor \frac{a + x}{2} \rfloor$，枚举 $a, b$ 的奇偶性，观察发现 $b - a$ 最好情况下变成 $\frac{b - a}{2}$，当 $a$ 为奇数时，令 $x = 1$，否则令 $x = 0$。 // Date: Mon Dec 25 23:28:12 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 const int N = 200010; int t, n, a[N]; int main(void) { #ifdef _DEBUG freopen("1901c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; int miv = INF, mav = -INF; For1(i, 1, n) { cin >> a[i]; miv = min(miv, a[i]); mav = max(mav, a[i]); } VI res; while (miv != mav) { if (miv & 1) { res.pb(1); miv = (miv + 1) / 2; mav = (mav + 1) / 2; } else { res.pb(0); miv /= 2; mav /= 2; } } int len = SZ(res); cout << len << '\n'; if (len <= n && len) { cout << res << '\n'; } } return 0; }

Minimax Problem tutorial 要求数组 $b$ 的最小值最大，考虑二分，可以对 $min_{k = 1}^m b_k$ 进行二分，对于 $x$，判定是否存在两个数组 $a_i, a_j$，使得它们组成的数组 $b$ 中的所有的值都 $\ge x$，数组 $a_i$ 的个数有 $3 \cdot 10^5$ 个，但是长度只有 $8$，可以想到用二进制表示数组 $a_i$，当 $a_{i,k} \ge x$ 时，对应的二进制位为 1。这样数组 $a_i$ 最多只有 $2^8$ 个，因此一次判定操作的复杂度是 $O(n \cdot 8 + (2^8)^{2})$ // Date: Sun Dec 24 09:26:26 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 const int N = 3000'10, M = 10; int n, m, a[N][M]; PII check(int x) { set<int> s; map<int, int> b2i; For1(i, 1, n) { int tmp = 0, base = 1; For1(j, 1, m) { if (a[i][j] < x) { } else { tmp += base; } base <<= 1; } s.insert(tmp); b2i[tmp] = i; } for (auto x : s) { for (auto y : s) { int z = (x | y); if (z == ((1 << m) - 1)) { return {b2i[x], b2i[y]}; } } } return {-1, -1}; } int main(void) { #ifdef _DEBUG freopen("1288d.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); while (cin >> n >> m) { For1(i, 1, n) { For1(j, 1, m) { cin >> a[i][j]; } } int l = 0, r = 1e9 + 10, mid; while (l < r) { mid = (l + r + 1) / 2; if (check(mid) != PII{-1, -1}) l = mid; else r = mid - 1; } auto res = check(l); cout << res.f1 << ' ' << res.f2 << '\n'; } return 0; }

Theofanis’ Nightmare tutorial 假设数组分成 3 组，每组的和分别是 $c_1, c_2, c_3$，那么有： $$\begin{equation} ans = 1 \cdot c_1 + 2\cdot c_2 + 3 \cdot c_3 \ = (c_3 + c_2 + c_1) + (c_3 + c_2) + (c_3) \end{equation}$$ 可以发现是后缀和的形式，要使得总和最大，只需要把后缀和为正的累加起来即可。 // Date: Sat Dec 23 16:21:56 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 const int N = 100010; int t, n, a[N]; ll p[N]; int main(void) { #ifdef _DEBUG freopen("1903c.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]; memset(p, 0, sizeof p); Rof1(i, 1, n) p[i] = p[i + 1] + a[i]; ll ans = p[1]; For1(i, 2, n) { if (p[i] > 0) { ans += p[i]; } } cout << ans << '\n'; } return 0; }

3SUM Closure tutorial 数组中的元素顺序无关，所以可以把数组先排序。容易注意到当存在 3 个正数时，此时不满足闭合：取数组中三个最大的正数相加，结果大于数组中的所有元素。同理，当数组中存在 3 个负数时，也不满足闭合。接下来考虑 0 的情况。因此满足题意的数组中正数或负数不超过 2 个， 当 $a_i, a_j, a_k$ 全部都是 0 的时候，这个三元组满足题意。当其中存在 2 个 0 的时候，也满足题意。因此 $\ge 2$ 个的数字 0 并不会破坏闭合性。只需要考虑数组中存在 1 个 0 即可。 因此需要考虑的数组长度最长只有 5，循环找出所有的三元组逐个判别即可。 // Date: Sat Dec 23 15:48: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()) 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 = 200010; int t, n, a[N]; int main(void) { #ifdef _DEBUG freopen("1698c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; int cnt0{}, cnt1{}, cnt2{}; VI b; bool flag = true; For1(i, 1, n) { cin >> a[i]; if (a[i] == 0) { if (!cnt0) { cnt0++; b.pb(a[i]); } } else if (a[i] > 0) { cnt1++; if (cnt1 >= 3) { flag = false; } else { b.pb(a[i]); } } else { cnt2++; if (cnt2 >= 3) { flag = false; } else { b.pb(a[i]); } } } if (!flag) { cout << "NO\n"; continue; } int len = SZ(b); set<int> s(all(b)); For(i, 0, len) { if (!flag) break; For(j, i + 1, len) { if (!flag) break; For(k, j + 1, len) { int tmp = b[i] + b[j] + b[k]; if (!has(s, tmp)) { flag = false; break; } } } } cout << (flag ? "YES" : "NO") << '\n'; } return 0; }

Good Subarrays (Easy Version) tutorial 因为要求的好子数组是连续的，设 $d_i$ 表示以 $a_i$ 结尾的最长好数组的长度。当 $a_i \ge d_{i - 1} + 1$ 时，有 $d_i = d_{i - 1} + 1$。当 $a_i \lt d_{i - 1} + 1$ 时，注意到 $a_i \le d_{i - 1}$，并且以 $a_i$ 结尾的好数组的最大长度不能超过 $a_i$，这要求 $a_i$ 前面要有长度为 $a_i - 1$ 的好数组，此时恰好有 $a_i - 1 \lt a_i \le d_{i - 1}$，也就是 $a_i$ 前面必定有长度为 $a_i - 1$ 的好数组，所以此时 $d_i = a_i$。答案就是 $\sum_{i = 1}^n d_i$ // Date: Fri Dec 22 22:36:16 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 const int N = 200010; int t, n, a[N], d[N]; int main(void) { #ifdef _DEBUG freopen("1736c1.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; // TLE // memset(d, 0, sizeof d); For1(i, 1, n) cin >> a[i]; ll res = 0; d[0] = 0; For1(i, 1, n) { if (a[i] >= d[i - 1] + 1) { d[i] = d[i - 1] + 1; } else { d[i] = a[i]; } res += d[i]; } cout << res << '\n'; } return 0; }

Masha and a Beautiful Tree 经典的分治问题，记录区间的左右端点和区间范围即可。找到一个分支无解之后，及时退出。 // Date: Fri Dec 22 22:12: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()) 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 t, n, a[N]; ll res; void dfs(int l, int r, int vl, int vr) { if (l >= r) return; if (res == -1) return; if (l + 1 == r) { if (a[l] > a[r]) { res++; swap(a[l], a[r]); } if (PII{vl, vr} != PII{a[l], a[r]}) { res = -1; } return; } int mid = (l + r) / 2, vmid = (vl + vr) / 2; if (a[l] >= vl && a[l] <= vmid) { dfs(l, mid, vl, vmid); dfs(mid + 1, r, vmid + 1, vr); } else { res++; dfs(l, mid, vmid + 1, vr); dfs(mid + 1, r, vl, vmid); } } int main(void) { #ifdef _DEBUG freopen("1741d.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]; res = 0; dfs(1, n, 1, n); cout << res << '\n'; } return 0; }

Beppa and SwerChat 对于 $a$ 中的每个元素 $a_i$，找到它在 $b$ 中的位置 $j$，如果 $j \ne i$，那么说明 $b_j$ 前面的人曾经来过，也就是至少 $j - 1$ 个人曾经来过，对于这 $j - 1$ 个人，需要在数组 $a$ 中跳过。在数组 $a$ 中跳过这 $j - 1$ 个人之后，检查 $b_j$ 之后的元素是否相对顺序在 $a$ 中不变，如果相对顺序改变了，更新答案。 // Date: Fri Dec 22 21:36:24 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 const int N = 100010; int n, a[N], b[N], t; bool vis[N]; int main(void) { #ifdef _DEBUG freopen("1776h.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; memset(vis, false, sizeof vis); For1(i, 1, n) cin >> a[i]; For1(i, 1, n) cin >> b[i]; int res = 0; for (int i = 1, j = 1, j1 = 1; i <= n; ++i) { if (vis[a[i]]) continue; while (j <= n && b[j] != a[i]) { vis[b[j]] = true; ++j; } if (j <= n) { if (j > j1) { res = j - 1; } j1 = ++j; } } cout << res << '\n'; } return 0; }

Cake Assembly Line tutorial 题意需要满足如下条件： $$ a_i + w \ge b_i + h \ a_i - w \le b_i - h $$ 也就是 $b_i + h - w \le a_i \le b_i - h + w$，设传送带移动距离是 $p$，那么应该满足 $b_i + h - w \le a_i + p \le b_i - h + w$，可以得到 $b_i + h - w - a_i \le p \le b_i - h + w - a_i$，对于所有的 $i$ 都成立，只需要让左边的最大值 $\le$ 右边的最小值。 ...

Forever Winter tutorial 统计每个点的度数，难点在于边界条件。 degree count $x$ 1 1 $xy$ $y+1$ $x$ 边界条件是 $x = y + 1$ // Date: Fri Dec 22 12:15:15 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 const int N = 210, M = 50010; int t, n, m, h[N], d[N]; int idx, e[M], ne[M]; void Init() { idx = 0; memset(d, 0, sizeof d); memset(h, -1, sizeof h); } void Add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } int main(void) { #ifdef _DEBUG freopen("1829f.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> m; Init(); For(i, 0, m) { int x, y; cin >> x >> y; Add(x, y); d[x]++; d[y]++; } map<int, int> ma; For1(i, 1, n) { ma[d[i]]++; } int resx = -1, resy = -1; for (auto &[de, cnt] : ma) { if (cnt == 1) { resx = de; } } if (resx != -1) { for (auto &[de, cnt] : ma) { if (cnt == resx) { resy = de - 1; break; } } } else { for (auto &[de, cnt] : ma) { if (de != 1) { resy = de - 1; resx = cnt - 1; break; } } } cout << resx << ' ' << resy << '\n'; } return 0; }

Array and Operations tutorial 为了让分数最小，需要把大的元素消除掉。消除的操作和元素的顺序没有关系，所以把原数组从小到大排序，把最大的 $2k$ 的元素消除掉。为了使得消除的分数最小，对这 $2k$ 个元素排序之后，前 $k$ 个元素和后 $k$ 个元素一一匹配，这样做的目的是使得分子比分母小的数对尽可能多。 // Date: Thu Dec 21 23:15:54 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 const int N = 110; int t, n, a[N], k; int main(void) { #ifdef _DEBUG freopen("1618d.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> k; For1(i, 1, n) { cin >> a[i]; } sort(a + 1, a + 1 + n); int res = 0, len = n - 2 * k; VI b; For1(i, 1, n) { if (i <= len) { res += a[i]; } else { b.pb(a[i]); } } For(i, 0, k) { res += b[i] / b[i + k]; } cout << res << '\n'; } return 0; }

Coin Rows tutorial 挺有趣的一道题。 这题并不能简单地 DP 做，不能最大化 Alice 的收益，此时 Bob 的收益并不是最小。 观察 Alice 的路径，形式是 $Z$ 字型。此时 Bob 只能选择上侧或者下侧，上侧是第一行的后缀和，下侧是第二行的前缀和，只需要让它们的最大值最小即可，线性扫一遍。 // Date: Thu Dec 21 20:11:59 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 const int N = 100010; int t, n, a[5][N]; ll d[5][N]; PII p[5][N]; int main(void) { #ifdef _DEBUG freopen("1555c.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, 2) { For1(j, 1, n) { cin >> a[i][j]; } } ll res = INF; memset(d, 0, sizeof d); Rof1(i, 1, n) { d[1][i] = d[1][i + 1] + a[1][i]; } For1(i, 1, n) { d[2][i] = d[2][i - 1] + a[2][i]; } For1(i, 1, n) { ll tmp = max(d[1][i + 1], d[2][i - 1]); res = min(res, tmp); } cout << res << '\n'; } return 0; }

Pokémon Army (easy version) 需要考虑的形式是 $-b+c$，所以元素可以分为两类，一种是前面带负号的，例如 $b$，另一种是前面带正号的，例如 $c$。 $d[i][0]$ 表示前 $i$ 个元素中，以 $c$ 类元素结尾的最大价值。$d[i][1]$ 表示前 $i$ 个元素中，以 $b$ 类元素结尾的最大价值。有了这两个状态，那么状态转移方程就比较好想了。 // Date: Thu Dec 21 19:53: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()) 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 t, n, q, a[N]; ll d[N][2]; int main(void) { #ifdef _DEBUG freopen("1420c1.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> q; memset(d, 0, sizeof d); For1(i, 1, n) { cin >> a[i]; d[i][0] = a[i]; } For1(i, 2, n) { d[i][1] = max(d[i - 1][0] - a[i], d[i - 1][1]); d[i][0] = max(d[i][0], max(d[i - 1][1] + a[i], d[i - 1][0])); } cout << max(d[n][0], d[n][1]) << '\n'; } return 0; }

Another Permutation Problem tutorial 可行的排列的形式是 $1, 2, 3, \ldots, k, n, n - 1, n - 2, \ldots, k + 2, k + 1$。这种形式的排列有 $n$ 个，暴力求出来取最大值。不过并不知道怎么证明，只能打表找规律。 // Date: Wed Dec 20 22:50: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()) 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, n; int main(void) { #ifdef _DEBUG freopen("1859c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; ll res{}; For1(i, 1, n) { int sum = -1, start = n - i + 1, ma = -1; ll tmp{}; For1(j, 1, n) { int x; if (j < start) { x = j * j; } else { if (sum == -1) sum = j + n; x = j * (sum - j); } tmp += x; ma = max(ma, x); } tmp -= ma; res = max(res, tmp); } cout << res << '\n'; } return 0; }

LuoTianyi and the Table tutorial 可以发现最终结果只和 $a[1][1], a[1][2], a[2][1]$ 有关，因为所有的以 $(1, 1)$ 为左上角的矩形都至少经过 $a[1][2]$ 或者 $a[2][1]$ ，所以把 $a[1][1]$ 作为最大值，其它两个点作为最小的两个值；或者把 $a[1][1]$ 作为最小值，其它两个点作为最大的两个值。这两种情况分别计算，并不是等价的。设 $n > m$，那么最大差的个数是 $n(m - 1)$ 或者 $m(n - 1)$，因为 $n > m$，所以 $m(n - 1) > n(m - 1)$。 // Date: Wed Dec 20 21:02:01 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 const int N = 10010; int t, a[N], n, m; int main(void) { #ifdef _DEBUG freopen("1825b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> m; int m1 = n * m; For(i, 0, m1) { cin >> a[i]; } sort(a, a + m1); int x = a[m1 - 1], y = a[0], y1 = a[1], d1 = x - y, d2 = x - y1; if (n < m) swap(n, m); ll res = d1 * (n - 1) * m + d2 * (m - 1); x = a[0], y = a[m1 - 1], y1 = a[m1 - 2], d1 = y - x, d2 = y1 - x; ll res1 = d1 * (n - 1) * m + d2 * (m - 1); res = max(res, res1); cout << res << '\n'; } return 0; }

Subsequence Addition (Easy Version) tutorial 需要注意到因为 $c_i$ 中元素不超过 $5000$，所以从 $a_i$ 中挑出的子序列的元素的和也不超过 $5000$。因为数组 $c$ 中的元素顺序没有关系，所以可以排序之后从小到大判断 $c_i$ 是否可行。设 $d_s$ 为当前的 $c$ 数组的子序列能够得到的和为 $s$，那么 $d_s = d_s | d_{s - c_i}$，每新加入一个 $c_i$，就用它去更新之前可行的 $d_s$。 这道题目有另外一个解法。观察可以发现如果 $c_i$ 小于当前数组 $c$ 的前缀和 $p[i - 1]$，那么 $c_i$ 一定是可行的，也就是 $c_1, c_2, \ldots, c_{j - 1}$ 的某个子序列的和可以组成 $c_i$。下面用数学归纳法证明。 假设对于长度为 $l$ 的数组 $c$ 上述结论成立：设数组 $c$ 的元素和是 $sum$，那么 $c$ 的子序列的和可以组成 $[1, sum]$ 中的所有数字。设 $1 \le x \le sum$，下面证明在数组 $c$ 中加入 $x$ 之后，数组 $c$ 的子序列的和可以组成 $[1, sum + x]$ 中的所有数字。只需要证明 $[sum + 1, sum + x]$ 中的数字可以被 $c_1, c_2, \ldots, c_l, c_{l + 1}$ 组成即可。 ...