Codeforces Round 901 (Div

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;
}