bzoj 4004: [JLOI2015]装备购买

  • 内容
  • 评论
  • 相关

【题目描述】
脸哥最近在玩一款神奇的游戏,这个游戏里有 n 件装备,每件装备有 m 个属性,用向量zi(aj ,.....,am) 表示 (1≤i≤n; 1≤j≤m),每个装备需要花费 ci,现在脸哥想买一些装备,但是脸哥很穷,所以总是盘算着怎样才能花尽量少的钱买尽量多的装备。对于脸哥来说,如果一件装备的属性能用购买的其他装备组合出(也就是说脸哥可以利用手上的这些装备组合出这件装备的效果),那么这件装备就没有买的必要了。严格的定义是,如果脸哥买了 zi1,.....zip这 p 件装备,那么对于任意待决定的 zh,不存在 b1,....,bp 使得 b1zi1 + ... + bpzip = zh(b 是实数),那么脸哥就会买 zh,否则 zh 对脸哥就是无用的了,自然不必购买。举个例子,z1 =(1; 2; 3);z2 =(3; 4; 5);zh =(2; 3; 4),b1 =1/2,b2 =1/2,就有 b1z1 + b2z2 = zh,那么如果脸哥买了 z1 和 z2 就不会再买 zh 了。脸哥想要在买下最多数量的装备的情况下花最少的钱,你能帮他算一下吗?
【题目解法】
比较裸的线性基 我们考虑使用高斯消元维护线性基 我们用b[i]表示第i维上的基向量 每次我们从最高位开始消元 如果当前位为0,那么直接跳过即可 否则,我们查看当前位上的基向量是否存在,如果没有,那么把当前的向量当作基向量 否则,我们用当前这个基向量来消当前的向量 消元后,如果该向量被消成0向量,那么就说明它可以被其它向量的线性组合取代。


#include 
#include 
#include 
#include 
using namespace std;
const int N=505;
const long long maxmod=1e9+7;
struct node
{
    long long a[N],v;
    bool operator < (const node &a) const
    {
        return v<a.v;
    }
} a[N];
int n,m,b[N],cnt; long long ans;
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
long long calc(long long x,long long y)
{
    long long nowans=1;
    while (y)
    {
        if (y%2==1) nowans=(nowans*x)%maxmod;
        x=(x*x)%maxmod; y=y/2;
    }
    return nowans;
}
void init()
{
    n=getint(); m=getint();
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) a[i].a[j]=getint();
    for (int i=1; i<=n; i++) a[i].v=getint(); sort(a+1,a+n+1);
}
bool add(int x)
{
    for (int i=1; i<=m; i++)
    {
        if (a[x].a[i]==0) continue;
        if (b[i]==0) {b[i]=x; return true;}
        long long t=(maxmod-a[x].a[i]*calc(a[b[i]].a[i],maxmod-2)%maxmod)%maxmod;
        for (int j=1; j<=m; j++) a[x].a[j]=(a[x].a[j]+a[b[i]].a[j]*t%maxmod)%maxmod;
    }
    for (int i=1; i<=m; i++) if (a[x].a[i]!=0) return true;
    return false;
}
void solve()
{
    for (int i=1; i<=n; i++) if (add(i)) ans+=a[i].v,cnt++;
    printf("%d %lldn",cnt,ans);
}
int main()
{
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    init();
    solve();
    return 0;
}

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据