P6775 [NOI2020] 制作菜品 题解
Moya_Rao
·
·
题解
感觉是非常好构造题，以及这是嘎嘎喵的第二篇黑题题解，开心喵。
咦，我的第一道黑题题解是 NOI 2019 啊？
这一道是 NOI 2020 诶 qwq。
这道题目有一个致命的，就是如果你想题的时候不看数据范围会死的很惨，否则，你会发现一个东西：
很奇怪的性质，这启示我们从这里入手。
分三种情况讨论。
### $m = n-1
发现如果最开始让 $d_n$ 不断消耗的话，可能导致前面需要超过 $2$ 中原料才能做成一道菜品，这是题目不支持的情况，**因此我们应该先尽可能消耗较小的 $d_1$**。
但是只用 $d_1$ 很可能不够，此时可以考虑最方便的操作，**将 $d_n$ 中取出 $k-d_1$ 和 $d_1$ 并起来得到 $k$**，这样就能做成一道菜了。此时，$m \gets m-1$ 且 $n \gets n-1$。
而当 $n=2$ 时剩下的 $d_1$ 和 $d_2$ **一定有 $d_1 + d_2 = k$**，放在一起构成一道菜即 $m=1$。
那么这种方案就能解决所有 $m = n-1$ 的问题了，也不可能无解。
当然，每次消耗原料做菜后都**需要重新对 $d$ 值排序**（保证单调性，否则之后就做不了了），总时间复杂度 $O(n^2 \log n)$，可以用插入排序把那个 $\log$ 省掉，不过没啥必要。
### $m \ge n
考虑向 m = n-1 转化，这样就可以套用 m = n-1 的构造方案了。
显然有结论 d_n \ge k（反证法），那么因为这个时候 m 是有多的，可以用前面构造 m = n-1 时被否掉的方案，也就是不断消耗 d_n。d_n > k 做一道菜 m 会减少而 n 不会，这让 m 向 n-1 逼近，总会达到 m=n-1；而 d_n = k 时当且仅当 d_1 = d_2 = \dots = d_n，这个时候一道一道做，做到最后肯定也用光了。
此时转化为 m = n-1 后套用前面的构造方案即可，如果什么时候 m=0 了也可以直接结束循环（构造完毕）。
m = n-2
最为复杂的一种情况。
可以发现在这个时候单独消耗一种会增加难度（不代表没有能单独消耗的方法，但是会增大 m 和 n 的差比如变成 m=n-3、m=n-4 等，属于没苦硬吃），不妨让每道菜都是由两种原料组成。
考虑对每次用的两种原料进行连边，因为 m = n-2，有 n 个点而只能连 m 条边，最后得到的是两棵树，也就是两个 m' = n' - 1 的方案，加起来就有一个 m = n-2 的方案了。
把式子简单拆一下得到 $\sum_{x \in S} d_x = k|S| - k$，注意到里面带有 $|S|$ 即**集合大小**，这个是不好做的，而**左边 $x$ 的个数恰好是 $|S|$**，$k$ 又是**定值**，所以可以移到左边去，即 $\sum_{x \in S}(d_x - k) = -k$。
发现这个东西，诶，不就是最简单的背包嘛？而且还是 **`bool` 类型的背包 DP**，直接做就行了。但是会出现负数，要加一个足够大的偏移量保证不越界。
无解就是**得不到合法非空子集 $S$** 的情况，有解的话一定要**还原方案**，不然无法进入两个子集分别构造 $m = n-1$ 答案。
时间复杂度为 $O(n \sum d)$ 即 $O(nmk)$ 的，过不太去，但前面提到了是 `bool` 类型的 DP，所以**可以用 `bitset` 优化一下**，最终时间复杂度为 $O(\frac{nmk}{w})$。
### sample code
代码内含有部分注释，希望能辅助你理解本题喵！
::::success[code && [submission](https://www.luogu.com.cn/record/280725581)]
```cpp
#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 505;
const int BIT = 5e6+5;
int T,n,m,k,d[N];
int id1[N],id2[N],len1,len2;
bitset<BIT> dp[N];//bitset 优化的 DP 数组
int read(){
int su=0,pp=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
return su*pp;
}
bool cmp_D(int x,int y){
return d[x]<d[y];//按 d 值从小到大对下标排序
}
void tback(int u,int sum){
//回溯寻找 dp 方案
if(!u)return;//到头了
int x=d[u]-k;
if(sum-x>=0&&dp[u-1][sum-x])
id1[++len1]=u,tback(u-1,sum-x);
//被 DP 选中，放进 1 类数组
else id2[++len2]=u,tback(u-1,sum);
//没被 DP 选中，放进 2 类数组
return;
}
void solve(int *id,int len){
//*id 为数组传参，len 为长度
//构造 m=n-1 情况的答案
sort(id+1,id+len+1,cmp_D);
//对下标数组按 d 值从小到大排序
while(len>1){
cout<<id[1]<<" "<<d[id[1]]<<" "<<id[len]<<" "<<k-d[id[1]]<<"\n";
//输出当前回合的构造步骤
d[id[len]]-=k-d[id[1]];//减少
for(int i=1;i<len;i++)id[i]=id[i+1];
len--;//移除已经用完的最小点
sort(id+1,id+len+1,cmp_D);//重新排序
}
return;//构造结束！
}
int main(){
T=read();
while(T--){
n=read(),m=read(),k=read();
for(int i=1;i<=n;i++)d[i]=read();
if(m==n-2){
//图不连通，可分为两棵树
//转为背包问题，用 bitset 优化
int pian=m*k;//偏移量
dp[0].reset();dp[0][pian]=1;//初始化
for(int i=1;i<=n;i++){
int x=d[i]-k;//贡献
if(x>=0)dp[i]=dp[i-1]|(dp[i-1]<<x);
else dp[i]=dp[i-1]|(dp[i-1]>>(-x));
//分正负考虑左移右移
}
if(!dp[n][pian-k]){
//不存在合法构造
cout<<"-1\n";continue;
}
len1=0,len2=0;
tback(n,pian-k);//回溯得到 DP 方案
solve(id1,len1),solve(id2,len2);
//分别对两个子集进行 m=n-1 形式的构造以得到最终答案
}else{
//m>=n-1 的情况
//如果 m>=n 则不断通过消耗最大值来减小 m
//如果 m=n-1 直接构造即可得到答案
for(int i=1;i<=n;i++)id1[i]=i;
//借用 id1 数组不再额外开浪费空间
sort(id1+1,id1+n+1,cmp_D);//按 d 值升序排序
while(m>=n&&m){//消耗最大值
int x=id1[n];//取最大值
cout<<x<<" "<<k<<"\n";//消耗
d[x]-=k;//修改 d 值实现本质消耗
if(!d[x])n--;//用光了
sort(id1+1,id1+n+1,cmp_D);//重新维护排序
m--;//做了一道菜了
}
solve(id1,n);//直接套用 m=n-1 构造方案即可
}
}
return 0;
}
```
::::
### 后记
非常适合练构造的好题，~~同时个人认为也是一道水黑~~。
最后希望看到这里的朋友能给嘎嘎喵留一个赞喵 /xin，真的非常谢谢你们啦！/qq