前言

花田给点力啊别把老五人写崩了！/kk/kk/kk

题面

题解

这种题好像可以单独分一类：输出前 $K$ 小方案(的权值)

其大致思路都是通过找到一种紧邻的调整方法，保证后继状态一定比前驱状态大，方案不重复（大概），并且转移的时空复杂度合理。这样便可以用优先队列实时取出下一个状态。

这一题是两个套起来的此类问题。

首先考虑 $m=1$ 的情况，只有一种颜色。若 $l=r$（即背包大小确定），我们把序列 $a_i$ 排序，那么任意一种方案 { b 1 , b 2 , . . . , b l } ⊆ { 1 , 2 , 3 , . . . , n } \{b_1,b_2,...,b_l\}\sube\{1,2,3,...,n\} {b1​,b2​,...,bl​}⊆{1,2,3,...,n} 都可以通过如下转移唯一得到：

• 令 $x$ 为满足 $b_x>b_{x-1}+1$ （或 $x=1,b_1>1$）的最小值，那么把 { b 1 , b 2 , . . . , b x − 1 , . . . , b l } \{b_1,b_2,...,b_x-1,...,b_l\} {b1​,b2​,...,bx​−1,...,bl​} 定为前驱状态，从 { 1 , 2 , . . . , l } \{1,2,...,l\} {1,2,...,l} 一直转移过来。

这样一来，每个状态的后继就只有 2 种： { b 1 , b 2 , . . . , b x + 1 + 1 , . . . , b l } \{b_1,b_2,...,b_{x+1}+1,...,b_l\} {b1​,b2​,...,bx+1​+1,...,bl​} 和 { b 1 , b 2 , . . . , b x + 1 , . . . , b l } \{b_1,b_2,...,b_x+1,...,b_l\} {b1​,b2​,...,bx​+1,...,bl​} （前提是保证后继合法也就是 { b } \{b\} {b} 递增）。而且，一个状态有用的信息就只有：总和、$x$、$b_{x+1}$、$b_{x+2}$ 。打包起来放优先队列里维护就好。

然后考虑 $m>1$ 的情况。现在我们已经可以得到每一个背包的前 $K$ 小了，怎么利用这些前 $K$ 小的信息来组装全局前 $K$ 小呢？

这又是一个经典方法了：我们将背包按照 $次小方案-最小方案$ 的关键字从小到大排序，用序列 { c 1 , c 2 , . . . , c m } \{c_1,c_2,...,c_m\} {c1​,c2​,...,cm​} 表示总方案（$c_i$ 表示背包 $i$ 选择了第 $c_i$ 小的方案），那么有如下转移方案：

• 令 $x$ 为满足 $c_x>1$ 的最大值，则前驱状态为 { c 1 , c 2 , . . . , max ⁡ ( c x − 1 , 1 + [ c x = 2 ] ) , c x − 1 , . . . , c m } \{c_1,c_2,...,\max(c_{x-1},1+[c_x=2]),c_x-1,...,c_m\} {c1​,c2​,...,max(cx−1​,1+[cx​=2]),cx​−1,...,cm​} （即 $c_x$ 减少 1，若减到 1 了并且前一个位置为 1 ，则将前一个位置加一）。初始状态为 { 1 , 1 , . . . , c m = 1 } \{1,1,...,c_m=1\} {1,1,...,cm​=1} 。

由于我们的排序，前驱状态一定比该状态更小。每个状态的后继最多 3 种： { c 1 , c 2 , . . . , c x + 1 , . . . , c m } \{c_1,c_2,...,c_x+1,...,c_m\} {c1​,c2​,...,cx​+1,...,cm​}、 { c 1 , c 2 , . . . , c x , 2 , . . . , c m } \{c_1,c_2,...,c_x,2,...,c_m\} {c1​,c2​,...,cx​,2,...,cm​} 和 { c 1 , c 2 , . . . , c x − 1 , 2 , . . . , c m } ( c x = 2 ) \{c_1,c_2,...,c_x-1,2,...,c_m\}(c_x=2) {c1​,c2​,...,cx​−1,2,...,cm​}(cx​=2) 。有用的信息只有三个：总和、$x$、$c_x$ 。还是打包起来放优先队列。

时间复杂度 $O((n+m+k)\log (n+m+k))$ 。

CODE

#include
#include
#include
#include
#include
#include
#include
#include
#include
#pragma GCC optimize(2)
using namespace std;
#define MAXN 200005
#define LL long long
#define ULL unsigned LL
#define DB double
#define lowbit(x) (-(x)&(x))
#define ENDL putchar('\n')
#define FI first
#define SE second
#define PR pair<int,int>
inline 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<<3)+(x<<1)+(s^48);s=getchar();}
	return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar((x%10)^48);}
void putnum(LL x) {
	if(!x) {putchar('0');return ;}
	if(x<0) putchar('-'),x=-x;
	return putpos(x);
}
void AIput(LL x,int c) {putnum(x);putchar(c);}

int n,m,s,o,k;
vector<int> v[MAXN];
vector<int> b[MAXN];
vector<LL> a[MAXN];
#define prr pair<LL,pair<int,PR>>
#define prr2 pair<LL,PR>
priority_queue<prr,vector<prr>,greater<prr>> q[MAXN];
priority_queue<prr2,vector<prr2>,greater<prr2>> P;
void nexp(int i) {
	if(q[i].empty()) return ;
	auto t = q[i].top(); q[i].pop();
	int x = t.SE.FI,l = t.SE.SE.FI,r = t.SE.SE.SE;
	if(l < r-1) q[i].push({t.FI + v[i][l+1] - v[i][l],{x,{l+1,r}}});
	if(x && b[i][x-1] < l-1) {
		r = l; l = b[i][x-1]; x --;
		q[i].push({t.FI + v[i][l+1] - v[i][l],{x,{l+1,r}}});
	}
	if(q[i].empty()) return ;
	a[i].push_back(q[i].top().FI - t.FI);
	return ;
}
int id[MAXN],cn;
bool cmp(int x,int y) {
	return a[x].front() < a[y].front();
}
int main() {
	freopen("knapsack.in","r",stdin);
	freopen("knapsack.out","w",stdout);
	n = read(); m = read(); k = read();
	for(int i = 1;i <= m;i ++) v[i] = {0};
	for(int i = 1;i <= n;i ++) {
		s = read(); o = read();
		v[s].push_back(o);
	}
	bool flag = 1;
	LL ans = 0;
	for(int i = 1;i <= m;i ++) {
		int le = v[i].size()-1;
		sort(v[i].begin(),v[i].end());
		s = read();o = read();
		o = min(o,le);
		LL aa = 0;
		if(s > o || !flag) {flag = 0;continue;}
		if(o < 1) continue;
		for(int j = s+1;j <= o;j ++) b[i].push_back(0);
		for(int j = 1;j <= s;j ++) b[i].push_back(j),aa += v[i][j];
		q[i].push({aa,{o-1,{b[i][o-1],v[i].size()}}});
		nexp(i); ans += aa;
		if(!a[i].empty()) id[++ cn] = i;
	}
	sort(id + 1,id + 1 + cn,cmp);
	if(cn) P.push({ans + a[id[1]][0],{1,0}});
	if(!flag) {
		ans = -1;
		while(!P.empty()) P.pop();
	}
	for(int i = 1;i <= k;i ++) {
		AIput(ans,'\n');
		if(P.empty()) ans = -1;
		else {
			auto t = P.top();P.pop();
			ans = t.FI;
			int x = t.SE.FI,y = t.SE.SE;
			if(x < cn && !y) {
				P.push({t.FI+a[id[x+1]][0]-a[id[x]][0],{x+1,0}});
			}
			if(y+1 == (int)a[id[x]].size()) nexp(id[x]);
			if(y+1 < (int)a[id[x]].size()) {
				P.push({t.FI+a[id[x]][y+1],{x,y+1}});
			}
			if(x < cn) {
				P.push({t.FI+a[id[x+1]][0],{x+1,0}});
			}
		}
	}
	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

后记

输出树上的前 $K$ 大路径也是同一类问题，可以用边分治给状态分组，在边分树上枚举两个节点转移，但是一条路径可能在优先队列中紧挨着出现两次，状态只用两个点唯一标识，所以可用 set 代替优先队列简单去重一下。这就是为什么我在“方案不重复”后面写个“大概”。