K优解
Time Limit: 20 Sec Memory Limit: 512 MB
Description
给定n个行数,每行m个。在每行中选出一个数来,求出前 k 小的异或和。
Input
第一行 3 个正整数 n,m,k。
接下来 n 行,每行 m 个非负整数,第 i 行第 j 个为权值a[i][j]。
Output
一行一个数表示答案。
Sample Input
3 2 2
11 21
9 25
17 19
11 21
9 25
17 19
Sample Output
2
HINT
n*m<=300000,k<=300000,保证m^n>=k,a[i][j]均不超过10^9
Solution
先对于每个 i,将每行的 a[i][1]~a[i][m] 从小到大排序,再将行按照其元素差值为多关键字排序(共m-1个关键字)。
那么我们知道,最小的方案肯定是所有行都取第一个。由于其有一些特殊,我们先抛开这个方案。
我们知道,次小的方案是(2,1,1,1…),把这个状态加入堆,由较优方案扩展较劣方案,对于每一个状态,我们记录其扩展到第几行,以及取第几个元素。
在已经得到前 k 优的方案时,当前所有方案中还未扩展的最好的方案x(其最后扩展位置为 i),就是第 k+1 优。
从方案x,我们可以扩展出几个较劣解:
1、x 的第 i 个元素不取m:将 i 行取的元素增加1(扩展位置为 i)
2、i + 1 <= n:将 i+1 行取为2(扩展位置为 i+1)
3、x 的第 i 个元素取为2 且 i + 1 <= n:将 i 行取为1,i+1 行取为2(扩展位置为 i+1)
由此,每个解都可由唯一的优于它的解扩展得来。
用个堆维护一下,每次取出最小的即可。
Code
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
typedef long long s64; const int ONE = ;
const int MOD = 1e9 + ; int n, m, k;
vector <int> A[ONE];
int id[ONE];
s64 Ans; struct power
{
s64 val;
int pt, id;
bool operator <(power a) const
{
return a.val < val;
}
};
priority_queue <power> q; int cmp(int a, int b)
{
for(int i = ; i < m; i++)
{
if(A[a][i + ] - A[a][i] < A[b][i + ] - A[b][i]) return ;
if(A[a][i + ] - A[a][i] > A[b][i + ] - A[b][i]) return ;
}
return ;
} int get()
{
int res=,Q=; char c;
while( (c=getchar())< || c>)
if(c=='-')Q=-;
if(Q) res=c-;
while((c=getchar())>= && c<=)
res=res*+c-;
return res*Q;
} int main()
{
n = get(); m = get(); k = get();
for(int i = ; i <= n; i++)
{
A[i].push_back();
for(int j = ; j <= m; j++)
A[i].push_back(get());
sort(A[i].begin(), A[i].end());
id[i] = i;
} sort(id + , id + n + , cmp); s64 res = ;
for(int i = ; i <= n; i++) res += A[i][];
Ans = res; q.push((power){res - A[id[]][] + A[id[]][], , }); for(int i = ; i <= k; i++)
{
power u = q.top(); q.pop();
Ans ^= u.val; if(u.id + <= m)
q.push((power){u.val - A[id[u.pt]][u.id] + A[id[u.pt]][u.id + ], u.pt, u.id + });
if(u.pt + <= n && <= m)
q.push((power){u.val - A[id[u.pt + ]][] + A[id[u.pt + ]][], u.pt + , });
if(u.pt + <= n && u.id == )
q.push((power){u.val - A[id[u.pt]][] + A[id[u.pt]][] - A[id[u.pt + ]][] + A[id[u.pt + ]][], u.pt + , });
} printf("%lld", Ans);
}