P9339 [JOISC 2023] Cookies

有 $n$ 种物品，每种物品有 $a_i$ 个，给你 $m$ 个数 $b_i$，你需要将物品分成尽可能少的组，使得

• 每组物品的种类两两不同。
• 每组物品的个数为 $b_i$ 之一。

若不可行输出 $-1$，否则给出最小的组数和方案。

$1 \le n,m,\sum a\le 15000$，$1 \le b_i \le n$。

先考虑，给你每组物品的个数后，怎样构造方案。发现相当于二分图匹配，记第 $i$ 组有 $c_i$ 个物品，那么存在方案当且仅当 $\sum a_i = \sum c_i$ 且存在完美匹配。第一条限制是好满足的，对于第二条限制，考虑 hall 定理。

记物品的个数组为左部点，有结论，若任意左部点的子集 $S$，都有

$$\sum_{i \in S} c_i \le \sum_{i \in N(S)} \min(|S|,a_i)$$

那么存在左部点的完美匹配。

证明

数学归纳法，记 $a_i$ 为右部点 $i$ 匹配后剩余的流量，对于左部点 $i$，选择前 $c_i$ 大的进行匹配，然后将 $i$ 删去。发现剩余的点仍满足上述限制。

若 $S \ne \emptyset$，那么 $N(S)=\{1,2,..,n\}$。从大到小依次选 $c_i$ 可使限制最紧。考虑 DP 求 $c$，将 $b$ 从大到小排序，记 $f_{i,j,k}$ 为考虑了前 $i$ 种个数，选择了 $j$ 组，总和为 $k$ 是否合法。转移就是完全背包。发现第二维需要 $\le \frac{\sum a}{b_i}$，那么时空复杂度均为 $O(n^2\log n)$（需要求方案所以不能压第一维）。用 bitset 优化，时空复杂度均为 $O(\frac{n^2\log n}{\omega})$。

构造方案按证明构造即可。

#include<bits/stdc++.h>
using namespace std;

#define U(x) ((int)x.size())
#define pb push_back
const int N=15e3+10,INF=1e9;
#define gc getchar()
#define rd read()
inline int read(){
	int x=0,f=0; char c=gc;
	for(;c<'0'||c>'9';c=gc) f|=(c=='-');
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

int n,m,sum=0,ans=-1,a[N],b[N],s[N],cnt[N],c[N];
vector<bitset<N>> f[N]; vector<int> vc; bitset<N> pre[N];
struct cmp{ bool operator()(int x,int y){ return a[x]<a[y]; } };
priority_queue<int,vector<int>,cmp> q;

int main(){

	n=rd; for(int i=1;i<=n;++i) sum+=(a[i]=rd),++s[1],--s[a[i]+1];
	for(int i=1;i<=sum;++i) s[i]+=s[i-1];
	for(int i=1;i<=sum;++i) s[i]+=s[i-1];
	m=rd; for(int i=1;i<=m;++i) b[i]=rd;
	sort(b+1,b+m+1,[&](int x,int y){ return x>y; });


	f[0].resize(1),f[0][0][0]=1;
	for(int i=0;i<=sum;++i) for(int j=0;j<=s[i];++j) pre[i][j]=1;
	for(int i=1,lim;i<=m;++i){
		lim=sum/b[i],f[i].resize(lim+1),f[i][0]=f[i-1][0];
		for(int j=0;j<=lim;++j){
			if(j<U(f[i-1])) f[i][j]=f[i-1][j];
			if(j>0) f[i][j]|=(f[i][j-1]<<b[i]);
			f[i][j]&=pre[j];
		}
	}
	for(int i=0;ans==-1&&i<=sum/b[m];++i) if(f[m][i][sum]==1) ans=i;

	if(ans==-1) return printf("-1\n"),0;

	for(int i=m,j=ans,k=sum;j;){
		for(;!f[i][j][k]||!f[i][j-1][k-b[i]];--i);
		c[j]=b[i],--j,k-=b[i];
	}

	printf("%d\n", ans);
	for(int i=1;i<=n;++i) q.push(i);
	for(int i=1;i<=ans;++i){
		printf("%d ", c[i]); vc={};
		for(int j=1;j<=c[i];++j){
			int u=q.top(); q.pop(),vc.pb(u);
			printf("%d ", u);
		}
		for(int v:vc) if(--a[v]) q.push(v);
		puts("");
	}

	return 0;
}