构造+背包+bitset。

Solution

牛逼题。

题目意外的保证了$m\ge n-2$所以肯定往这上面想。

首先观察样例猜结论，肯定是用大的数去补小的数，仔细想想，对于$m=n-1$这样操作在前$n-2$次就会消掉$n-2$个数，最后一对数一定会在最后一次操作时消掉。

再来想想$m>n-1$的情况，这也比较好办，只要将多的菜用一种材料完成，即可将问题转化成$m=n-1$。

最阴间的$m=n-2$，我们依旧延续上文的想法，将其和$m=n-1$联系起来，可以发现将$n,m$拆两部分，每一部分都满足$\sum_{i\in S}d_i=(|S|-1)k$即可，这个东西是可以$dp$的，但是发现这么做显然不优，于是考虑再进行一步转化，对左右两边都减一个$|S|k$，原式就等于$\sum_{i\in S} d_i-k=-k$，这个东西就可以直接跑背包，这是可以用$bitset$优化的（~~但我就是想不到~~），首先将负数全部转正，然后左移右移即可。

复杂度：$O(\frac{n^2k}{w})$。本人跑的贼慢。

Code

#include<bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while('0' > c || c > '9') { if(c == '-') flag = 1; c = getchar();}
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...Arg>
inline void read(T &res, Arg &...com){ read(res), read(com...);}
template <class T>
void out(T res)
{
    if(res > 9) out(res / 10);
    putchar(res % 10 + '0');
}
template <class T>
inline void write(T res)
{
    if(res < 0) putchar('-'), res = -res;
    out(res), putchar('\n');
}
const int N = 500 + 5, M = 5000000 + 5;
int n, T, m, k;
int d[N];
priority_queue<PII>q;
inline void solve()
{
    for(int i = 1;i <= n;i ++) q.push({d[i], i});
    while(m != n - 1)
    {
        PII o = q.top();
        q.pop();
        o.first -= k;
        printf("%d %d\n", o.second, k);
        q.push(o);
        m --;
    }
    while(!q.empty()) d[q.top().second] = q.top().first, q.pop();
    while(m --)
    {
        int minn = 1e9 + 7, id_minn, maxn = 0, id_maxn;
        for(int i = 1;i <= n;i ++)
            if(d[i] != 0)
            {
                if(minn >= d[i]) id_minn = i, minn = d[i];
                if(maxn <= d[i]) id_maxn = i, maxn = d[i];
            }
        printf("%d %d %d %d\n", id_minn, minn, id_maxn, k - minn);
        d[id_maxn] -= k - minn, d[id_minn] = 0;
    }
}
bitset<M>s[505];
int vis[N];
PII st[N];
int hh;
inline void pout()
{
    int cnt = hh - 1;
    while(cnt --)
    {
        PII minn = {1e9 + 7, 0}, maxn = {0, 0};
        int id_maxn, id_minn;
        for(int i = 1;i <= hh;i ++)
            if(st[i].first != 0)
            {
                if(minn >= st[i]) id_minn = i, minn = st[i];
                if(maxn <= st[i]) id_maxn = i, maxn = st[i];
            }
        printf("%d %d %d %d\n", minn.second, minn.first, maxn.second, k - minn.first);
        st[id_minn].first -= minn.first, st[id_maxn].first -= k - minn.first;
    }
}
inline void split()
{
    int sum = n * k;
    if(n == 3) return puts("-1"), void();
    for(int i = 0;i <= n;i ++) s[i].reset(), vis[i] = 0;
    for(int i = 1;i <= n;i ++) d[i] -= k;
    s[0][sum] = 1;
    for(int i = 1;i <= n;i ++)
    {
        if(d[i] > 0) s[i] = s[i - 1] | (s[i - 1] << d[i]);
        else s[i] = s[i - 1] | (s[i - 1] >> (-d[i]));
    }
    if(!s[n][sum - k]) return puts("-1"), void();
    int last = sum - k;
    hh = 0;
    for(int i = n;i >= 1;i --)
        if(s[i - 1][last - d[i]]) last -= d[i], vis[i] = 1;
    for(int i = 1;i <= n;i ++) 
        if(vis[i]) st[++ hh] = {d[i] + k, i};
    pout();
    hh = 0;
    for(int i = 1;i <= n;i ++)
        if(!vis[i]) st[++ hh] = {d[i] + k, i};
    pout();
}
inline void work()
{
    read(n, m, k);
    for(int i = 1;i <= n;i ++) read(d[i]);
    if(m >= n - 1) return solve();
    return split();
}
int main()
{
    read(T);
    while(T --) work();
    return 0;
}

Luckyleaves's Blog

NOI2020 制作菜品

Solution

Code