LOJ#3342. 「NOI2020」制作菜品

构造题，但感觉并不算困难。

注意到部分分的设置，由浅入深大致分为 $m=n-1$，$m\ge n-1$，$m=n-2$ 几部分。我们按顺序进行思考。

$\mathbf{m=n-1}$

考虑将材料从大到小进行排序，为 $d_1\le d_2\le \cdots\le d_{n-1}\le d_n$。我们考虑以下两点：

Lemma 1: $d_1<k$。

Lemma 2: $d_1+d_n\ge k$。

我们容易构造出一种方案：每次取出最小的 $d_i$ 和最大的 $d_j$，将 $d_i\to 0,d_j\to d_i+d_j-k$。然后转化为 $m-1,n-1$ 的情况，做到 $m=0$ 完成构造。

$\mathbf{m>n-1}$

Lemma 3: $d_n\ge k$。

我们用 $d_n$ 单独做一道菜。这样就转化为 $m=n-1$ 的情况，使用上面的方法即可。

$\mathbf{m=n-2}$

我们尝试向 $m=n-1$ 转换。我们尝试将每种材料分成两个集合 $S,T$，设 $n_1=|S|,n_2=|T|$，满足 $\sum_{i\in S}d_i=(n_1-1)k$。相当于转化为两个 $m=n-1$ 的情况。显然问题有解当且仅当我们能够找到这样的 $S,T$。

于是我们相当于求 $\sum_{i\in S}(k-d_i)=k$ 的集合 $S$。这直接就是一个 01 背包问题。只用判断可行性，使用 bitset 优化即可做到 $\displaystyle \mathcal O(\frac{n^2k}{\omega})$。

代码还是比较好写的。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<vector>
#include<set>

using namespace std;
const int N=5e2+10,M=2.5e6+10;

template <class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template <class T>
inline void write(T res)
{
    if(res < 0) putchar('-'), res = -res;
    if(res > 9) write(res / 10);
    putchar(res % 10 + '0');
}
template <>
inline void write(char c) {putchar(c);}
template <>
inline void write(const char *s) { while(*s) putchar(*s ++); }
template <class T, class ...ARC>
inline void write(T res, ARC ...com) { write(res), write(com...);}

struct Node
{
    int id;
    int x;
    bool operator<(const Node &t)const{return x==t.x?id<t.id:x<t.x;}
};
int T,n,m,k;
vector<Node>a;
multiset<Node>s;
bitset<(M<<1)>f[N];
bool vis[N];
inline void work(const vector<Node> &a)
{
    s.clear();              
    for(auto x:a)if(x.x)s.insert(x);
    int si=s.size();
    for(int i=1;i<si;i++)
    {
        Node x=*s.begin(),y=*s.rbegin();
        s.erase(x),s.erase(y);
        write(x.id,' ',x.x,' ',y.id,' ',k-x.x,'\n');
        y.x-=k-x.x;
        s.insert(y);
    }
}
inline void solve()
{
    read(n,m,k);
    a.clear();
    for(int i=1;i<=n;i++)
    {
        int x;
        read(x);
        a.push_back({i,x});
    }
    if(m>=n-1)
    {
        for(auto &x:a)
        {
            while(x.x>=k&&m>n-1)
                x.x-=k,write(x.id,' ',k,'\n'),m--;
            if(!x.x)n--;
        }
        return work(a);
    }
    for(int i=0;i<=n;i++)f[i].reset();
    f[0][M]=1;
    for(int i=1;i<=n;i++)
    {
        int cost=k-a[i-1].x;
        if(cost>0)f[i]=f[i-1]|f[i-1]<<cost;
        else f[i]=f[i-1]|f[i-1]>>(-cost);
    }
    if(!f[n][M+k])return puts("-1"),void();

    int lim=n-1,now=k;
    vector<Node>ans;
    while(now)
    {
        for(int i=lim;~i;i--)
        {
            int cost=k-a[i].x;
            if(f[i][M+now-cost])
            {
                now-=cost;
                lim=i-1;
                ans.push_back(a[i]);
                break;
            }
        }
    }
    work(ans);
    memset(vis,0,sizeof(vis));
    for(auto x:ans)vis[x.id]=1;
    ans.clear();
    for(auto x:a)
        if(!vis[x.id])
            ans.push_back(x);
    work(ans);
}

int main()
{
    freopen("dish.in","r",stdin);
    freopen("dish.out","w",stdout);
    read(T);
    while(T--)solve();
    return 0;
}