题解：AT_abc480_f [ABC480F] Cake Cutting

· · 题解

ABC480F 题解

题意简述

有 N 块蛋糕，第 i 块大小为 A_i。总大小 S=\sum A_i，且 S 是 M 的倍数。

你可以任意次选择一块蛋糕切成两块。

最终要将所有蛋糕分成 M 份，每份大小均为 T = S/M。

求最少需要切多少刀。

数据范围：N \le 20，M \le 100，A_i \le 10^9。

分析

如果一块蛋糕或若干块蛋糕的总和为 k \times T，我们可以通过切割使它们恰好分成 k 份大小为 T 的蛋糕。 对于这样一组蛋糕，最多需要切 k-1 刀，因为分成 k 块有 k-1 个边界，最多就是 k-1 刀。

整个总大小是 M \times T。如果将所有蛋糕划分成 C 组，每组的总和都是 T 的倍数，设第 i 组大小为 k_i T，则总刀数为

\sum (k_i - 1) = \sum k_i - C = M - C。

因此，需要最大化划分组数 C。

问题转化为：将 N 个蛋糕划分成尽可能多的组，使得每组的总和是 T 的倍数。

实现

Step 1

由于 N \le 20，可以考虑状压枚举所有子集。

尝试贪心地从小到大枚举（即集合 st 的所有真子集在遍历到 st 之前已经被枚举过）。

这样就可以保证：对于所有的集合，如果选择它作为一个“块”（即该集合内元素和整除 T），那么它就是最小的可行解，因为它的所有真子集全部都不能单独成“块”。

综上，只要当前枚举到的集合可以“单独成块”，就贪心地让它立即“单独成块”。

进而可以保证得到的划分组数是最大的。

Step 2

现在考虑一个“块”的操作次数（切几刀）：

已知“块”中元素的下标，可以求得“块”的和 S。每个人平均分到大小为 T 的蛋糕，分成 k = \frac{S}{T} 块，切了 k-1 刀。 ans 累加 \frac{S}{T}-1。

Step 3

每一个块的和可以预处理出来：

枚举到集合 i 时，i 的真子集的和已经求出。

考虑子集 subi = i \oplus \operatorname{lowbit}(i)。

subi 中蛋糕大小的和加上 lowbit 处的蛋糕大小，即可得到集合 i 中蛋糕大小的和。

for (int i = 1; i < (1 << n); i++) {
    int lbt = i & (-i), j = __builtin_ctz(lbt);
    sum[i] = sum[i ^ lbt] + a[j + 1]; // 1-based
}

总时间复杂度 O(2^N)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N = 21;
int n, a[N], m, M, u, ans;
ll s, sum[(1 << N)], T;
int main() {
    cin >> n >> m;
    M = (1 << n);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s += a[i];
    }
    T = s / m;
    for (int i = 1; i < M; i++) { // 预处理 sum[st]
        int lbt = i & (-i), j = __builtin_ctz(lbt);
        sum[i] = sum[i ^ lbt] + a[j + 1];
    }
    for (int st = 1; st < M; st++) { // 优先枚举子集。
        if (u & st) {                // 如果当前集合 st 中已存在元素被使用过：continue;
            continue;
        }
        ll sst = sum[st];
        if (sst % T) { // 如果不能整除：continue;
            continue;
        }
        ans += sst / T - 1; // 分成 k 块需要 k-1 刀。
        u |= st;            // 标记被使用。
    }
    cout << ans << '\n';
    return 0;
}

:::info[关于GenAI的使用] 本文仅使用 DeepSeek 辅助修改错别字、标点及 Markdown 排版，未用于生成算法思路或代码。文章核心内容均由作者独立完成。 :::