[JLOI2015]装备购买

---

题解

高斯消元?
首先考虑如果是能否被异或出来应该怎么办?
按价值排序后从价格低的往价格高的插入线性基
能插入的就买下来

那么考虑线性基表示的是什么
线性基表示的是把一个数看做二进制数,每一位就是一维的空间
然后求能把所有向量包含在这个空间的最小向量集

考虑线性基在插入一个向量的时候做的是什么?
高斯消元!
把要插入的这一位消成0
如果消不成就把这个向量插入线性基
否则就继续往后找其他位

那么构建好的线性基本质上就是高斯消元消成的上三角矩阵
那么这个题就也是同理了
按照价值从小到大依次插入
然后考虑每一种属性
如果这种属性已经被占了并且ta有此属性
那么就想高斯消元那样消掉在这一位的这个东西
如果当前位没人占了并且ta现在仍然有该属性
那么就把现在的ta插入
这时插入的ta最高位就是该位,因为前面有属性的位已经被消掉了

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int M = 505 ;
const double EPS = 1e-5 ;
using namespace std ;

bool vis[M] ;
int n , m , ans1 , ans2 , lib[M] ;
struct Product { double val[M] ; int cst ; } p[M] ;
inline bool cmpcst(Product a , Product b) { 
	return a.cst < b.cst ; 
}
inline bool Insert(int idx) {
	for(int i = 1 ; i <= m ; i ++) {
		if(fabs(p[idx].val[i]) < EPS) continue ;
		if(!lib[i]) {
			lib[i] = idx ;
			return true ;
		}
		else {
			double tp = p[idx].val[i] / p[lib[i]].val[i] ;
			for(int j = i ; j <= m ; j ++)
				p[idx].val[j] -= tp * p[lib[i]].val[j] ;
		}
	}
	return false ;
}
int main() {
	scanf("%d%d",&n , &m) ;
	for(int i = 1 ; i <= n ; i ++) {
		for(int j = 1 ; j <= m ; j ++)
			scanf("%lf",&p[i].val[j]) ;
	}
	for(int i = 1 ; i <= n ; i ++) scanf("%d",&p[i].cst) ;
	sort(p + 1 , p + n + 1 , cmpcst) ;
	for(int i = 1 ; i <= n ; i ++) {
		if(!Insert(i)) continue ;
		else ++ ans1 , ans2 += p[i].cst ;
	}
	printf("%d %d
",ans1 , ans2) ;
	return 0 ;
}