题目

题目链接

做法

这道题目和元素很像，直接把线性基中异或的部分改成高斯消元的样子即可，然后我A了，QMQ。

时间复杂度：$O(n^3)$

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define  N  510
using  namespace  std;
struct  node
{
    double  a[N];
    double&  operator[](int  x)
    {
        return  a[x];
    }
}a[N],b[N];bool  v[N];
int  val[N],f[N]/*排序数组*/;
inline  bool  cmp(int  x,int  y){return  val[x]<val[y];}
int  ans1,ans2;
int  m,n;
void  GSXY(node  x,int  y)//高斯消元
{
    for(int  i=1;i<=n;i++)
    {
        if(x[i]>=1e-4  ||  x[i]<=-1e-4)
        {
            if(v[i])
            {
                double  fuck=x[i]/a[i][i];
                for(int  j=i;j<=n;j++)x[j]-=a[i][j]*fuck;
            }
            else
            {
                a[i]=x;ans2+=y;v[i]=1;
                ans1++;
                break;
            }
        } 
    }
}
int  main()
{
    scanf("%d%d",&m,&n);
    for(int  i=1;i<=m;i++)
    {
        for(int  j=1;j<=n;j++)scanf("%lf",&b[i][j]);
    }
    for(int  i=1;i<=m;i++){scanf("%d",&val[i]);f[i]=i;}
    sort(f+1,f+m+1,cmp);//按价值排序
    for(int  i=1;i<=m;i++)GSXY(b[f[i]],val[f[i]]);
    printf("%d %d\n",ans1,ans2);
    return  0;
}