前言

这题解不够新鲜，因为国庆疯玩了

$C$、$D$都是好题。

D. Jellyfish and Mex

题意

有 $n$ 个数，你可以删去其中一个数，然后将剩余的数的 $mex$ 累加进答案，问答案的最小值。

做法

$dp_i$ 表示当 $mex$ 为 $i$ 的时候，答案最小值是多少。

主要是这个状态不容易想到，一般大家都是直接定义这个状态为最终答案了吧，但这样就不好转移了。

所以 $dp$ 的转移很简单，$dp_i = dp_j + (cnt_i - 1)*j + i$。初始状态，$dp_{mex}=0$。

func solve() {
    n := read()
    a := make([]int, n + 1)
    t := make(map[int]int)
    for i := 1; i <= n; i++ {
        a[i] = read()
        t[a[i]]++
    }
    sort.Slice(a[1:], func(i, j int) bool {
        return a[1+i] < a[1+j]
    })
    mex := 0
    for i := 1; i <= n; i++ {
        if mex == a[i] {
            mex++
        }
    }

    //println(a[1:])
    f := make([]int, mex + 1)
    for i := 0; i <= mex; i++ {
        f[i] = int(1e18)
    }
    f[mex] = 0
    for i := mex; i >= 0; i-- {
        for j := i + 1; j <= mex; j++ {
            f[i] = min(f[i], f[j] + (t[i] - 1) * j + i)
        }
    }
    println(f[0])
}

C. Jellyfish and Green Apple

题意

给定$n,m$，分别代表有 $n$ 份苹果个 $m$ 个人，每次你可以将一份切割成为两份，问最少切多少次，能够平均的分给 $m$ 个人。

做法

先将 $n$ 对 $m$ 取模，然后再考虑怎么扩展 $n$ 变成 $m$ 的倍数。

这题可以从样例得到一点启发，和二进制有关，最后一个样例直接体现出来的是，如果 $m$ 是 $2$ 的幂次，$n$ 可以将低位的 $1$ 扩展到高位，这样就必定是 $m$ 的倍数了。

但如果 $m$ 不是 $2$ 的幂次呢？

这个时候和二进制的关系就不是很大了，不要陷入二进制的牛角尖。

考虑从 $n$ 中取出 $k$，操作这 $k$ 个后，能够有 $k*2^t=m$。一直这样操作，直到 $n=0$，所以有 $n\%k=0,m\%k=0$。那么显然 $k$ 越大越好，故 $k=gcd(n,m)$。

然后这题就做完了。

func solve() {
    n, m := read(), read()
    n %= m
    gcd := __gcd(n, m)
    n /= gcd
    m /= gcd
    if calc(m) > 1 {
        println(-1)
        return
    }
    ans := 0
    for i := 0; i < 30; i++ {
        if n >> i & 1 == 1 && (1 << i) < m{
            ans += (m / (1 << i) - 1) * (1 << i)
        }
    }
    println(ans * gcd)
}

B. Jellyfish and Game

题意

。。。很无聊的一个题，直接模拟就好了，他们一定会取对方的最大值，因为不这样的话，自己会越来越亏。

代码

func solve() {
    n, m, k := read(), read(), read()
    a := make([]int, n + 1)
    b := make([]int, m + 1)
    for i := 1; i <= n; i++ {
        a[i] = read()
    }
    for i := 1; i <= m; i++ {
        b[i] = read()
    }
    sort.Ints(a[1:])
    sort.Ints(b[1:])
    if k & 1 == 1 {
        if a[1] < b[m] {
            a[1], b[m] = b[m], a[1]
        }
    } else {
        if a[1] < b[m] {
            a[1], b[m] = b[m], a[1]
        }
        sort.Ints(a[1:])
        sort.Ints(b[1:])
        if b[1] < a[n] {
            b[1], a[n] = a[n], b[1]
        }
    }
    println(sum(a[1:]...))
}

A. Jellyfish and Undertale

题意

好长的题啊，我还很丢人的 $wa2$ 了。。。

大意大概是，你有一个炸弹，爆炸倒计时是 $b$，当 $b$ 归零的时候，就爆炸了。每秒钟 $b$ 减小 $1$。你可以延长爆炸时间，给定你 $n$ 个数，代表你能延长的时间，但是你最多能够将时间提升到 $a$。

问最终炸弹在什么时候爆炸。

做法

最多提升到 $a$，那不就是最多提升 $a-1$ 秒。

func solve() {
    a, b, n := read(), read(), read()
    ans := b
    for i := 1; i <= n; i++ {
        x := read()
        ans += min(a - 1, x)
    }
    println(ans)
}