Codeforces Round 901 (Div-526互联

C. Jellyfish and Green Apple

题解

显然$n \% m =0$，答案一定为$0$

如果$n > m$，我们显然可以将$n / m$的苹果分给每个人，然后再处理$n % m $

如果$n < m$，我们一定会将所有苹果一直对半切直到$n > m$，所以答案每次对半切一定会加$n$

直到$n \%m = 0$的时候结束

那么什么情况下无解呢？

我们考虑每次对半切会使得$n :=n * 2$，也就是说如果一个质因子$p,p\neq 2$在$m$中存在，但是在$n$中不存在，那么$n$不管怎么翻倍，永远不会出现$n \%m = 0$

那么这个该如何判断呢？

我们可以通过$\frac{m}{gcd(n,m)}=2^i$来判断

int n, m;

int lowbit(int x) { return x & -x; }

void solve()
{
    cin >> n >> m;
    if (n % m == 0)
    {
        cout << 0 << endl;
        return;
    }
    n = n % m;
    int r = m / gcd(n, m);
    if (r != lowbit(r))
    {
        cout << -1 << endl;
        return;
    }
    int ans = 0;
    while (true)
    {
        while (n * 2 < m)
        {
            ans += n;
            n <<= 1;
        }
        ans += n;
        n <<= 1;
        if (n % m == 0)
            break;
        n = n % m;
    }
    cout << ans << endl;
}

D. Jellyfish and Mex

$1 \leq n \leq 5000$

题解：$DP$

我们考虑$dp$

显然对于$a_i > mex$部分我们可以不用管

如果当前数组$a$的$mex$为$g$，我们想使得$x,x < g$成为$mex$，那么代价为$g \times (cnt[x] - 1) + x$

我们定义状态为：$dp[i]$：代表通过删除操作使得$mex = i$的最小代价

转移方程为：

\[dp[mex] = 0 \\ dp[i] = min \sum_{j = i + 1}^{mex}(dp[j] + j \times (cnt[i] - 1) + i) \]
倒序遍历$i$即可

显然答案为$dp[0]$

int n, a[N];
// dp[i] 代表通过删除操作使得 mex = i 的最小代价

void solve()
{
    cin >> n;
    map<int, int> mp;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        mp[a[i]]++;
    }
    int mex = -1;
    for (int i = 0;; ++i)
        if (!mp.count(i))
        {
            mex = i;
            break;
        }
    vector<int> dp(mex + 10, INF);
    dp[mex] = 0;
    for (int i = mex - 1; i >= 0; --i)
        for (int j = i + 1; j <= mex; ++j)
            dp[i] = min(dp[i], dp[j] + j * (mp[i] - 1) + i);
    cout << dp[0] << endl;
}