Contestant. Rank 728. Rating +14.

罚时爆炸

A. Jellyfish and Undertale

题意

对于一个即将引爆的炸弹，给定 i 个工具，每个工具最多使用一次，使用时将会使炸弹的计时器 +xi 个单位时间，但如果计时器的时间大于 a，它将会复位为 a。

找出一个方案，使计时器在归 0 前，时间尽可能长，并输出这个时间。

思路

显然，为了让时间尽可能长，我们一定会在计时器为 1 时使用工具，那么工具的使用顺序是无所谓的。

那么，我们只需将每个工具的 xi 和 a−1 取最小值，然后累加即可。

时间复杂度：O(n)

对应AC代码

C++
#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

题意

给定两个人之间的博弈：

  1. 总共进行 k 轮；

  2. 如果当前是奇数轮，那么 A 可以选择将自己的一个元素和 B 的任意一个元素交换，或者不操作；

  3. 如果当前是偶数轮，那么 B 可以选择将自己的一个元素和 A 的任意一个元素交换，或者不操作；

  4. 每个玩家都尽可能最大化自己的元素总和

输出最后，A 的所有元素总和。

思路

首先，可以想象为两个人在 "拉扯"：

  1. A 把自己最小的元素和 B 最大的元素交换；

  2. B 把自己最小的元素和 A 最大的元素交换；

  3. …

可以发现，A 的元素总和是以 2 为周期的，那么我们分讨一下即可。

当然，如果 A 最小的元素大于等于 B 的最大元素，那么 A 考虑不操作。

时间复杂度：O(nlog⁡n)

对应AC代码

C++
#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 kg，需要将这些水果平均分给 m 个人。

定义一次操作为选定一个水果块，并将其分成等重量的两块。

输出最小的操作数，使最后每个人收到水果块总重量相同。

思路

首先，我们可以给每个人分 ⌊nm⌋ 个，从而剩下 nmodm 块。

我们记其为 p，那么我们现在就需要将 p 拆成 m 份。

显然，因为我们是对半切的，那么保留某些不切是不合理的，这样只会让能分的份数更小（我们需要凑起来）。

那么，我们只需枚举切成了多小即可。

具体来说，我们枚举对每一小块切了几次，如果现在的块数是 m 的倍数，那么这个方案就是合法的，我们模拟算一下切了几次即可。

时间复杂度：O(322)

对应AC代码

C++
#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，定义操作如下：

  1. 从序列中选定一个数并删除；

  2. m:=m+MEX(a)

初始状态下，m 为 0。

在 n 次操作后，输出 m 的最大值。

思路

首先，如果我们确定要删哪个有效的数的时候，我们完全可以直接将其删完，因为删完之后，MEX 肯定会减小。

其次，删除的顺序并不是有规律的，我们只能从当前的 MEX 开始往前删除，无法确定具体删哪个。

因而，我们考虑动态规划。

具体来说，我们可以倒推，记 i 为这次要删掉的数，那么我们枚举 j∈[i+1,MEX]，将 j 视为上一次删掉的数。

那么显然有递推式：dp[i]=min(dp[i],dp[j]+(cnt[i]−1)×j+i)。

其中，cnt[i] 为数字 i 的个数。

为何呢？因为我们删掉 cnt[i]−1 个数之前，MEX 都是上一个被删掉的数，而将最后一个删完后，MEX 变成了当前的数。

时间复杂度：O(n2)

对应AC代码

C++
#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