周赛Round53

D.小红组比赛

题意

n场比赛，每场m道题，每一道题有一个难度分数，每一场选一道题出来组成的难度分数要最接近target,问最小差值是多少

思路

1. 这个问题和背包问题中的装箱问题类似，尽可能把背包装满。数据范围也不大
2. 我们可以用dp[i][x] 表示前i场比赛中获得x分可不可能，也就是开一个bool数组

代码

#include <bits/stdc++.h>
// 动态规划 
// dp[i][j] 前i场比赛有没有可能获得j分
// 类比装箱问题
int mar[105][25] = {0};
bool dp[105][5005] = {0};
int main()
{
    int n = 0, m = 0;
    std::cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            std::cin >> mar[i][j];
        }
    }
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            for (int k = 0; k <= 5000; k++)
            {
                if (k >= mar[i][j] && dp[i][k] == 0) // 注意一旦有可能，那他就有可能，这里防止再次被后续的修改
                {
                    dp[i][k] = dp[i - 1][k - mar[i][j]];
                }
            }
        }
    }
    int target = 0, ans = 0x7f7f7f7f;
    std::cin >> target;
    for (int i = 0; i <= 5000; i++)
    {
        if (dp[n][i])
        {
            ans = std::min(ans, abs(i - target));
        }
    }
    //std::cout << dp[3][9] << std::endl;
    std::cout << ans << std::endl;
    return 0;
}

E. 折半丢弃

题意

一个数组，每次任意选一个数，/2（向下取整），使得序列的MEX最大 MEX：没有出现在数组中的最小非负整数

思路

1. 假如MEX是t的话，那么数组中0 —— t - 1都要出现
2. 假如答案是ans, t < ans的话， MEX可以继续变大， t > ans 的话， MEX就要缩小了
3. 那么对MEX的检验满足单调性，就可以二分答案了

代码

#include <bits/stdc++.h>
int nums[100010] = {0};
int n = 0;
// mex = t时，序列中0 —— t-1一定都出现了
// 这个时候 >= t 的数都可以做出贡献
// 可以一直/2 然后看有没有没有出现的数
// 对mex的检查满足单调性，所以可以二分答案

bool check(int x)
{
    std::set<int> s;
    for (int i = 0; i < n; i++)
    {
        int y = nums[i];
        while(y >= x)
        {
            y /= 2;
        }
        while(y > 0 && s.count(y) != 0)
        {
            y /= 2;
        }
        s.insert(y);
    }
    if (s.size() == x)
    {
        return true;
    }
    return false;
}

void solve()
{
    std::cin >> n;
    for (int i = 0; i < n; i++)
    {
        std::cin >> nums[i];
    }
    
    int l = 0, r = n + 1;
    while(l < r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
        {
            l = mid + 1;
        }
        else
        {
            r = mid;
        }
    }
    std::cout << l - 1 << std::endl;
    
}

int main()
{
    int t = 0;
    std::cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}