小红组比赛

分析

dp
暴搜很好写（但我还写挂了……），但过的点很少。记忆化优化，开个二维数组存储当前状态。

void dfs(int u,int sum)
{
    //if(dp[sum]!=-1)return;
    if(dp[u][sum])
    {
        ans=min(ans,dp[u][sum]);
        return;
    }
    if(u==n)
    {
        ans=min(ans,abs(z-sum));
        return;
    }
    for(int i=0;i<m;i++)
    {
    dfs(u+1,sum+a[u][i]);
    dp[u+1][sum+a[u][i]]=ans;
    }
}

正解 dp ，准确的说是个背包。
状态表示
$dp[i][j]$ 表示到第 $i$ 场比赛 $j$ 分数是否存在。
边界
$dp[0][0]=1$ 显然0场比赛分数是为0的，这个存在。
转移
对于当前的分数，暴力枚举每一场比赛的每一个分数，可以使得后一场比赛的加上上一场某个分数后的总分是存在的。
计算答案
因为第二维就是枚举的所有分数都选的情况下总分的情况，那只要存在的就与 $score$ 去比较，得出答案。

代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,m,z;
int a[5005][5005];
bool dp[5005][5005]={true};
int ans=1e9;
signed main()
{

    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    scanf("%d",&a[i][j]);
    scanf("%d",&z);

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            for(int k=0;k<=5000-a[i][j];k++)
            {
                dp[i+1][k+a[i][j]]=dp[i][k]||dp[i+1][k+a[i][j]];
            }
        }
    }

    for(int i=0;i<=5000;i++)
    {
        if(dp[n][i])
        {
            ans=min(ans,abs(z-i));
        }
    }
    cout<<ans;
    return 0;
}

折半丢弃

分析

由题意序列可排序，具有单调性可以看出用二分，然后就没有然后了，不会写。

代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+10;
int t,n;
void solve()
{
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a.begin(),a.end());
    //单调性可二分
    set<int>s;
    int i=0;
    for(auto &x:a)
    {
        while(x&&s.count(x))x/=2;
        s.insert(x);
    }
    while(s.count(i))i++;//s没有的最小非负整数
    while(s.size()&&*s.rbegin()>i)
    {
        int x=*s.rbegin();
        s.erase(x);
        x/=2;
        while(x&&s.count(x))x/=2;
        s.insert(x);
        while(s.count(i))i++;
    }
    cout<<i<<endl;
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--)solve();
    return 0;
}