P9234 [蓝桥杯 2023 省 A] 买瓜 题解

· · 题解

对于每个瓜，显然有三种状态：不买、买一半和买。考虑使用折半搜索，把 n 个瓜分为两部分分别枚举状态，记录每种状态瓜的总重和劈瓜数量，再用哈希表找两边总重为 m 的状态。时间复杂度 O(3^{\frac{n}{2}})。
经测试我的写法 std::unordered_map 会 TLE，gp_hash_table 会 MLE，所以手写了一个哈希表。

实现中可以将瓜重和 m 都乘 2 避免出现浮点数。

struct map {
    static constexpr u32 P = 20000003, N = 143500000;

    u32 _u[N], _next[N];
    uint8_t _v[N];
    u32 h[P], cnt;

    uint8_t& operator[](u32 u) {
        u32 U = u % P;
        for (u32 i = h[U]; i; i = _next[i])
            if (_u[i] == u)
                return _v[i];
        cnt++;
        _u[cnt] = u;
        _next[cnt] = h[U];
        _v[cnt] = -1;
        h[U] = cnt;
        return _v[cnt];
    }
    uint8_t get(u32 u) {
        u32 U = u % P;
        for (u32 i = h[U]; i; i = _next[i])
            if (_u[i] == u)
                return _v[i];
        return -1;
    }
} g;
int main() {
    dR(u32, n, m), m *= 2;
    dRV(u32, a, n);
    for (auto&& x: a)
        x *= 2;
    [&](auto&& a) {
        u32 n = len(a);
        std::vector<u64> sum(1u << n); // 预处理不劈瓜时瓜重
        for (u32 i = 0; i < n; i++)
            sum[1u << i] = a[i];
        for (u32 S = 1; S < (1u << n); S++)
            sum[S] = sum[lowbit(S)] + sum[S ^ lowbit(S)];
        for (u32 S = 0; S < (1u << n); S++) {
            for (u32 T = S;; T = (T - 1) & S) { // 枚举三进制状态
                u64 s = sum[T] / 2 + sum[S ^ T];
                if (s <= m)
                    chkmin(g[s], __builtin_popcount(T));
                if (!T)
                    break;
            }
        }
    }(std::vector(a.begin(), a.begin() + n / 2));
    uint8_t ans = -1;
    [&](auto&& a) {
        u32 n = len(a);
        std::vector<u64> sum(1u << n);
        for (u32 i = 0; i < n; i++)
            sum[1u << i] = a[i];
        for (u32 S = 1; S < (1u << n); S++)
            sum[S] = sum[lowbit(S)] + sum[S ^ lowbit(S)];
        for (u32 S = 0; S < (1u << n); S++) {
            for (u32 T = S;; T = (T - 1) & S) {
                if (__builtin_popcount(T) < ans) {
                    u64 s = sum[T] / 2 + sum[S ^ T];
                    if (s <= m)
                        if (auto&& v = g.get(m - s); v != 0xff)
                            chkmin(ans, __builtin_popcount(T) + v);
                }
                if (!T)
                    break;
            }
        }
    }(std::vector(a.begin() + n / 2, a.end()));
    writeln(ans == 0xff ? -1 : ans);
    return 0;
}