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

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 个元素取为2i + 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);
}
05-11 22:34