[NOI2020] 制作菜品——构造、01背包、bitset

看起来一脸不可做…过了很久还是不可做。

一看题解，woc！居然还有 m ≥ n − 2 mge n-2 m≥n−2 这个条件！

还有 m ≥ n − 1 mge n-1 m≥n−1 的部分分，这是个很明显的提示。先看看 m = n − 1 m=n-1 m=n−1 的情况，当 n = 2 n=2 n=2 的时候可以直接取。当 n > 2 n>2 n>2 的时候， d i d_i di​ 的最小值一定是 < k k >k >k 的，我们可以直接用完最小值，把最大值扣去一部分放回去，就变成了一个 m = n − 1 m=n-1 m=n−1，但 n n n 更小的情况。由于 n = 2 n=2 n=2 时有解，所以直接这么构造下去一定有解。

然后考虑 m ≥ n mge n m≥n 的情况，此时 d i d_i di​ 的最大值一定 ≥ k ge k ≥k，我们直接从最大值中取 k k k 即可规约到 m m m 更小的情况。最终会得到 m = 1 , n = 1 / 2 m=1,n=1/2 m=1,n=1/2 的情况，也是一定有解的。

最后是 m = n − 2 m=n-2 m=n−2 的情况，上面的讨论已经提示我们了，可以推出此时有解的充要条件为存在一个 { 1 , 2 , . . . , n } {1,2,...,n} {1,2,...,n} 的子集 S S S，使得 ∑ i ∈ S d i = ( ∣ S ∣ − 1 ) k sum_{iin S}d_i=(|S|-1)k ∑i∈S​di​=(∣S∣−1)k，也即 ∑ i ∈ S ( d i − k ) = − k sum_{iin S}(d_i-k)=-k ∑i∈S​(di​−k)=−k。找到子集了过后，子集和补集可以分别用上面的构造法。

找符合要求的子集只需要用01背包即可，由于只关心有无解所以DP值全是bool类型，可以用bitset优化，总复杂度 O ( T n 2 k w ) O(Tfrac{n^2k}{w}) O(Twn2k​)，居然能过。

#include//JZM yyds!!
#define ll long long
#define lll __int128
#define uns unsigned
#define fi first
#define se second
#define IF (it->fi)
#define IS (it->se)
#define END putchar('n')
#define lowbit(x) ((x)&-(x))
#define inline jzm
using namespace std;
const int MAXN=114514;
const ll INF=1e18;
ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[50],lpt;
void print(ll x,char c='n'){
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt>0)putchar(ptf[lpt--]^48);
	if(c>0)putchar(c);
}

int n,m,k,a[505];
struct cmp{
	bool operator()(int x,int y){
		if(a[x]^a[y])return a[x]st;
struct itn{
	int i,j,x;itn(){}
	itn(int I,int J,int X){i=I,j=J,x=X;}
};
vectoras;
void solve(const vector&s,int m){
	st.clear();
	for(int x:s)st.insert(x);
	while((int)st.size()>2){
		if(m>=(int)st.size()){
			int x=*st.rbegin();
			st.erase(x),as.emplace_back(itn(x,0,k)),a[x]-=k,m--;
			if(a[x]>0)st.insert(x);
		}else{
			int x=*st.begin(),y=*st.rbegin();
			st.erase(x),st.erase(y),m--;
			as.emplace_back(itn(x,y,a[x])),a[y]-=k-a[x],a[x]=0;
			if(a[y]>0)st.insert(y);
		}
	}if(st.size()==2){
		int x=*st.begin(),y=*st.rbegin();
		st.clear(),as.emplace_back(x,y,a[x]);
	}else if(st.size()==1)
		as.emplace_back(itn(*st.begin(),0,k)),st.clear();
}
const int AD=2500000;
bitset<5000000>f[501];
int main()
{
	for(int NND=read();NND--;){
		n=read(),m=read(),k=read(),as.clear();
		for(int i=1;i<=n;i++)a[i]=read();
		if(m==n-2){
			f[0].reset(),f[0][AD]=1;
			for(int i=1;i<=n;i++){
				if(a[i]-k>=0)f[i]=f[i-1]|(f[i-1]<<(a[i]-k));
				else f[i]=f[i-1]|(f[i-1]>>(k-a[i]));
			}if(!f[n][AD-k]){print(-1);continue;}
			vectorA,B;
			for(int i=n,j=AD-k,to;i>0;i--){
				to=j-a[i]+k;
				if(to<0||to>=(AD<<1)){B.push_back(i);continue;}
				if(f[i-1][to])A.push_back(i),j=to;
				else B.push_back(i);
			}solve(A,A.size()-1),solve(B,B.size()-1);
		}else{
			vectorA;
			for(int i=1;i<=n;i++)A.push_back(i);
			solve(A,m);
		}
		if((int)as.size()!=m){print(-1);continue;}
		for(auto&t:as){
			if(t.j)printf("%d %d %d %dn",t.i,t.x,t.j,k-t.x);
			else print(t.i,' '),print(k);
		}
	}
	return 0;
}