P9339 [JOISC 2023] 曲奇 题解

Description

莉婕喜欢做饼干。她制作了 NN 种饼干。第 ii 种饼干有 AiA_i 个。为了出售她制作的饼干，她将它们装入盒子中。但是，应该满足以下条件。

  • 对于每个盒子，其中的饼干种类应不同。

  • 对于每个盒子，其中的饼干数量应等于以下 MM 个数字之一：B1,B2,⋯ ,BMB_1,B_2,⋯ ,B_M。

编写一个程序，给出莉婕制作的饼干信息和将饼干装箱的条件，确定是否可能将所有饼干包装到盒子中。此外，如果可以将所有饼干包装在盒子中，则您的程序应输出最少的盒子数量。

1≤M≤N≤15000,∑Ai≤150001\leq M\leq N\leq 15000,\sum A_i\leq 15000。

Solution

假设有 kk 个盒子，CiC_i 表示第 ii 个盒子的大小，考虑怎么判定一组 CiC_i 合法。

首先 ∑Ci=∑Ai\sum C_i=\sum A_i。

然后把 CiC_i 从大到小排序，那么前 jj 个盒子需要放 ∑i=1jCi\sum_{i=1}^{j}{C_i} 个饼干，而每种饼干在每个盒子最多放一个，所以需要满足 ∑i=1jCi≤∑i=1nmin⁡{Ai,j}\sum_{i=1}^{j}{C_i}\leq\sum_{i=1}^{n}{\min\{A_i,j\}}。

这个东西是必要条件，下面用 Hall 定理证明这个也是充分的。

首先建出二分图，左部点是盒子，右部点是饼干，SS 向第 ii 个盒子连流量 CiC_i 的边，第 ii 种饼干向汇点连流量 AiA_i 的边，第 ii 个盒子向第 jj 种饼干连流量为 11 的边。

根据 Hall 定理，对于任意盒子的子集 SS，需要满足 ∑i∈SCi≤∑j=1nmin⁡{Aj,∣S∣}\sum_{i\in S}{C_i}\leq\sum_{j=1}^{n}{\min\{A_j,|S|\}}，最劣情况一定是从大到小排序后的一段后缀，即上面的结论。

然后就可以 dp 了。

设 fi,j,kf_{i,j,k} 表示已经考虑了前 ii 大的盒子，选了 jj 个，总和为 kk 是否可行。

用 bitset 转移是 O(S3w)O\left(\frac{S^3}{w}\right) 的，但是由于 j≤SBij\leq \frac{S}{B_i}，所以总状态是 Slog⁡SS\log S 级别，复杂度优化为 O(S2log⁡Sw)O\left(\frac{S^2\log S}{w}\right)。

时间复杂度：O(S2log⁡Sw)O\left(\frac{S^2\log S}{w}\right)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 1.5e4 + 5;

int n, m, mm, s;
int a[kMaxN], b[kMaxN], c[kMaxN], lim[kMaxN], coef[kMaxN];
std::vector<std::bitset<kMaxN>> f[kMaxN];
std::bitset<kMaxN> g[kMaxN];

void getcc(int i, int j, int k) {
  // std::cerr << i << ' ' << j << ' ' << k << '\n';
  if (i == m + 1) return assert(!j && !k);
  while (1) {
    if (j < f[i + 1].size() && f[i + 1][j][k]) return getcc(i + 1, j, k);
    c[++mm] = b[i], --j, k -= b[i];
  }
}

void dickdreamer() {
  std::cin >> n;
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i];
    ++coef[1], --coef[a[i] + 1], lim[a[i] + 1] += a[i];
    s += a[i];
  }
  std::cin >> m;
  for (int i = 1; i <= m; ++i) std::cin >> b[i];
  for (int i = 1; i <= s; ++i) {
    lim[i] += lim[i - 1], coef[i] += coef[i - 1];
  }
  for (int i = 0; i <= s; ++i) {
    lim[i] += i * coef[i];
    g[i].reset(), g[i].flip();
    g[i] ^= (g[i] << (lim[i] + 1));
    // std::cerr << lim[i] << " \n"[i == s];
  }
  f[m + 1].resize(1), f[m + 1][0].reset(), f[m + 1][0][0] = 1;
  for (int i = m; i; --i) {
    f[i].resize(s / b[i] + 1);
    for (int j = 0; j < f[i].size(); ++j) f[i][j].reset();
    for (int j = 0; j < f[i + 1].size(); ++j) f[i][j] = f[i + 1][j];
    for (int j = 0; j < f[i].size(); ++j) {
      f[i][j] &= g[j];
      if (j + 1 < f[i].size()) f[i][j + 1] |= (f[i][j] << b[i]);
    }
    // std::cerr << "!!! " << b[i] << ' ' << f[i].size() << '\n';
  }
  int cnt = -1;
  for (int i = 0; i < f[1].size(); ++i) {
    if (f[1][i][s]) {
      cnt = i; break;
    }
  }
  if (!~cnt) return void(std::cout << "-1\n");
  getcc(1, cnt, s);
  std::cout << cnt << '\n';
  std::priority_queue<std::pair<int, int>> q;
  for (int i = 1; i <= n; ++i) q.emplace(a[i], i);
  for (int i = 1; i <= cnt; ++i) {
    std::vector<int> vec;
    for (int j = 1; j <= c[i]; ++j) {
      vec.emplace_back(q.top().second);
      q.pop();
    }
    std::cout << c[i] << ' ';
    for (auto x : vec) {
      std::cout << x << ' ';
      --a[x];
      assert(a[x] >= 0);
      // q.emplace(a[x], x);
      if (a[x]) q.emplace(a[x], x);
    }
    std::cout << '\n';
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}
P9339 [JOISC 2023] 曲奇 题解
https://sobaliuziao.github.io/2025/02/17/post/9203558.html
作者
Egg_laying_master
发布于
2025年2月17日
许可协议