bzoj4004,戳我戳我

Solution:

• 裸的线性基，这没啥好说的，我们说说有意思的地方（就是我老是wa的地方）

Attention:

• 这题在\(luogu\)，上貌似不卡精度，\(bzoj\)卡精度(一开始还以为自己精度被卡的很惨，结果是线性基打错了)
• 线性基板子：

    for(int j=50;j>=0;j--){

      if(!(box>>j))continue;

      if(!a[j]){a[j]=box;break;}

      else box=(a[j]^box);

    }

• 注意不是一个个动态开位置存线性基，而是像高斯消元一样存一个倒三角
• 然后我们要注意的就是线性基的制作方式，这道题表达意思是要前面存在过的装备组合相加得到，那么我们消元的时候是拿存在的线性基的倍数消元
  
  是这个样子：

double X=eqt[num].a[i]/x[i][i];

    for(int j=i;j<=m;j++){

    eqt[num].a[j]-=(x[i][j]*X);

}

不是这个样子（他和高斯小消元还是有点小不同（我觉得可能是我的高斯消元板子写错了））

double X=x[i][i]/eqt[num].a[i];

    for(int j=i;j<=m;j++){

        eqt[num].a[j]*=X;

        eqt[num].a[j]-=x[i][j];

    }

Code:

//It is coded by Ning_Mew on 5.27

#include<bits/stdc++.h>

#define double long double

using namespace std;

const int maxn=507;

const double eps=1e-5;

int n,m,ans=0,sum=0;

struct Node{

  double a[maxn];int val;

}eqt[maxn];

double x[maxn][maxn];

bool cmp(const Node &xx,const Node &yy){return xx.val<yy.val;}

double ffabs(double xx){return xx<0?-xx:xx;}

bool par(int num){

  bool kk=false;

  for(int i=1;i<=m;i++){

    if(fabs(eqt[num].a[i])<eps)continue;

    if(fabs(x[i][i])<eps){

      for(int j=i;j<=m;j++){x[i][j]=eqt[num].a[j];}

      kk=true;break;

    }else{

      /*double X=x[i][i]/eqt[num].a[i];

      for(int j=i;j<=m;j++){

	eqt[num].a[j]*=X;

	eqt[num].a[j]-=x[i][j];

	}*/

      double X=eqt[num].a[i]/x[i][i];

      for(int j=i;j<=m;j++){

	eqt[num].a[j]-=(x[i][j]*X);

      }

    }

  }

  return kk;

}

int main(){

  scanf("%d%d",&n,&m);

  for(int i=1;i<=n;i++){

    for(int j=1;j<=m;j++){

      scanf("%Lf",&eqt[i].a[j]);

    }

  }

  for(int i=1;i<=n;i++)scanf("%d",&eqt[i].val);

  sort(eqt+1,eqt+n+1,cmp);

  for(int i=1;i<=n;i++){

    if(par(i))ans+=eqt[i].val,sum++;

  }

  printf("%d %d\n",sum,ans);

  return 0;

}