MX-J24 题解（T1 - T4） - 指南

T1: P14056 【MX-X21-T1】[IAMOI R5] 七休制

题目描述

你有三种类型的日子：

• 加训：疲劳度 $+1$。
• 休息：疲劳度不变。
• 颓废：疲劳度 $-1$。

最开始的疲劳度是 $0$，总共有 $a+b+c$ 天，需要恰好有 $a$ 天加训，$b$ 天休息，$c$ 天颓废。你可以随意安排顺序，求有多少天的疲劳度为 $0$。

数据范围：$0\le a,b,c\le 100$。

思路

算法标签：贪心

按照贪心的角度来讲，我们先休息 $b$ 天（对答案的贡献为 $b$）。然后让加训和颓废交替进行（对答案的贡献为 $\min (a,c)$）。最终答案为 $b+\min (a,c)$。

Code

#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;using db = double;using pii = pair<int, int>;using pq = priority_queue<int, vector<int>>;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int a, b, c;cin >> a >> b >> c;cout << b + min(a, c) << "\n";return 0;}

T2: P14057 【MX-X21-T2】[IAMOI R5] 空气蛹

题目描述

有 $n$ 个杯子，编号为 $1$ 到 $n$，每个的容量都为 $m$。现在，第 $i$ 个杯子里水的体积为 $a_i$。

你可以进行若干次操作，每次可以选择两个不同的杯子 $i$ 和 $j$ ，并把 $i$ 中的所有水倒入 $j$ 中。如果操作后 $j$ 中的水的体积大于 $m$，那么 $j$ 中的水的体积会溢出到只剩 $m$。

完成这些操作后，你需要保证杯中水的体积单调不减，且留下水的总体积尽量大。求这个最大值。

数据范围：$1\le T\le 10$，$1\le n\le 10^5$，$1\le m\le 10^9$，$0\le a_i\le m$。

思路

算法标签：贪心

首先如果这些杯子已经按照升序排序排好了，那么答案显然为 $\sum _{i=1}^n{a}_i$。

否则，我们至少需要合并一次。由于合并一次就会产生一个空杯子，这样这个杯子就可以作为中转杯，让其他所有的水杯升序排序且不浪费。

那么问题就变成了该让那两个杯子合并呢？贪心来讲显然是最小的两个杯子，因为这样才可以让浪费尽可能的小。

Code

#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;using db = double;using pii = pair<int, int>;const int N = (int)1e5 + 5;int n;ll m, a[N], sum = 0;void sol() {cin >> n >> m;bool flag = true;sum = 0;for (int i = 1; i <= n; i++) {cin >> a[i];sum += a[i];if (a[i] < a[i - 1]) flag = false;}if (!flag) {sort(a + 1, a + n + 1);cout << sum - a[1] - a[2] + min(a[1] + a[2], m) << "\n";} else cout << sum << "\n";}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T; cin >> T;while (T--) sol();return 0;}

T3: P14058 【MX-X21-T3】[IAMOI R5] 两个人的演唱会

题目描述

给定一个长度为 $n$ 的，由正整数组成的环 $a_1,a_2,\cdots ,a_n$，你需要将这个环切成若干段，是的所有段的内极差都小于等于 $m$，求分成的最小段数。

数据范围： $1\le T\le 5\cdot 10^6$，$1\le n$，$\sum n\le 3\cdot 10^7$，$1\le m,a_i\le 10^9$。

思路

算法标签：贪心

先考虑是一条链的情况，那么直接贪心找到最少次数（subtask 7）。

如果是环，我们可以直接暴力枚举从哪里破环，然后进行贪心，这样的时间复杂度是 $O(n^2)$。

考虑优化，先破环成链，先特判整个环的极差 $\le m$ 的情况（答案为 $1$），然后进行贪心。假设贪心后的最优答案为 $ans$，那么我们的答案就是 $\frac{ans}{2}$，原因如下：

• 假设 $|a_1-a_n|>m$ 时，就跟链的情况一样，所以答案为 $\frac{ans}{2}$。
• 假设 $|a_1-a_n|\le m$ 时，$a_1$ 和 $a_n$ 必定会合并成为一个段。答案为 $\lfloor \frac{ans}{2}\rfloor$，由于是整数，所以就是 $\frac{ans}{2}$。

Code

#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;using db = double;using pii = pair<int, int>;const int N = (int)3e7 + 5;int n, m;int a[N * 2];void init() {}void sol() {cin >> n >> m;for (int i = 1; i <= n; i++) { // 注意：破环成链cin >> a[i];a[i + n] = a[i];}// 贪心求出最小的答案int maxn = a[1], minn = a[1], ans = 1;for (int i = 2; i <= 2 * n; i++) {maxn = max(maxn, a[i]);minn = min(minn, a[i]);if (maxn - minn > m) {ans++;maxn = a[i];minn = a[i];}}ans /= 2;cout << (ans == 0 ? 1 : ans) << "\n"; // 这里包含了一个特判：环的极差 <= m}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T; cin >> T;while (T--) sol();return 0;}

T4: P14059 【MX-X21-T4】[IAMOI R5] 使一颗心免于哀伤

题目描述

一个黑白棋子组成的环，双方轮流删除一段连续的同色棋子（知更鸟只能删黑棋，星期日只能删白棋），删后仍成环。如果只剩一种颜色，游戏结束：若全白则知更鸟胜，若全黑则星期日胜。

思路

算法标签：分类讨论

首先特判两种显然的情况：

1. 环上只有一种颜色，那么答案显然一定（若是白色则知更鸟胜，若是黑色则星期日胜）。
2. 换上只有两段（两段色块），那么答案一定是先手必胜（手画画就知道了，先手直接全拿完自己的那一段就胜了）。

因为两个人都是聪明的，所以他们不希望出现我拿完一段棋子就只剩下一种颜色的棋子了，所以我们尽量少拿，也就是每次拿一个。这样就很容易想到判断谁必胜的方法：两个人能拿的棋子更多者，为必胜者。

注意：需要先特判那两种情况

Code

#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;using db = double;using pii = pair<int, int>;const int N = (int)1e5 + 5;int n;string s;void init() {}void sol() {cin >> n;cin >> s;s = '_' + s;// 判断只有一种颜色的情况bool flag1 = 0, flag2 = 0;for (int i = 1; i <= n; i++) {if (s[i] == '1') flag1 = true;else flag2 = true;}if ((flag1 & flag2) == 0) { // 如果只有一种颜色cout << (!flag1 ? "Robin\n" : "Sunday\n");return ;}// 数出有多少个色块（注意环）int cnt = 1;for (int i = 1; i < n; i++) {if (s[i] != s[i + 1]) cnt++;}if (cnt & 1) cnt--; // 首尾颜色相同if (cnt == 2) { // 如果只有两段，那么先手必胜（即 Robin）cout << "Robin\n";return ;}// 计算 cnt > 2 的情况int sum1 = 0, sum2 = 0;for (int i = 1; i <= n; i++) {if (s[i] == '1') sum1++;else sum2++;}cout << (sum1 > sum2 ? "Robin\n" : "Sunday\n");}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T; cin >> T;while (T--) sol();return 0;}