Reincarnation

正因为梦易碎，才格外美好。

P6775 「NOI2020」制作菜品

发表于 更新于 分类于
本文字数： 4.9k 阅读时长 ≈ 4 分钟

非常好的 训练。

题目简介

题目名称：制作菜品
题目来源：

评测链接：https://www.luogu.com.cn/problem/P6775

形式化题意：有 种颜色的小球，颜色 有 个，一共有 个坑，每个坑能放 个小球。询问是否存在一种放球方案使得每个坑里的球至多有 种颜色。求出方案或报告无解。多测。

数据范围：

你发现数据点分为了三种部分：，所以我们也按照这个情况来进行讨论。

首先考虑 的情况，我们将 排序，因为有 ，所以如果存在一个 ，那么就一定存在一个 。

所以我们考虑贪心选择，首先填入 ，然后在坑中填入最大的 的一部分，然后 后重新排序。以此做 次就可以得到答案。

时间复杂度 ，可以通过 。

然后你发现这个方法在 时适用，因为每次操作会减少恰好一个颜色的小球，那么 次之后剩下的小球就是原本个数最多的，用于填补前 个剩下的部分。时刻注意 的条件，所以保证了任何情况下 都不成立。

但是你发现这个方法无法处理 的情况，因为这种情况会剩下两个颜色的小球，也就是在某一操作时，出现了 ，也就是剩下 个坑的时候 种球两两组合。然后你发现也只有在 的时候才有可能出现无解的情况。也就是剩下 个坑时剩下的 种球无法两两组合。

但上面的做法实在是太优美了，所以我们考虑把 向 转移。

我们找到 的一个真子集 ，那么我们有 ，也就是 ，所以，我们可以通过这种方式将 拆成两个 的子问题。

然后考虑怎么样找到这个 ，根据上面的性质，我们知道：

那么两边同时减去 得到：

那么这就是一个 可行性背包的问题，每个物品的体积为 ，背包大小为 ，求出恰好装满背包的方案。然后我们记录一下方案后按照 做两次就行了。

由于体积和容量涉及负数，所以我们开始的时候平移一下即可。

时间复杂度 。可以通过 ，怎么秽蚀呢？

然后考虑可行性背包的本质，我们将当前可行性状态记为 ，那么加入一个体积为 的物品，会产生新的状态为 ，实际上在二进制压缩中为 t|(t<<v)。也就是一次平移的问题。

所以经典优化，将 数组用 std::bitset 优化，执行左移右移。最后时间复杂度 。可以通过本题。

AC 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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
// ----- Eternally question-----
// Problem: P6775 [NOI2020] 制作菜品
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6775
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-10-06 08:11:21
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using Pir=std::pair<int,int>;
#define fir first
#define sec second
#define Mkr std::make_pair
const int MAXN=5e2+10,MAXM=5e3+10,MAXK=5e3+10,MAXS=5e6+10;
const int S=2.5e6;
int Test,N,M,K,D[MAXN];
inline void solve(std::vector<Pir>vec,int m)
{
	int Len=vec.size();
	for(int i=1;i<=m;++i)
	{
		std::sort(vec.begin(),vec.end());
		int pos=0;
		for(;pos<Len;++pos) if(vec[pos].fir) break;
		if(vec[pos].fir>=K)
		{
			write(vec[pos].sec,' ',K,'\n');
			vec[pos].fir-=K;
		}
		else
		{
			vec[Len-1].fir-=K-vec[pos].fir;
			write(vec[pos].sec,' ',vec[pos].fir,' ');
			write(vec[Len-1].sec,' ',K-vec[pos].fir,'\n');
			vec[pos].fir=0;
		}
	}
}
std::bitset<MAXS>Dp[MAXN];
int val[MAXN];
inline bool get(std::vector<Pir>&vec1,std::vector<Pir>&vec2)
{
	std::memset(Dp,0,sizeof(Dp));
	for(int i=1;i<=N;++i) val[i]=D[i]-K;
	Dp[0][S]=1;
	for(int i=1;i<=N;++i)
	{
		if(val[i]>=0) Dp[i]|=(Dp[i-1]<<val[i])|Dp[i-1];
		else Dp[i]|=(Dp[i-1]>>(-val[i]))|Dp[i-1];
	}
	if(Dp[N][S-K]==0) return 0;
	vec1.clear(),vec2.clear();
	int pos=N,posv=S-K;
	while(pos)
	{
		if(Dp[pos-1][posv-val[pos]])
		{
			vec1.push_back(Mkr(D[pos],pos));
			posv-=val[pos];
		}
		else vec2.push_back(Mkr(D[pos],pos));
		--pos;
	}
	return 1;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	while(Test--)
	{
		read(N,M,K);
		for(int i=1;i<=N;++i) read(D[i]);
		if(M>=N-1)
		{
			std::vector<Pir>vec;
			for(int i=1;i<=N;++i) vec.push_back(Mkr(D[i],i));
			solve(vec,M);
		}
		else
		{
			std::vector<Pir>vec1,vec2;
			bool ok=get(vec1,vec2);
			if(!ok) puts("-1");
			else solve(vec1,vec1.size()-1),solve(vec2,vec2.size()-1);
		}
	}
	return 0;
}
/*

*/
相关文章