LP3265 [JLOI2015]装备购买 [线性基/贪心]

Author Avatar
ajcxsu 2018年09月13日
  • 73 次阅读

顺便也把线性基总结一下吧ww

Problem

https://www.luogu.org/problemnew/show/P3265

Solution

考虑一组 $k$ 维向量。

我们可以对向量定义一个乘上标量的操作。
我们再定义一个向量与向量相加的操作。
由这两种操作,对于某组向量里,有一些向量可以用其它的向量得到,那么这组向量就是多余的。

现在我们有这组向量,我们需要找到最精简的向量组,通过这两种操作能够得到这组向量里的所有向量。
那么这个向量组就叫基。

我们考虑我们需要的基是个什么东西。

我们需要的基是一个这样的 $k*k$ 的矩阵。

性质:对于第 $i$ 行矩阵,$a_{i,i}=1$,而对于所有的$a_{i, j}=0,\ j< i$。每一行代表了基里的一组向量。
那么我们如果对这个矩阵进行一下高斯消元,一定可以化成对角线为1的形式,即能表示所有的向量。

所以基里的向量组最多是 $k$ 组,且基里的向量一定不能互相表示(即线性无关)。

我们考虑怎么得到这个基。 维数从小到大往基里插入这个向量。若这个向量的第$i$维不为0,而基里的第$i$行的第$i$维不为0。那么我们可以用基里的这个向量来消去插入的向量的该维,并向下检查。若为0,则往基里插入这组向量。这组向量保证了是通过之前所给的向量组运算而来的,并且符合基的要求,因此可以成为基里的一组向量。

如果插到最后都找不到,就说明这组向量能被现有基里的向量所表示。

基里的所有向量都由原本的向量组运算而来,并且通过运算去除了冗余的向量,因此通过基里的向量互相运算,一定能够展开成原来向量组(生成基的逆运算)。

无论是对于异或线性基(一个数是32/64维的向量组),还是这样的实数线性基,原理都是一样的。

建议结合异或线性基来进行更好的理解。


对于本题,维护一个实数线性基。
基里含有的线性基的个数是确定的。因为经过高斯消元整理过后的基一定是唯一的。
因此影响的实际上是插入线性基的顺序。

一个贪心的思想,花费小的先插入线性基,肯定没错就是了emm

UPD

很有意思的是这个贪心的问题与kruskal非常类似,于是我在想kruskal的正确性。

我们假设现在我们选择序列中的四个元素,这四个元素的权值从小到大排列。

若我们按照贪心策略选择,有$A< B< C< D$,选择$A,D$。则存在选择$A$则不能选择$B,C$,否则不会选到$D$。

若我们需要选择$B$,则存在不选择$A$能选择$B$。

则这要求我们一定选择$C$,才可能有$B+C< A+D$。

我们考虑有连通块$X,Y$,则有边$X-A-Y$。

选择$A$不能选择$B$,不选择$A$能选择$B$,显然有边$X-B-Y$。

选择$A$不能选择$C$,显然存在$C$处于连通块$X,Y$中或$X-C-Y$或其它情况。

无论哪种情况,都有选择$B$不能选择$C$。

这个问题跟其非常相似。

因为选择$A$不能选择$B,C$。则$B$和$C$都能被基$S+A$所表示。

更加阐述一下,令$B=S+k_1A$,则存在$C=S'+k_2B=S'+k_2(S+k_1A)=S'+k_2S+k_2k_1A=S''+k_2k_1A$。

所以选择$B$不能选择$C$。

因此这个贪心是正确的。

希望我没证假

Code

// Code by ajcxsu
// Problem: kejin

#include<bits/stdc++.h>
#define EPS (1e-12)
using namespace std;

typedef long double ld;
const int N=510;
int n, m;
struct Basis {
    ld a[N][N];
    char vis[N];
    bool ins(ld b[]) {
        for(int i=1;i<=m;i++)
            if(fabs(b[i])>EPS){
                if(!vis[i]) { for(int j=i;j<=m;j++) a[i][j]=b[j]/b[i]; vis[i]=1; return true; }
                else for(int j=i+1;j<=m;j++) b[j]-=a[i][j]*b[i];
                b[i]=0;
            }
        return false;
    }
} bas;

struct W { int idx, c; } w[N];
bool cmp(const W &a, const W &b) { return a.c<b.c; }
ld b[N][N];
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin>>n>>m;
    int cnt=0, cost=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) cin>>b[i][j];
    for(int i=1;i<=n;i++) cin>>w[i].c, w[i].idx=i;
    sort(w+1, w+1+n, cmp);
    for(int i=1;i<=n;i++)
        if(bas.ins(b[w[i].idx]))
            cnt++, cost+=w[i].c;
    cout<<cnt<<' '<<cost<<endl;
    return 0;
}

本文链接:https://acxblog.site/archives/sol-luogu-3265.html
文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。