[算法] 线性基

其实是为了写题去看的线性基。

一个炒鸡冷门的算法,只能用于求某类特殊的题目。noip自然不考。

下面直接以考试题为例题

题目连接

可以很自然看到题目中的描述,”求某个点子树中最大的异或值“。

1.线性基是用来干嘛的,是个啥?

既然我们要以该题为样板例题,那么线性基就啃腚和异或有关。事实上,线性基就是用来求”一个序列中可求出的最大异或值“。它的效率很高,可以在一个常数级别的复杂度就求出来(预处理需要高一些的复杂度)。

线性基可以看作是一个序列,序列中的每一个数相异或都可以得到原来的序列中的每一个数。

是不是一听起来就感到很迷茫?这个序列怎么求?什么叫“可以看作”?

2.线性基怎么构造?

上面提到,可以在常数时间内求出,所以你可以想到,这个线性基如果以数组构成,它的下标i表示的应该是2的i次方。这样遍历一遍数组才可以求出来啊!

就是这样!喵!

线性基中的数异或起来,可以求出原数组任何一数,下标意为2的某次方,怎样的序列异或起来才可以呢?

$$ a[0]=2^0; $$
$$ a[1]=2^1; $$
$$ a[2]=2^2; $$
$$ a[3]=2^3; $$

.......

看看是不是这样?这就是最基本的线性基。

if (原数组第i位上有1) a[i]=2的i次方;

但我们还是希望这个数组存储的信息尽可能少。如果按上面的来,原数组的意义就只在于看二进制状态下哪一位为1,哪一位为0。而我们就可以按照原数组的数缩减信息。

我们在代码中去体会

void insert(int x){
    for (int i=20;i>=0;i--){
        if (x&(1<<i)) {//假设插入数中当前位为1,进入判定
            if (k[i]) x=x^k[i];//假设线性基数组中已经可以组成这个数的这一位,就溜掉,同时继续看下一位
            else {
                k[i]=x;//假设线性基数组还无法组成它的当前位,就把它整个放进去,这样既保证不会保存过多信息,又让线性基中的数可以依旧有原有的功能。
                return ;
            }
        }
    }
}

然后构建好了线性基,我们来康康怎么求最大值。

3.线性基求最大值

int maxji(){
    int ans=0;
    for (int i=20;i>=0;i--) {
        if ((ans^k[i]) > ans) ans=ans^k[i];
    }
    return ans;
}

这个贪心似的东东是个什么鬼?
就是贪心。

如果答案异或线性基中的某个数大于本身,那就异或好了。

等等,难道这不会有后效性什么的吗?别忘了线性基存的到底是什么,想一想,自己意会一下吧。

4.各类资料

由于博主本人能力有限,很多地方有水分,而且解释得不清楚,下面放上几篇大佬的blog
百度都推荐的
文章列出了线性基的各种性质

撒花结束

Last modification:August 24th, 2019 at 03:23 pm

3 comments

  1. marTixx

    tql!!!!

  2. fpjo

    %%%

  3. JRLC

Leave a Comment