专栏文章

题解：P6775 [NOI2020] 制作菜品

cchrisgr_pretty_girl
P6775题解参与者 5已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@mir1jqa5
此快照首次捕获于
2025/12/04 14:14
3 个月前
此快照最后确认于
2025/12/04 14:14
3 个月前
查看原文

m≥n−1m \ge n - 1

对于这种情况我们有一个显而易见的贪心，设数量最少的原料为第 ii 个，数量最多的原料为第 jj 个。如果 di≥kd_i \ge k 我们直接将其做成一道菜，否则我们将 did_i 全部用作一道菜，同时在这道菜中加入 djd_j 的一部分，使得其符合要求。
首先先证明一下贪心的正确性，将 dd 数组排序，假设不存在 d1+dn>kd_1 + d_n > k。
即假设 d1+dn≤kd_1 + d_n \le k。
因为 dd 为正整数，那么 dn<kd_n < k。
就有 ∑i=2n−1di<(n−2)⋅k\sum\limits_{i = 2}^{n - 1} d_i < (n - 2) \cdot k。
那么 ∑i=1ndi<(n−1)⋅k\sum\limits_{i = 1}^{n} d_i < (n - 1) \cdot k。
因为 ∑i=1ndi=m⋅k\sum\limits_{i = 1}^{n} d_i = m \cdot k 与 m≥n−1m \ge n - 1。
所以 ∑i=1ndi≥(n−1)⋅k\sum\limits_{i = 1}^{n} d_i \ge (n - 1) \cdot k。
与先前算的结果矛盾，所以假设不成立，在 m≥n−1m \ge n - 1 时一定存在 d1+dn>kd_1 + d_n > k 同时因为二者相加严格大于 kk 所以每次贪心后，两个原料一定还会剩下至少一部分，所以最劣情况也只会 m−1m - 1 同时 n−1n - 1 不会在贪心过程中出现 m<n−1m < n - 1 的情况。

m=n−2m = n - 2

对于这种情况，我们容易发现如果还按贪心做法，最终可能会出现 m=1m = 1 同时 n=3n = 3 的情况，方案不合法，所以我们需要考虑将 m=n−2m = n - 2 的情况转化为 m=n−1m = n - 1 的情况。
注意到当 m=n−2m = n - 2 时，可以将 mm 和 nn 分解为 m1=n1−1m_1 = n_1 - 1 和 m2=n2−1m_2 = n_2 - 1 那么只要我们对 dd 进行可行性背包，看是否可以将 dd 分为上述的两部分，并使用 bitset 优化，就可以通过本题了。
题解还没通过，口胡一个证明吧。
首先这个充分性肉眼可见，所以只需要证明必要性。
假设 m=n−2m = n - 2 分不出来两部分。
那么第一种情况 m=n−2m = n - 2 无法拆分，那么容易证明此时一定没有合法解（拆不出两部分说明，没有一道菜可以同时消耗掉两种原料，那么每次做菜只会使 m−1m - 1 同时 n−1n - 1 最后一定存在 m=1m = 1 同时 n=3n = 3 的情况）。
第二种情况，我们可以分出 m1>n1−1m_1 > n_1 - 1 和 m2<n2−1m_2 < n_2 - 1 两个部分，对于第一部分肯定有解，第二部分肉眼可见无法拆分为 m1′≥n1′−1m_1' \ge n_1' - 1 与 m2′≥n2′−1m_2' \ge n_2' - 1 两部分，所以必然存在不可分，或一部分 m<n−1m < n - 1 此时对于前者可以归类为第一种情况的证明，对于后者我们递归划分 m<n−1m < n - 1 的部分最后必然会出现不可分，或分出 m=1m = 1 同时 n=3n = 3 的情况，两种情况都不合法，所以第二种情况不合法（感觉没啥问题轻喷）。
题解还没过，来聊聊时间复杂度吧挤牙膏写法。
首先，贪心就算写的再丑陋也不是时间复杂度的大头（我写的是 O(nlog⁡n)\mathcal{O}(n \log n)）所以我们来分析一下背包的时间复杂度吧。很明显没有优化的时候，背包的时间复杂度是 O(n2⋅k)\mathcal{O}(n^2 \cdot k) 这个时间复杂度明显只能过前 17 个点，所以我们对其优化，之后时间复杂度为 O(n2⋅kw)\mathcal{O}(\frac{ n^2 \cdot k}{w}) 稳稳通过本题。
小细节：背包时有可能溢出，所以需要多开一点，并且初始化的值应该在中间。

CODE

CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 505;
int n, m, k, d[N];
bool book[N];
bitset<5000004>bag[N], kk;
void dfs(int x, int y) {
    if(!y) return;
    else if(!bag[x + 1][2500000 + y]) book[x] = 1, dfs(x + 1, y - d[x]);
    else dfs(x + 1, y);
}
struct node{ int id, d; };
bool operator <(const node & x, const node & y) { 
    if(x.d ^ y.d) return x.d < y.d;
    else return x.id < y.id;
}
int main() {
    //freopen("dish2.in", "r", stdin);
    //freopen("1.out", "w", stdout);
    int t;
    scanf("%d", &t);
    while(t--) {
    	//cout << t << endl << endl;
        scanf("%d%d%d", &n, &m, &k);
        for(int i = n; i; --i) scanf("%d", d + i);
        if(m == n - 2) {
            if(m == 3) {
				puts("-1");
                continue;
            }
            memset(book, 0, sizeof(book));
            int dd[N];
            for(int i = n; i; --i) {
                dd[i] = d[i];
                d[i] = k - d[i];
            }
            bag[n + 1][2500000] = 1, kk = 0, kk[2500000 + k] = 1;
            //cout << kk << endl;
            for(int i = n ; i; --i) {
                bag[i] = bag[i + 1] | (d[i] >= 0 ? bag[i + 1] << d[i] : bag[i + 1] >> -d[i]);
                //if(t == 5) cout << i << "  " << bag[i][k] << endl;
            }
            if((bag[1] & kk) == 0) {
                puts("-1");
                continue;
            }
            dfs(1, k);
            multiset<node> lc1, lc2;
            for(int i = n; i; --i) {
                if(book[i]) lc1.insert({n - i + 1, dd[i]});
                else lc2.insert({n - i + 1, dd[i]});
            }
            while(!lc1.empty()) {
                auto a = lc1.begin();
                node aa = *a;
                lc1.erase(a);
                printf("%d %d", aa.id, aa.d);
                if(aa.d < k) {
                    auto b = --lc1.end();
                    node bb = *b;
                    lc1.erase(b);
                    int bbb = k - aa.d;
                    printf(" %d %d", bb.id, bbb);
                    bb.d -= bbb;
                    if(bb.d) lc1.insert(bb);
                }
                putchar('\n');
            } while(!lc2.empty()) {
                auto a = lc2.begin();
                node aa = *a;
                lc2.erase(a);
                printf("%d %d", aa.id, aa.d);
                if(aa.d < k) {
                    auto b = --lc2.end();
                    node bb = *b;
                    lc2.erase(b);
                    int bbb = k - aa.d;
                    printf(" %d %d", bb.id, bbb);
                    bb.d -= bbb;
                    if(bb.d) lc2.insert(bb);
                }
                putchar('\n');
            } 
        } else {
            multiset<node> st;
            for(int i = n; i; --i) st.insert({n - i + 1, d[i]});
            while(!st.empty()) {
                auto a = st.begin();
                node aa = *a;
                st.erase(a);
                if(aa.d >= k) {
                    printf("%d %d", aa.id, k);
                    if(aa.d ^ k) {
                        aa.d -= k;
                        st.insert(aa);
                    }
                } else {
                    auto b = --st.end();
                    node bb = *b;
                    st.erase(b);
                    int bbb = k - aa.d;
                    printf("%d %d %d %d", aa.id, aa.d, bb.id, bbb);
                    bb.d -= bbb;
                    if(bb.d) st.insert(bb);
                }
                putchar('\n');
            }
        }
    }
    return 0;
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...