BZOJ 4345 Korale

发表于 | 更新于

Link

Solution

K非常大。。 由这个条件

先按权值从小到大排序，对于权值相同的，根据所用珠子集合的标号的字典序从小到大排序

可以启发得到一种想法：先找到第K大的权值，再构造相应字典序的解。 所以第一步需要找到第K大的权值，常用的思路是把选出的数字集合按照一些性质分类、扩展，用一个堆来维护(K个串)。对于这道题来说，有这样一种构造方法： 首先把整个序列排序 堆的每个节点维护一个数对<a,b>< a,b >，表示和为aa，编号的最大值为bb。扩展的时候，扩展出<a+v[b+1],b+1>< a+v[b+1],b+1 >和<a−v[b]+v[b+1],b+1>< a-v[b]+v[b+1],b+1 > 为什么这样就能不重不漏地取到前KK大的权值和呢？为什么不能呢。。不会严格证明，但是可以感受到这样确实是可以不重不漏地取到的。。一个集合，根据倒数第二个点取或者没取，只有一个前驱；不停地递归下去，肯定会回到状态<v[1],1>< v[1],1 > 在计算第KK大的权值和sumsum的同时，还要记录前KK大的权值和中有多少个和第KK大的权值和相同，设为cc。那么就需要构造出权值和为sumsum，字典序第cc大的集合。 让我万万想不到的是，构造的方法就是深搜。。每次找到最靠左的且小于当前总和的数字，减掉之后搜下去。。 想不明白复杂度？

Tips

如果能像这样先把权值搞掉只搜字典序，就大大简化了问题。。 字典序是有可能需要搜的。。。

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
#include "lucida"
using std::pair;
using std::greater;
using std::vector;
using std::sort;
using std::make_pair;
using std::priority_queue;
//using std::min;
#define min(x,y) ( (x)<(y)?(x):(y) )
typedef pair<int64,int> HeapNode;
const int MAXN=1000000+11,MAXK=1000000+11,INF=1e9+1e5,LOG=23;
int n;
struct SparseTable {
	int f[MAXN][LOG],log_2[MAXN];
	SparseTable(){}
	SparseTable(int*,int);
	int operator ()(int,int);
}RMQ;
SparseTable::SparseTable(int *a,int n) {
	log_2[0]=-1;
	for(int i=1;i<=n;++i) {
		f[i][0]=a[i];
		log_2[i]=log_2[i>>1]+1;
	}
	for(int j=1,endj=log_2[n];j<=endj;++j) {
		for(int i=1,endi=n-(1<<j)+1;i<=endi;++i) {
			f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
}
int SparseTable::operator ()(int l,int r) {
	if(l>r) return -INF;
	int lg=log_2[r-l+1];
	return min(f[l][lg],f[r-(1<<lg)+1][lg]);
}
int Leftmost(int lbd,int64 x) {
	//找lbd右边最靠左的<=x的数字的位置
	int L=lbd,R=n+1;
	while(L!=R) {
		int Mid=(L+R)>>1;
		if(RMQ(lbd,Mid)<=x) {
			R=Mid;
		} else {
			L=Mid+1;
		}
	}
	return L==n+1?-1:L;
}
int s[MAXN],a[MAXN],res[MAXN],rc,stack[MAXN],top;
bool DFS(int l,int64 rem,int& rep) {
	
	//os<<l<<' '<<rem<<'\n';

	if(rem==0) {
		if(--rep==0) {
			while(top)
				res[++rc]=stack[top--];
			return 1;
		}
		else 
			return 0;
	}
	else {
		for(;l<=n;++l) {
			//l只需要枚举关键点！
			l=Leftmost(l,rem);
			if(l==-1)
				break;
			else {
				stack[++top]=l;
				if(DFS(l+1,rem-s[l],rep))
					return 1;
				top--;
			}
		}
	}
	return 0;
}
int main() {
//	freopen("input","r",stdin);
	int K;is>>n>>K;
	K--;
	for(int i=1;i<=n;++i) {
		is>>a[i];
		s[i]=a[i];
	}
	sort(a+1,a+1+n);
	//从n个数字选出若干个构成一个集合
	//集合按照1.元素值之和 2.元素标号字典序 比较大小
	//求第K大的集合
	priority_queue<HeapNode,vector<HeapNode>,greater<HeapNode> > Q;
	int64 Ans=0;int rep=0;
	Q.push(make_pair(a[1],1));
	while(K--) {
		HeapNode cur=Q.top();Q.pop();
		if(chkmx(Ans,cur.first)) {
			rep=1;
		} else {
			rep++;
		}
		if(cur.second!=n) {
			int p=cur.second,s=cur.second+1;
			Q.push(make_pair(cur.first+a[s],s));
			Q.push(make_pair(cur.first-a[p]+a[s],s));
		}
	}
	os<<Ans<<'\n';
	new(&RMQ) SparseTable(s,n); 
	DFS(1,Ans,rep);
	for(int i=rc;i>=1;--i)
		os<<res[i]<<' ';//(i==1?'\n':' ');
	return 0;
}