Greedy

Restore the Array 这道题的细节还是挺多的。大题思路就是对于当前的 $b_i$，如果 $a_i$ 还没有确定，那么令 $a_i = b_i$，这样可以留出 $a_{i + 1}$ 的位置给 $b_{i + 1}$ 确定。如果 $a_{i}$ 已经确定，检查它是否恰好等于 $b_{i}$，如果不等，那么只能让 $a_{i + 1} = b_i$。接下来如果 $b_i < b_{i + 1}$，同时 $a_i = b_i$，此时 $a_{i+1}$ 这个位置就「没有用了」，不妨令 $a_{i + 1} = 0$，原因是 $a_{i + 1}$ 不能等于 $b_{i + 1}$（如果 $a_{i + 1} = b_{i + 1}$，那么 $b_{i} = b_{i + 1}$，然而 $b_i < b_{i + 1}$）。 // Date: Fri Dec 8 19:17:03 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, a[N], b[N]; int main(void) { #ifdef _DEBUG freopen("1811c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { int n1; cin >> n; n1 = n - 1; For1(i, 1, n1) { cin >> b[i]; } memset(a, -1, sizeof a); For1(i, 1, n1) { bool flag = false; if (a[i] == -1) { a[i] = b[i]; flag = true; } else { if (a[i] < b[i]) { a[i + 1] = b[i]; } else { flag = true; } } if (b[i] < b[i + 1]) { if (flag) { a[i + 1] = 0; if (i + 2 <= n) { a[i + 2] = b[i + 1]; } } } } if (a[n] == -1) a[n] = 0; For1(i, 1, n) { cout << a[i] << ' '; } cout << '\n'; } return 0; }

Points on Plane 模拟前几个样例可以发现需要根据奇偶性讨论。反向考虑，当结果为 $0, 1, 2, 3, 4$ 的时候的节点分配是怎样的，可以得到当答案 $k$ 是奇数的时候，能够放下的最多的点数是 $2(k + 1)(\frac{k}{2} + 1)$；当答案 $k$ 是偶数的时候，能够放下的最多的点数是 $(k + 1)^2$。然后就可以二分答案了。 // Date: Thu Dec 7 21:25:48 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; ll n; bool check(ll x) { ll cnt; if (x & 1) { cnt = (x + 1) * (x / 2 + 1) * 2; } else { cnt = (1 + x) * (1 + x); } return cnt < n; } int main(void) { #ifdef _DEBUG freopen("1809b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; if (n == 1) { cout << "0\n"; continue; } ll l = 0, r = 1e10, mid; while (l < r) { mid = (l + r + 1) / 2; if (check(mid)) l = mid; else r = mid - 1; } cout << l + 1 << '\n'; } return 0; }

Settlement of Guinea Pigs 当没有医生来之前，每增加一只猪，就需要新增一个笼子。当医生来了之后，知道了所有猪的性别，设一共有 $cnt$ 只，那么最多需要的笼子个数是：$\frac{cnt}{2} + 1$。 // Date: Thu Dec 7 19:42: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 = 100010; int t, n, a[N]; int main(void) { #ifdef _DEBUG freopen("1802b.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, cur = 0, cnt = 0; For1(i, 1, n) { if (a[i] == 1) { cnt++; cur++; res = max(res, cur); } else { if (cnt) { cur = cnt / 2 + 1; } res = max(res, cur); } } cout << res << '\n'; } return 0; }

A Cookie for You 挺有趣的一道题目。 先观察第一类人，可以发现无论当前的局面是什么，第一类人总可以把饼干一直吃下去。 再观察第二类人，可以发现他们能够吃到的最多的饼干的数量是 $min(a, b)$，即使在第一类人的「帮助」下，也不能够增加第二类人能够吃到的饼干的数量。 // Date: Wed Dec 6 22:45: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 int t; ll a, b, n, m; int main(void) { #ifdef _DEBUG freopen("1371c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> a >> b >> n >> m; bool flag = true; ll a1 = min(a, b); if (a1 < m) { flag = false; } else { ll rem = a + b - m; if (rem < n) flag = false; } cout << (flag ? "YES\n" : "NO\n"); } return 0; }

Omkar and Last Class of Math 对于给定的 $n$，要找到 $x$ 和 $y$，满足 $x + y = n$，并且满足 $LCM(x, y)$ 尽可能小。显然满足条件的 $LCM(x, y)$ 的一个上界是 $n - 1$。当 $n$ 是偶数的时候，只需要取 $x = y = \frac{n}{2}$。当 $n$ 是奇数的时候，设 $y = kx$，那么 $x + kx = (k + 1)x = n$，所以只需要枚举 $[1, \sqrt{n}]$ 就可以了，此时枚举变量可能是 $k + 1$，也可能是 $x$，这两种情况分别求出 $x$ 和 $y = kx$，其中 $LCM(x, y) = LCM(x, kx) = kx = y$，维护最小值即可。 // Date: Wed Dec 6 00:57: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()) #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; ll n; int main(void) { #ifdef _DEBUG freopen("1372b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; PII res = {1, n - 1}; if (n % 2 == 0) { res = {n / 2, n / 2}; } else { ll cur = n - 1; for (ll i = 2; i * i <= n; i++) { if (n % i == 0) { ll x = i, y = n / i; int tmp = max((x - 1) * y, y); if (tmp < cur) { res = {(x - 1) * y, y}; cur = tmp; } tmp = max((y - 1) * x, x); if (tmp < cur) { res = {(y - 1) * x, x}; cur = tmp; } } } } cout << res.f1 << ' ' << res.f2 << '\n'; } return 0; }

Big Vova 构造出一个数列，使得它的前缀 $GCD$ 的字典序最大，数组范围只有 $1000$，所以在构造的过程中，计算当前的前缀 $GCD$，线性选出一个和之前结果最大的 $GCD(pre, a[i])$ 即可。 // Date: Tue Dec 5 23:51:39 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 = 1010; int t, n, a[N], b[N]; bool vis[N]; int gcd(int a, int b) { return (a % b == 0) ? b : gcd(b, a % b); } int main(void) { #ifdef _DEBUG freopen("1407b.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]; } sort(a + 1, a + 1 + n, greater<int>()); b[1] = a[1]; vis[1] = true; int pre = b[1]; For1(i, 2, n) { int g = 0, idx = -1; For1(j, 2, n) { if (vis[j]) continue; int g1 = gcd(pre, a[j]); if (g1 > g) { g = g1; idx = j; } } vis[idx] = true; b[i] = a[idx]; pre = gcd(pre, b[i]); } For1(i, 1, n) { cout << b[i] << ' '; } cout << '\n'; } return 0; }

Negative Prefixes 因为要使得满足前缀和 $p_j < 0$ 的 $j$ 的最大值最小，所以把可以移动的元素按照从大到小排序，把大的数字尽量放在后面，这样负数在前面，就可以满足条件。 // Date: Tue Dec 5 22:46:45 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 = 110; int t, n, a[N], l[N], b[N]; int main(void) { #ifdef _DEBUG freopen("1418b.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]; } VI d; For1(i, 1, n) { cin >> l[i]; if (!l[i]) { d.pb(a[i]); } } sort(all(d), greater<int>()); int idx = SZ(d) - 1; Rof1(i, 1, n) { if (l[i]) { b[i] = a[i]; } else { b[i] = d[idx--]; } } For1(i, 1, n) { cout << b[i] << ' '; } cout << '\n'; } return 0; }

Nice Matrix tutorial 因为每行每列都需要是回文，所以四个角的数字必须相同。先考虑这四个数字，让它们都转变成某个数字，使得操作数最小，让它们都变成中位数是最优的。对于矩阵中所有的这样的四个数字都做这样的操作。实现的过程中需要考虑奇偶性。 // Date: Sun Dec 3 18:52: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()) #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, m; ll a[N][N]; bool vis[N][N]; int main(void) { #ifdef _DEBUG freopen("1422b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> m; memset(vis, false, sizeof vis); For1(i, 1, n) { For1(j, 1, m) { cin >> a[i][j]; } } ll res = 0; For1(i, 1, n) { int i1 = n + 1 - i; if (i1 < i) break; For1(j, 1, m) { VI tmp; tmp.clear(); int j1 = m + 1 - j; if (j1 < j) break; if (j1 != j) { tmp.pb(a[i][j]); tmp.pb(a[i][j1]); if (i != i1) { tmp.pb(a[i1][j]); tmp.pb(a[i1][j1]); } } else { if (i != i1) { tmp.pb(a[i][j]); tmp.pb(a[i1][j]); } } int len = SZ(tmp); if (len) sort(all(tmp)); if (len == 4) { For(k, 0, len) { res += abs(tmp[k] - tmp[1]); } } else if (len == 2) { res += abs(tmp[0] - tmp[1]); } } } cout << res << '\n'; } return 0; }

Inflation tutorial 这题有点意思，首先要发现递增 $p_0$ 总是最优的：设 $c_j = \frac{p_j}{preSum_{j-1}}$，如果递增的是 $p_i$，如果 $i > j$，此时 $c_j$ 不变；如果 $i = j$，此时 $c_j$ 变大；如果 $i < j$，那么 $c_j$ 变小。我们希望对某个元素 $p_j$ 递增的时候，之前的性质能够保持不变，所以每次都递增 $p_0$ 即可。判定整个数列满足题目要求的性质是线性的，所以可以二分答案。 // Date: Sun Dec 3 17:54: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 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 = 110; int t; ll n, k, p[N], b[N]; bool check(ll x) { For1(i, 2, n) { ll l = 100 * p[i], r = k * (x + b[i - 1]); if (l > r) return false; } return true; } int main(void) { #ifdef _DEBUG freopen("1476b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> k; memset(b, 0, sizeof b); For1(i, 1, n) { cin >> p[i]; b[i] = b[i - 1] + p[i]; } ll l = 0, r = 1e11 + 10, mid; while (l < r) { mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid + 1; } cout << r << '\n'; } return 0; }

Deep Down Below tutorial 先考虑每一个洞穴，为了要打败所有的怪物，考虑每个怪兽要求的起始等级，然后求最大值。接下来考虑所有的洞穴，每个洞穴的起始等级要求不一样，可以先从小到大排序，因为对于给定等级，判定能否通关只需要一次线性扫描，所以可以二分答案。除了二分解法，其实也可以按照单个洞穴的思路来考虑所有的洞穴。 // Date: Sun Dec 3 10:23:28 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; pair<ll, ll> b[N]; VI a[N]; bool check(ll x) { For(i, 0, n) { if (x < b[i].f1) return false; x += b[i].f2; } return true; } int main(void) { #ifdef _DEBUG freopen("1561c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; For(i, 0, n) { int len; cin >> len; a[i].clear(); For(j, 0, len) { int x; cin >> x; a[i].pb(x); } ll ma = a[i][0]; For(j, 1, len) { ma = max(ma, ll(a[i][j] - j)); } b[i].f1 = ma; b[i].f2 = len; } sort(b, b + n); ll l = 1, r = 1e18, mid; while (l < r) { mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid + 1; } cout << r + 1 << '\n'; } return 0; }

Removing Smallest Multiples tutorial 设移除 $v$ 的代价是 $f(v) = x$，那么满足 $x | v$，并且 $x, 2x, 3x, \ldots, (k - 1)x$ 在集合中都不存在，并且都已经被移除，其中 $v = kx$。可以根据这一点来求出所有的 $f(v)$，不过要反过来求。对于每个 $x$，考虑所有的 $kx$，如果 $x, 2x, 3x, \ldots, kx$ 都不在集合中，并且 $kx$ 还没有被移除，那么 $kx$ 的代价就是 $x$。 // Date: Sun Sep 17 19:57:48 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 LN ListNode #define LNP ListNode * #define TN TreeNode #define TNP TreeNode * #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 #ifdef _DEBUG struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int val) : val(val), next(nullptr) {} ListNode(int val, ListNode *next) : val(val), next(next) {} }; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; #endif const int N = 1000010; bool vis[N]; int a[N], n, t, c[N]; int main(void) { #ifdef _DEBUG freopen("1734c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { string s; cin >> n >> s; For1(i, 1, n) { a[i] = (s[i - 1] == '1'); vis[i] = false; c[i] = 0; } ll ans = 0; For1(i, 1, n) { if (!a[i]) { if (!vis[i]) { vis[i] = true; c[i] = i; } for (int j = i + i; j <= n; j += i) { if (a[j]) break; if (!vis[j]) { vis[j] = true; c[j] = i; } } } } For1(i, 1, n) { if (!a[i]) { ans += c[i]; } } cout << ans << '\n'; } return 0; }

Minimize Distance 正数和负数分开做，从大到小排序之后，每 $k$ 个一组考虑，因为距离远的是一定要送到的，距离近的可以顺便送到。最终如果正数的最大值更大，那么最后就停留在正数。 // Date: Sat Dec 2 18:01: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 const int N = 200010; int t, n, k, a[N]; VI b, c; int solve(VI &b, ll &res) { int len = SZ(b), cnt = 0, maxb = 0; if (!len) return 0; maxb = b[0]; int cur = b[0]; cnt = 1; bool flag = true; if (cnt == k) { res += cur; flag = false; cnt = 0; } For(i, 1, len) { if (cnt == 0) { cur = b[i]; } cnt++; if (cnt == k) { if (flag) { res += cur; flag = false; } else { res += cur * 2; } cnt = 0; } } if (cnt > 0 && cnt < k) { if (flag) { res += cur; } else { res += cur * 2; } } return maxb; } int main(void) { #ifdef _DEBUG freopen("1585c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> k; b.clear(); c.clear(); For1(i, 1, n) { cin >> a[i]; if (a[i] > 0) b.pb(a[i]); else if (a[i] < 0) c.pb(abs(a[i])); } sort(all(b), greater<int>()); sort(all(c), greater<int>()); ll res = 0; int lenb = SZ(b), maxb = 0; if (lenb) { maxb = solve(b, res); } int maxc = 0; int lenc = SZ(c); if (lenc) { maxc = solve(c, res); } if (lenb && lenc) { res += min(maxb, maxc); } cout << res << '\n'; } return 0; }

Not Sitting 因为要距离已经选定的点尽量远，所以只可能是四个角落的其中一个，枚举就可以了。男生为了距离女生更近一点，所以他应该尽量选择靠近中心的位置，因为靠近中心的位置可以让它距离所有点的距离都尽可能小，因此女生应该先从中心的点开始涂色，女生选择的点越少，最终两人的距离越小，两人都是最优策略，因此答案数组需要从小到大排序。 // Date: Sat Dec 2 17:04:06 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, n, m; int main(void) { #ifdef _DEBUG freopen("1627b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> m; vector<PII> corners{ {1, 1}, {1, m}, {n, 1}, {n, m}, }; VI res; For1(i, 1, n) { For1(j, 1, m) { int dis = 0; for (auto &[x, y] : corners) { int tmp = abs(x - i) + abs(y - j); dis = max(dis, tmp); } res.pb(dis); } } sort(all(res)); for (auto x : res) { cout << x << ' '; } cout << '\n'; } return 0; }

Directional Increase tutorial 感觉这题有点不好想到。上面的官方题解已经很清楚了。统计每个点的增加次数和减少次数，然后观察它们的关系，得到递推公式，这个思路挺有意思的。 // Date: Wed Nov 29 18:47:27 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; ll a[N], b[N]; int main(void) { #ifdef _DEBUG freopen("1693a.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]; } bool mark = true, zero = false; ll sum = 0; b[1] = a[1]; sum = b[1]; if (b[1] < 0) { mark = false; } else if (b[1] == 0) { zero = true; } For1(i, 2, n) { sum += a[i]; b[i] = a[i] + b[i - 1]; if (b[i] < 0) { mark = false; break; } else if (b[i] > 0 && zero) { mark = false; break; } else if (b[i] == 0) { zero = true; } } if (sum && mark) mark = false; cout << (mark ? "YES\n" : "NO\n"); } return 0; }

Game of Ball Passing tutorial 这是一道非常经典的贪心题目，遇到过很多次。题解在上面的 tutorial 链接讨论区，比较关键的是证明。首先找到整个数列的最大值 $x$，设整个数列的和是 $sum$，如果 $x \ge sum - x$，那么可以让其他所有元素依次消耗 $x$。如果 $x < sum - x$，那么可以这样思考：设 $y = sum - x$，把 $y$ 中的元素按顺序排列，因为每个人把球传出，对应的 $a_i$ 便会递减 $1$，所以我们可以依次对 $y$ 中的每个人递减 $1$，可以一直这样下去，甚至直到剩下一个或零个人，并且整个过程是连续的，设剩下的元素和为 $z$，那么 $z < y$，并且容易证明 $z < x$（假设 $p - q = z$，如果 $p - q \ge x$，那么有 $p \ge q + x$，这和 $x$ 是最大值矛盾），所以有 $z < x < y$，由于 $y$ 到 $z$ 的过程是连续的，所以一定存在某个时刻恰好等于 $x$，此时就转化成了第一种情况。 // Date: Wed Nov 29 21:36:17 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; ll a[N], sum; int main(void) { #ifdef _DEBUG freopen("1649b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; sum = 0; ll ma = -1; For1(i, 1, n) { cin >> a[i]; sum += a[i]; ma = max(ma, a[i]); } if (!sum) cout << "0\n"; else if (2 * ma <= sum) cout << 1 << '\n'; else { cout << 2 * ma - sum << '\n'; } } return 0; }