设置（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种方案的效果值的异或和

样例输入

样例输出

提示

样例说明

最小的2种方案的效果值分别为37(11+9+17)和39(11+9+19)，异或和为37 xor 39 = 2

数据规模和约定

对于30%的数据，m^n<=10^6,k<=30000

对于另外30%的数据n<=100,n*m<=50000,k<=50000

对于100%的数据，n*m<=300000，k<=300000，保证m^n>=k，任意一个控制元件的任意一种设置效果值均不超过10^9

solution

我们考虑拿n维向量做状态，每一个点拓展出n个，标记判重，拓展出k大即可。

显然状态数太多了。

我们考虑减少一个状态的来源，使得每个状态仅被拓展一次。

那么可以考虑按顺序向后加。

也就是一个状态拓展到了第i位，那么他的后继状态一定拓展到>=i位

每一个点拓展出三个后继状态：i加一个块，i+1变成1个块，把1个块的i变成0个，i+1变成1个块

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#define maxn 300005
#define ll long long
using namespace std;
int n,m,k;
vector<int>a[maxn];
ll ans;
struct node{
    int x,num;ll v;
};
bool operator <(node a,node b){return a.v>b.v;}
priority_queue<node>q;
bool cmp(vector<int> a,vector<int> b){
    return a[1]-a[0]<b[1]-b[0];//////////////////////
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1,t;j<=m;j++){
            scanf("%d",&t);a[i].push_back(t);
        }
        sort(a[i].begin(),a[i].end());
    }
    sort(a+1,a+n+1,cmp);
    ll val=0;
    for(int i=1;i<=n;i++)val+=a[i][0];
    /*
    for(int i=1;i<=n;i++){
    for(int j=0;j<m;j++)cout<<a[i][j]<<' ';cout<<endl;
}*/
    q.push((node){1,0,val});
    while(k){
        //cout<<"k "<<k<<endl;
        node t=q.top();q.pop();
        k--;ans^=t.v;
        //printf("id=%d num=%d v=%lld
",t.x,t.num,t.v);
        if(t.num<m-1)q.push((node){t.x,t.num+1,t.v-a[t.x][t.num]+a[t.x][t.num+1]});
        if(t.num>0&&t.x<n)q.push((node){t.x+1,1,t.v-a[t.x+1][0]+a[t.x+1][1]});
        if(t.num==1&&t.x<n){
            ll nv=t.v+a[t.x][0]-a[t.x][1];
            nv=nv+a[t.x+1][1]-a[t.x+1][0];
            q.push((node){t.x+1,1,nv});
        }
    }
    cout<<ans<<endl;
    return 0;
}

View Code