题解：P15051 [UOI 2023 II Stage] Nova Poshta

zszl · 2026-01-27 21:23:13 · 题解

前言

下文均采用 C++23 的标准。

洛谷题目

解法

先算货物总重，判断单辆卡车能否单独装下，能就直接输出；

若不能，二进制状态压缩枚举所有分给 Vasyl 的货物组合，验证合法则输出合作方案，无合法组合则输出无法完成。

时间复杂度分析

在 n 个货物的情况下时间复杂度为 O(2^nn)（欢迎大家改用 dfs 来加速）。空间复杂度 O(n)。

代码

#define ups(i,st,nd) for(int i=(st);i<(nd);++i)

int m[5];
int M1, M2, sum, w1, w2;

signed main() {
    ios::sync_with_stdio(false), ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); clock_t timr_start = clock();

    ups(i, 0, 5) read(m[i]), sum += m[i];
    read(M1, M2);

    if (sum < M1+1 && sum < M2+1) {
        write("They both can do it!");
        return 0;
    }
    if (sum < M1+1) {
        write("Vasyl can do it!");
        return 0;
    }
    if (sum < M2+1) {
        write("Petro can do it!");
        return 0;
    }

    ups(mask, 0, 32) {
        w1 = 0;
        ups(i, 0, 5) if (mask >> i & 1) w1 += m[i];
        w2 = sum - w1;
        if (w1 < M1+1 && w2 < M2+1) {
            write("They need to work together!\nVasyl: ");
            ups(i, 0, 5) if (mask >> i & 1) writes(i+1);
            write("\nPetro: ");
            ups(i, 0, 5) if (!(mask >> i & 1)) writes(i+1);
            return 0;
        }
    }

    write("They can not do it!");

    cerr << "time use " << (clock() - timr_start) << "ms.";
    return 0;
}

评价

可以作为新手学习状压的题目。