XSY 押题！/se
对于一类问题：
有 \(n\) 种不同的饮料，第 \(i\) 种有 \(a_i\) 升。你需要把它们分到 \(m\) 个瓶子里面，每个瓶子容量为 \(k\)，你的分配方案需要满足：
- 每个瓶子都被装满，题目保证满足 \(mk=\sum a_i\)。
- 每个瓶子内至多有两种饮料。
求出任意一组合法的方案或判定无解。
为了方便，我们将当前情况下的所有饮料按 \(a\) 从小到大排序。
引理1：当 \(m=n-1\) 时一定有解。
首先由于 \(m<n\)，所以必然有 \(a_1<k\)。
发现此时 \(a_1+a_n\) 必定大于等于 \(k\)，否则：
\[\begin{aligned} &a_1+a_n<k\\ \to &\forall i,a_i<k\\ \to &\sum_{i=2}^{n-1}a_i<(n-2)k\\ \to &\sum_{i=1}^n a_i<(n-1)k \end{aligned} \]所以我们可以用完 \(a_1\)，然后用 \(a_n\) 填充剩下的 \(k-a_1\)。此时瓶子数量 \(m\) 减一，饮料数量 \(n\) 减一或减二，继续进入到 \(m=n-1\) 或 \(m=n\) 的情况。
引理 2：当 \(m\geq n\) 时一定有解。
由于 \(m\geq n\)，所以必然有 \(a_n\geq k\)。所以我们可以单独用 \(a_n\) 来填充一瓶，此时瓶子数量 \(m\) 减一，饮料数量 \(n\) 不变或减一，进入到 \(m\geq n\) 或 \(m=n-1\) 的情况。
引理 3：当 \(m<n-1\) 时有解，当且仅当能将所有饮料分成 \(n-m\) 组，使得每一组的饮料集合 \(T\) 都满足 \(\sum _{i\in T} a_i=(|T|-1)k\)。
充分性：显然，因为每一组都是 \(m=n-1\) 的情况。
必要性：考虑证明每一种合法的方案都会被统计到。
考虑建立一张图，点集为每一种饮料，然后对于每一个瓶子，在瓶子中两种饮料之间连一条边（只有一种饮料就连自环），这样会连出来一张 \(n\) 个点 \(m\) 条边的非简单图，记 \(-X=m-n\)。
考虑每一个连通块，每个连通块的 \(|E|-|V|\) 必定大于等于 \(-1\)。
考虑往图中逐个加入每个连通块，并记录当前图中的 \(y=|E|-|V|\)。发现由于每加入一个连通块 \(y\) 至多减少 \(1\)，所以 \(y\) 的变化过程肯定可以被表示成：\(0,\cdots,-1,\cdots,-2,\cdots,-X+1,\cdots,-X\)，那么就容易分成 \(X\) 部分，每部分都是 \(m=n-1\) 的集合了。
于是当 \(m\geq n-1\) 的时候我们可以直接特判掉，否则问题变为：判定是否有一种分组方式使得分成 \(n-m\) 组且每一组的饮料集合 \(T\) 都满足 \(\sum _{i\in T} a_i=(|T|-1)k\)，并求出分组方案。
先转化一下变成 \(\sum_{i\in T}a_i-k=-k\)，令 \(a_i\gets a_i-k\)，现在每一组的要求就是 \(\sum_{i\in T}a_i=-k\)。
考虑 DP，朴素的子集 DP 可以做到 \(O(3^n)\)。
更加优秀的做法：暴力的思路是枚举每一种加入饮料的顺序，如果当前还未确定分组的饮料 \(a_i\) 的和为 \(-k\) 就贪心地把它们划为一组。看是否存在一种顺序使得某一时刻组数达到 \(n-m\)（此时还未加入的饮料的 \(a_i\) 的和一定是 \(0\)，把它们并入这一组即可）。这样做是正确的，因为我们枚举了每一种加入饮料的顺序，而若存在一种合法的方案，则一定存在一种加入顺序满足这个贪心正确（只需按组将所有饮料依次加入即可）。使用状压 DP 优化顺序的枚举即可做到 \(O(2^nn)\)。
【NOI2020】制作菜品，这题是分成两组，可以背包做到更优复杂度：
#include<bits/stdc++.h>
#define N 510
#define K 5010
#define fi first
#define se second
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
int T,n,m,k,d[N];
bool vis[N];
set<pii>s;
vector<pii>ans;
bitset<N*K*2>f[N];
void work()
{
while(!s.empty())
{
pii maxn=*(--s.end());
pii minn=*s.begin();
if(minn.fi+maxn.fi<k) break;
m--;
if(minn.fi>=k)
{
s.erase(maxn);
ans.push_back(mk(maxn.se,k));
maxn.fi-=k;
if(maxn.fi) s.insert(maxn);
}
else
{
s.erase(minn);
s.erase(maxn);
ans.push_back(mk(minn.se,minn.fi));
ans.push_back(mk(maxn.se,k-minn.fi));
maxn.fi-=(k-minn.fi);
if(maxn.fi) s.insert(maxn);
}
}
}
int main()
{
// freopen("dish3.in","r",stdin);
// freopen("dish3.out","w",stdout);
T=read();
while(T--)
{
ans.clear();
n=read(),m=read(),k=read();
for(int i=1;i<=n;i++) d[i]=read();
if(m==n-2)
{
s.clear();
for(int i=1;i<=n;i++) vis[i]=0;
bool flag=0;
f[0].reset();
f[0].set(n*k);
for(int i=1;i<=n;i++)
{
f[i]=f[i-1];
if(d[i]-k>=0) f[i]|=(f[i-1]<<(d[i]-k));
else f[i]|=(f[i-1]>>(k-d[i]));
if(f[i][n*k-k])
{
s.clear();
int ns=n*k-k;
for(int j=i;j>=1;j--)
{
if(!f[j-1][ns])
{
vis[j]=1;
s.insert(mk(d[j],j));
ns-=d[j]-k;
assert(f[j-1][ns]);
}
}
work();
assert(s.empty());
for(int j=1;j<=n;j++)
if(!vis[j]) s.insert(mk(d[j],j));
work();
assert(s.empty());
flag=1;
break;
}
}
if(!flag)
{
puts("-1");
continue;
}
}
else
{
s.clear();
for(int i=1;i<=n;i++) s.insert(mk(d[i],i));
work();
}
bool lst=0;
for(pii now:ans)
{
if(lst) printf("%d %d\n",now.fi,now.se),lst=0;
else if(now.se==k) printf("%d %d\n",now.fi,now.se);
else printf("%d %d ",now.fi,now.se),lst=1;
}
}
return 0;
}
#include<bits/stdc++.h>
#define N 25
#define PN 3000000
#define ll long long
#define INF 0x7fffffff
#define lowbit(x) (x&-x)
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
int f[PN];
int n,aa[N],pos[PN];
ll S,a[N],sum[PN];
int main()
{
// freopen("drink4.in","r",stdin);
// freopen("drink4.out","w",stdout);
n=read();
for(int i=1;i<=n;i++) aa[i]=read(),S+=aa[i],pos[1<<(i-1)]=i;
int maxn=(1<<n)-1;
for(int A=(n+1)>>1;A<=n+1;A++)
{
for(int i=1;i<=n;i++) a[i]=1ll*aa[i]*A-S;
sum[0]=0;
for(int i=1;i<=maxn;i++)
{
int t=lowbit(i);
sum[i]=sum[i^t]+a[pos[t]];
}
for(int i=1;i<=maxn;i++) f[i]=-INF;
f[0]=0;
for(int i=0;i<maxn;i++)
{
ll res=sum[i]+f[i]*S;
for(int j=1;j<=n;j++)
{
if(!((i>>(j-1))&1))
{
if(res+a[j]==-S) f[i|(1<<(j-1))]=max(f[i|(1<<(j-1))],f[i]+1);
else f[i|(1<<(j-1))]=max(f[i|(1<<(j-1))],f[i]);
}
}
}
if(f[maxn]>=n-A)
{
printf("%d\n",A);
return 0;
}
}
return 0;
}