Contestant. Rank 728. Rating +14.罚时爆炸
A. Jellyfish and Undertale
题意
对于一个即将引爆的炸弹，给定 \(i\) 个工具，每个工具最多使用一次，使用时将会使炸弹的计时器 \(+x_i\) 个单位时间，但如果计时器的时间大于 \(a\)，它将会复位为 \(a\)。
找出一个方案，使计时器在归 \(0\) 前，时间尽可能长，并输出这个时间。
思路
显然，为了让时间尽可能长，我们一定会在计时器为 \(1\) 时使用工具，那么工具的使用顺序是无所谓的。
那么，我们只需将每个工具的 \(x_i\) 和 \(a - 1\) 取最小值，然后累加即可。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int a, b, n;
cin >> a >> b >> n;
vector<int> p(n + 1);
int ans = b;
for(int i=1;i<=n;i++) {
cin >> p[i];
ans += min(a - 1, p[i]);
}
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}不可以乱贪心
B. Jellyfish and Game
题意
给定两个人之间的博弈：
总共进行 \(k\) 轮；
如果当前是奇数轮，那么 \(A\) 可以选择将自己的一个元素和 \(B\) 的任意一个元素交换，或者不操作；
如果当前是偶数轮，那么 \(B\) 可以选择将自己的一个元素和 \(A\) 的任意一个元素交换，或者不操作；
每个玩家都尽可能最大化自己的元素总和
输出最后，\(A\) 的所有元素总和。
思路
首先，可以想象为两个人在 "拉扯"：
\(A\) 把自己最小的元素和 \(B\) 最大的元素交换；
\(B\) 把自己最小的元素和 \(A\) 最大的元素交换；
\(\ldots\)
可以发现，\(A\) 的元素总和是以 \(2\) 为周期的，那么我们分讨一下即可。
当然，如果 \(A\) 最小的元素大于等于 \(B\) 的最大元素，那么 \(A\) 考虑不操作。
时间复杂度：\(O(n \log n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, m, t;
cin >> n >> m >> t;
vector<int> a(n + 1), b(m + 1);
int sum1 = 0;
for(int i=1;i<=n;i++) {
cin >> a[i];
sum1 += a[i];
}
for(int j=1;j<=m;j++) cin >> b[j];
sort(all(a)), sort(all(b));
if(a[1] < b[m]){
sum1 = sum1 - a[1] + b[m];
}
if(t % 2 == 0){
sum1 = sum1 - max(a[n], b[m]) + min(a[1], b[1]);
}
cout << sum1 << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}打个表（x
C. Jellyfish and Green Apple
题意
给定 \(n\) 个水果块，每块重量 \(1~\text{kg}\)，需要将这些水果平均分给 \(m\) 个人。
定义一次操作为选定一个水果块，并将其分成等重量的两块。
输出最小的操作数，使最后每个人收到水果块总重量相同。
思路
首先，我们可以给每个人分 \(\lfloor \frac{n}{m} \rfloor\) 个，从而剩下 \(n \bmod m\) 块。
我们记其为 \(p\)，那么我们现在就需要将 \(p\) 拆成 \(m\) 份。
显然，因为我们是对半切的，那么保留某些不切是不合理的，这样只会让能分的份数更小（我们需要凑起来）。
那么，我们只需枚举切成了多小即可。
具体来说，我们枚举对每一小块切了几次，如果现在的块数是 \(m\) 的倍数，那么这个方案就是合法的，我们模拟算一下切了几次即可。
时间复杂度：\(O(32 ^ 2)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, m;
cin >> n >> m;
n %= m;
if(n == 0) {
cout << 0 << '\n';
return;
}
for(int k=1;k<=32;k++){
if(n * (1ll << k) % m == 0){
int ans = 0;
for(int i=1;i<=k;i++){
ans += n;
n = n * 2 % m;
}
cout << ans << '\n';
return;
}
}
cout << -1 << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}有种暴力的美
D. Jellyfish and Mex
题意
给定一个序列 \(a\)，定义操作如下：
从序列中选定一个数并删除；
\(m := m + MEX(a)\)
初始状态下，\(m\) 为 \(0\)。
在 \(n\) 次操作后，输出 \(m\) 的最大值。
思路
首先，如果我们确定要删哪个有效的数的时候，我们完全可以直接将其删完，因为删完之后，\(MEX\) 肯定会减小。
其次，删除的顺序并不是有规律的，我们只能从当前的 \(MEX\) 开始往前删除，无法确定具体删哪个。
因而，我们考虑动态规划。
具体来说，我们可以倒推，记 \(i\) 为这次要删掉的数，那么我们枚举 \(j \in [i + 1, MEX]\)，将 \(j\) 视为上一次删掉的数。
那么显然有递推式：\(dp[i] = \min(dp[i], dp[j] + (cnt[i] - 1) \times j + i)\)。
其中，\(cnt[i]\) 为数字 \(i\) 的个数。
为何呢？因为我们删掉 \(cnt[i] - 1\) 个数之前，\(MEX\) 都是上一个被删掉的数，而将最后一个删完后，\(MEX\) 变成了当前的数。
时间复杂度：\(O(n ^ 2)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
sort(all(a));
map<int, int> cnt;
int mex = -1;
for(int i=1;i<=n;i++) {
cnt[a[i]] ++;
if(a[i] == mex + 1) mex ++;
}
mex ++;
if(mex == 0){
cout << 0 << '\n';
return;
}
vector<int> dp(mex + 1, inf);
dp[mex] = 0;
for(int i=mex;i>=0;i--){
for(int j=i+1;j<=mex;j++){
dp[i] = min(dp[i], (cnt[i] - 1) * j + i + dp[j]);
}
}
cout << dp[0] << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}也是推了好久没推清楚（x