[NOIP2015神奇五校模拟赛No.7]设置(settings)

发表于   |  

题目描述

如题所示，这将是一个关于设置的问题。
你需要通过对一个控制台进行设置，来得到不同的效果。
这个控制台由n个控制元件组成，每个元件有m种设置，其中i号元件的第j种设置将会给整体带来a[i][j]的效果值。
最终的效果值是所有n个元件所选设置的效果值之和。
然而，效果值并不是越大或越小越好，不同的效果值有不同的意义。
所以我们要求你给出效果值最小的那k种不同的方案（2种方案不同，当且仅当2种方案中存在至少1个元件的设置不同）。
不过由于我们其实并不关心你给出的那k种方案是什么，只需要弄清你是否能够找出那些方案，所以你只需要输出所有k种方案的效果值的异或和。

输入

第一行3个正整数n,m,k
接下来n行，每行m个非负整数，其中第i行第j个数表示第i个控制元件的第j种设置的效果值a[i][j]

输出

仅一行一个整数，表示k种方案的效果值的异或和

样例输入

3 2 2
11 21
9 25
17 19

样例输出

2

样例说明

最小的2种方案的效果值分别为37(11+9+17)和39(11+9+19)，异或和为37 xor 39 = 2
数据规模和约定
对于30%的数据，m^n<=10^6,k<=30000
对于另外30%的数据n<=100,nm<=50000,k<=50000
对于100%的数据，nm<=300000，k<=300000，保证m^n>=k，任意一个控制元件的任意一种设置效果值均不超过10^9

Solution

非常牛逼的枚举。。。 可以推广。

这其实是一个用堆求k优解的一般思路。
先对于每个i，将元件i的a[i][1]~a[i][m]从小到大排序，再将所有元件按照其(第2~第m种设置与第1种设置的差值)多关键字从小到大排序（共m-1个关键字）。
现在开始，我们将排在第i位的元件称为元件i，其第j小的设置称为元件i的设置j。
那么我们知道，最小的方案肯定是所有元件都设置为1。由于其有一些特殊，我们先抛开这个方案。（实际上不抛开也是可行的）
我们知道，次小的方案是(2,1,1,1…)，我们以此为起点s，由较优方案扩展较劣方案，对于每一个方案，我们记录其最后被扩展的位置（对于s，这个位置为1）。在已经得到前t优的方案时，当前所有方案中还未扩展的最好的方案x（其最后扩展位置为i），就是第t+1优。
从方案x，我们可以扩展出几个较劣解：
1、 i < n：将i+1号元件设置为2（扩展位置为i+1）
2、 x的第i个元件设置为2且i < n：将i号元件设置为1，i+1号元件设置为2（扩展位置为i+1）
3、x的第i个元件设置不为m：将i号元件设置增加1（扩展位置为i）
由此，每个解都可由唯一的优于它的解扩展得来。
用堆维护当前所有解即可。

以上方法保证了每次枚举的值都比之前的大并且没有遗漏。

不过还是调了很久

  1. 这题枚举不能从1111开始，会出现等于的情况导致重复。
  2. qsort打错了 mid要放在循环外面啊orz
  3. 进一步理解了怎么用c++指针
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXT 600000+100
#define MAXNheap 3000000
#define ll long long 
#define g(i,j) (i-1)*(m+1)+j
using namespace std;
int n,m,k;
ll a[MAXT];
struct data{
	int x,p;
	ll sum;
};
struct heap{
	int cnt,cmp;
	data h[MAXNheap];
	bool CMP(data a,data b){
		if (cmp) return (a.sum >= b.sum)? true:false;
		return (a.sum <= b.sum)? true:false;
	}
	inline void up(int n){
		for (int i=n;i>1;i=i/2)
			if (!CMP(h[i/2],h[i]))
				swap(h[i/2],h[i]);
			else break;
	}
	inline void down(){
		int tmp;
		for (int i=1;(i<<1)<=cnt;i=tmp){
			if (((i<<1)==cnt) || CMP(h[i<<1],h[(i<<1)+1]) ) tmp=(i<<1);
			else tmp=(i<<1)+1;
			if (!CMP(h[i],h[tmp])) swap(h[tmp],h[i]); else break;
		}
	}
	void push(data x){
		h[++cnt]=x;
		up(cnt);
	}
	void pop(){
		h[1]=h[cnt--];
		down();
	}
	data top(){
		return h[1];
	}
}q;

bool cmp2(ll* a,ll* b){
	for (int i=2;i<=m;i++){
		if (a[i]-a[1]<b[i]-b[1]) return true;
		if (a[i]-a[1]>b[i]-b[1]) return false;
	}
	return false;
}

ll mid[MAXT],tmp[MAXT];

void qsort(int tl,int tr){
	int l=tl,r=tr;
	memcpy(mid,a+g(((l+r)/2),0),(m+1)*sizeof(ll));
	do{ 
		while (cmp2(a+g(l,0),mid)) l++;
		while (cmp2(mid,a+g(r,0))) r--;
		if (l<=r) {
			memcpy(tmp,a+g(r,0),(m+1)*sizeof(ll));
			memcpy(a+g(r,0),a+g(l,0),(m+1)*sizeof(ll));
			memcpy(a+g(l,0),tmp,(m+1)*sizeof(ll));
			l++;r--;
		}
	}while(l<=r);
	if (tl<=r) qsort(tl,r);
	if (l<=tr) qsort(l,tr);
}

int main(){
	freopen(""in.txt"",""r"",stdin);
	freopen(""out.txt"",""w"",stdout);
	scanf(""%d%d%d"",&n,&m,&k);
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			scanf(""%d"",&a[g(i,j)]);
		}
	}
	data tmp;
	tmp.x=1;tmp.p=2;tmp.sum=0;
	for (int i=1;i<=n;i++){
		sort(a+g(i,1),a+g(i,1)+m);
		tmp.sum+=a[g(i,1)];
	}
	qsort(1,n);
	q.cmp=0;	
	ll ans=tmp.sum;
	tmp.sum=tmp.sum-a[g(1,1)]+a[g(1,2)];
	q.push(tmp);	
	for (int i=2;i<=k;i++){
		data t=q.top();
		q.pop();		
		ans^=t.sum;
		if (t.x<n){
			tmp.x=t.x+1;tmp.p=2;tmp.sum=t.sum+a[g(tmp.x,tmp.p)]-a[g(tmp.x,tmp.p-1)];
			q.push(tmp);
		}
		if (t.x<n && t.p==2){
			tmp.sum=tmp.sum-a[g(t.x,2)]+a[g(t.x,1)];
			q.push(tmp); 
		}
		if (t.p!=m){
			tmp.x=t.x;tmp.p=t.p+1;tmp.sum=t.sum+a[g(tmp.x,tmp.p)]-a[g(tmp.x,tmp.p-1)];
			q.push(tmp);
		}
	}
	cout<<ans<<endl;

}