题面

🔗

题目描述

厨师准备给小朋友们制作 $m$ 道菜，每道菜均使用 $k$ 克原材料。为此，厨师购入了 $n$ 种原材料，原材料从 $1$ 到 $n$ 编号，第 $i$ 种原材料的质量为 $d_i$ 克。$n$ 种原材料的质量之和恰好为 $m\times k$ 克，其中 $d_i$ 与 $k$ 都是正整数。

制作菜品时，一种原材料可以被用于多道菜，但为了让菜品的味道更纯粹，厨师打算每道菜至多使用 $2$ 种原材料。现在请你判断是否存在一种满足要求的制作方案。更具体地，方案应满足下列要求：

• 共做出 $m$ 道菜。
• 每道菜至多使用 $2$ 种原材料。
• 每道菜恰好使用 $k$ 克原材料。
• 每道菜使用的每种原材料的质量都为正整数克。
• $n$ 种原材料都被恰好用完。

若存在满足要求的制作方案，你还应该给出一种具体的制作方案。

输入格式

本题单个测试点包含多组测试数据。

第一行一个整数 $T$ 表示数据组数。对于每组数据：

• 第一行三个正整数 $n,m,k$ 分别表示原材料种数、需要制作的菜品道数、每道菜品需使用的原材料的质量。
• 第二行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 种原材料的质量 $d_i$。

输出格式

对于每组测试数据：

• 若不存在满足要求的制作方案，则输出一行一个整数 $-1$;
• 否则你需要输出 $m$ 行，每行表示一道菜品的制作方案，根据使用的原材料种数，格式为下列两种之一：
  • 依次输出一行两个整数 $i$ 和 $x$，表示该道菜使用 $x$ 克第 $i$ 种原材料制作。你应保证 $1\le i\le n$，$x=k$。
  • 依次输出一行四个整数 $i$、$x$、$j$ 和 $y$，表示该道菜使用 $x$ 克第 $i$ 种原材料与 $y$ 克第 $j$ 种原材料制作。你应保证$1\le i,j\le n$，$i\ne j$，$x+y=k$，$x,y>0$。

本题使用自定义校验器检验你的答案是否正确，因此若有多种满足条件的方案，你只需要输出任意一种。

你应保证方案输出的格式正确，且同一行中相邻的两个数使用单个空格分隔，除此之外你的输出中不应包含其他多余字符。

样例 #1

样例输入 #1

4
1 1 10
10
4 3 100
80 30 90 100
5 3 1000
200 400 500 900 1000
6 4 100
25 30 50 80 95 120
1
2
3
4
5
6
7
8
9

样例输出 #1

1 10
1 80 2 20
2 10 3 90
4 100
-1
1 5 5 95
1 20 4 80
2 30 6 70
3 50 6 50
1
2
3
4
5
6
7
8
9

提示

样例 1 解释

对于第二组数据，一种满足要求的制作方案为：

• 使用 $80$ 克原材料 $1$ 与 $20$ 克原材料 $2$ 做第一道菜。
• 使用 $10$ 克原材料 $2$ 与 $90$ 克原材料 $3$ 做第二道菜。
• 使用 $100$ 克原材料 $4$ 做第三道菜。

样例 2

见选手目录下的 dish/dish2.in 与 dish/dish2.ans。

样例 3

见选手目录下的 dish/dish3.in 与 dish/dish3.ans。

---

测试点约束

对于所有测试点：
$1\le T\le 10$，$1\le n\le 500$，$n-2\le m\le 5000$，$m\ge 1$，$1\le k\le 5000$，${\sum }_{i=1}^n{d}_i=m\times k$。

每个测试点的具体限制见下表：

题解

完蛋了，场上绝对想不出来的，反正我是绝对想不出来的，部分分也是。

首先我们注意到这个条件 $m\ge n-2$ 。并且，发现有 $m\ge n-1$ 的部分分。

所以呢？完全没有思路啊！谁邒能想到有这么一个结论——

$m\ge n-1$ 一定有解呢？！！

通过反证法，或者直观想象（考场上只能靠这个了吧！）可以发现 $m\ge n-1$ 时满足
min ⁡ { d i } < k min ⁡ { d i } + max ⁡ { d i } ≥ k \min\{d_i\}min{di​}<kmin{di​}+max{di​}≥k

而且，这种方向也只能想到构造方法的时候才会注意吧：每次将最小值和最大值做一道菜，最小值花光（如果最大值也减到 0 就强制认为最大值没减完），成为 $m$ 少 1，$n$ 少 1 的更小的问题。

如果 $m\ge n$ ，直观想象可以发现 max ⁡ { d i } ≥ k \max\{d_i\}\geq k max{di​}≥k ，我们一直将最大的做一道菜，然后强制认为它不消失，一直做到 $m=n-1$ 为止，变成上一个问题。

如果 $m=n-2$ ，就非常麻烦，有个结论是怎么都想不到的：这种情况下有解当且仅当可以将菜和原材料分组划分为两个 $m=n-1$ 的问题。(证明)

也就是说，我们需要找到一个子集 $S$ ，满足 ${\sum }_{i\in S}{d}_i=(|S|-1)k\Rightarrow {\sum }_{i\in S}(d_i-k)=-k$ ，看右边的式子，明显我们可以用背包DP！

直接做是 $O(n^{2}k)$ 的，但是我们只需要判断是否有解，以及构造随便一组解，所以我们可以用 bitset 优化，并存下每一次的 bitset 来构造方案。

时间复杂度 $O(nm+\frac{n^{2}k}{\omega })$ 。

CODE

我原本以为，最终是看有没有到达 $-k$ 的，所以可以随机化将背包值域变成 $\sqrt{n}\cdot k$ ，但是居然怎么都会 WA ，太奇怪了。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAXN 50005
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define PR pair<int,int>
#define UIN unsigned int
int xchar() {
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
// #define getchar() xchar()
inline LL read() {
	LL f = 1,x = 0;int s = getchar();
	while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
	while(s >= '0' && s <= '9') {x = (x<<1) + (x<<3) + (s^48);s = getchar();}
	return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar((x%10)^48);}
inline void putnum(LL x) {
	if(!x) {putchar('0');return ;}
	if(x<0) putchar('-'),x = -x;
	return putpos(x);
}
inline void AIput(LL x,int c) {putnum(x);putchar(c);}

int n,m,s,o,k;
int d[MAXN];
bool f[MAXN];
PR a[MAXN],b[MAXN];
const int maxm = 5000*300,zr = 5000*150;
bitset<maxm> dp[505],emp;
int id[MAXN];
int ld[MAXN],rd[MAXN];
mt19937 ji(114514);
int main() {
	int T = read();
	while(T --) {
		n = read();m = read();k = read();
		for(int i = 1;i <= n;i ++) d[i] = read(),f[i] = 0;
		int mm = m;
		while(m >= n) {
			int md = 0;
			for(int i = 1;i <= n;i ++) {
				if(d[i] >= d[md]) md = i;
			}
			a[m] = {md,k}; b[m] = {0,0};
			d[md] -= k; m --;
		}
		if(m == n-1) {
			while(m > 0) {
				int mn = 0,mx = 0;
				for(int i = 1;i <= n;i ++) {
					if(f[i]) continue;
					if(!mn || d[i] < d[mn]) mn = i;
					if(!mx || d[i] >= d[mx]) mx = i;
				}
				a[m] = {mn,d[mn]}; b[m] = {mx,k-d[mn]};
				d[mx] -= (k-d[mn]); d[mn] = 0; f[mn] = 1;
				if(a[m].SE < b[m].SE) swap(a[m],b[m]);
				m --;
			}
		}
		else {
			for(int i = 0;i <= n;i ++) dp[i] = emp,id[i] = i;
			shuffle(id + 1,id + 1 + n,ji);
			dp[0][zr] = 1;
			for(int i = 1;i <= n;i ++) {
				int x = d[id[i]]-k;
				if(x > 0) {
					dp[i] = (dp[i-1]<<x)|dp[i-1];
				}
				else dp[i] = (dp[i-1]>>(-x))|dp[i-1];
			}
			if(!dp[n][zr-k]) {AIput(-1,'\n');continue;}
			int p = zr-k,c1 = 0,c2 = 0;
			for(int i = n;i > 0;i --) {
				int x = d[id[i]]-k;
				if(!dp[i-1][p]) ld[++ c1] = id[i],p -= x;
				else rd[++ c2] = id[i];
			}
			for(int I = 1;I < c1;I ++) {
				int mn = 0,mx = 0;
				for(int i = 1;i <= c1;i ++) {
					if(f[ld[i]]) continue;
					if(!mn || d[ld[i]] < d[mn]) mn = ld[i];
					if(!mx || d[ld[i]] >= d[mx]) mx = ld[i];
				}
				a[m] = {mn,d[mn]}; b[m] = {mx,k-d[mn]};
				d[mx] -= (k-d[mn]); d[mn] = 0; f[mn] = 1;
				if(a[m].SE < b[m].SE) swap(a[m],b[m]);
				m --;
			}
			for(int I = 1;I < c2;I ++) {
				int mn = 0,mx = 0;
				for(int i = 1;i <= c2;i ++) {
					if(f[rd[i]]) continue;
					if(!mn || d[rd[i]] < d[mn]) mn = rd[i];
					if(!mx || d[rd[i]] >= d[mx]) mx = rd[i];
				}
				a[m] = {mn,d[mn]}; b[m] = {mx,k-d[mn]};
				d[mx] -= (k-d[mn]); d[mn] = 0; f[mn] = 1;
				if(a[m].SE < b[m].SE) swap(a[m],b[m]);
				m --;
			}
		}
		for(int i = 1;i <= mm;i ++) {
			AIput(a[i].FI,' ');
			AIput(a[i].SE,' ');
			if(b[i].SE) {
				AIput(b[i].FI,' ');
				AIput(b[i].SE,' ');
			}
			ENDL;
		}
	}
	return 0;
}
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
130
131
132
133
134
135
136
137
138
139
140