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; }
发表评论