Tag-线性基

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2020-08-18 20:00:36 |  0 Comments  |  线性基

ZOJ 4086 Little Sub and a Game 线性基博弈

题目大意

玩家Little Sub和lqybzx分别有N、M个数对(xi,yi)、(x'i,y'i),且双方都知道对方的数对中的数是什么,Little Sub先从自己的N个数对中的每个数对中选取1个数z,并且ans = ans xor z,之后lqybzx会对自己的M个数对做相同的操作。

Little Sub(A)希望最终结果更大,而lqybzx(B)希望最终结果更小,且双方均采取最优策略,问最终答案是多少。

题解

对于博弈的题目来说,我们其实不是好知道双方的脑回路是怎么想的。有时候我们能猜到有时候我们猜不到。

所以不妨我们先来假设两个人每个数对都选第一个数字,先把一个答案ans算出来,然后我们来根据每个人的数对再来进行调整。

由于是二进制的运算所以我们考虑对每个答案ans的每个二进制位上是否为1来讨论两个玩家的策略。

因为我们需要对二进制位进行讨论,所以我们需要讨论两个玩家的数对(x,y)中x xor y对答案的控制能力。所以我们需要对两个玩家的数对(x,y)进行x xor y的线性基的构造。

假设构造的两个x xor y的线性基分别为A、B。

如果在某个位bit上我们取了线性基X中在bit位上的元素,我们相当于在总答案的上面对某一组数对(x,y)的选择进行改变(ans xor(x xor y),本来ans中有x或y,选择这一次相当于换成另外一个)

我们从高位到低位逐一进行扫描,对于第i位,分为以下八种情况:

ans[i] = 0,A[i] = 0,B[i] = 0,双方都对这个位无法操作

ans[i] = 0,A[i] = 0,B[i] = 1,只有B对这个位可以操作,但由于B想要答案更小,所以他不会对这一位进行操作。

ans[i] = 0,A[i] = 1,B[i] = 0,只有A对这个位可以操作,由于A想要答案更大,所以他会选择对这一位进行操作,ans ^= A[i]。

ans[i] = 0,A[i] = 1,B[i] = 1,A与B都可对这个位操作,而且如果A对这个位操作的话,B一定也会对这个位操作,所以我们可以把A[i] xor B[i]加入到线性基A中,表示A和B同时选/不选。

ans[i] = 1,A[i] = 0,B[i] = 0,双方都对这个位无法操作

ans[i] = 1,A[i] = 0,B[i] = 1,只有B对这个位可以操作,由于B想要答案更小,所以他会选择对这一位进行

 2019-10-05 22:54:58 |  0 Comments  |  线性基

牛客欢乐赛4 2017湘潭市赛 C.Intersection 线性基 + 秩(线性代数题目)

题目大意

给两个可重集合A,B,求问有多少个数x同时属于A的异或集和B的异或集。

此处的异或集指,从原集合中人与选出若干个数异或出的所有可能结果构成的集合。

题解

如果要我们去枚举每一个数选或者不选,那么一个集合的异或集最多会有250个种元素。这样枚举每种情况的代价太大了,我们如何能够构造一种能够表示异或集内所有可能的值呢?

这里很自然的想到可以对原集合构造异或线性基,线性基的插入就可以判断当前这个数能否被当前构造出的线性基表示。

如果一个数x属于当前集合的异或集,那么x一定能够用线性基向量中的所有位和系数0/1(代表选不选)的组合表示出来。

通过以下韦恩图,我们可以更轻松的理解容斥原理|A∩B| = |A| + |B| - |A∪B|:

其中|A|表示A的秩,也即元素个数。

我们对A、B、A∪B分别构造线性基,并分别求出秩ra,rb,rab,由于同时属于A和B的异或集的元素x一定由A∩B的异或集的线性基向量的各项及0/1系数组合构成,所以最终答案实际上就是2|xor_set(A∩B)|,也即2ra+rb-rab

最终测试的是long long 就能过。

这里的秩当然也可以用高斯消元来解释(高斯消元实际上就对应着方程组矩阵的秩,有大学线性代数基础的同学可能比较清楚),不过高斯消元感觉比线性基更麻烦一些,所以我比赛的时候选择了线性基。

代码

#include <bits/stdc++.h>
int n;
typedef long long ll;
const int maxn = 55;
ll ans,a[maxn],b[maxn];
const int upper = 64;
ll xor_shift[upper];
bool add(ll x){
    bool flag = false;
    for(int i = upper-1;i >= 0;--i){
        if(x & (1ll<<i)){
            if(!xor_shift[i]){
                xor_shift[i] = x;
                flag = true;
                break;
            }
            else{
                x ^= xor_shift[i];
     
 2019-07-27 20:09:15 |  0 Comments  |  线性基

2019 Multi-University Training Contest 1 1002 Operation 线性基

题目大意

给出一个序列,有两种操作你需要完成:

0操作:询问l-----r区间内所有数中部分数通过异或运算所组成的所有数中的最大值。

1操作:在序列尾部插入值x。

注意题目强制在线。

题解

此题是个强制在线的题目,不能使用离线算法(如莫队、CDQ分治)完成。

从0操作我们可以看出来此题很明显是一个线性基的题目(线性基主要用来解决序列中取出若干数使得这些数的异或值最大的问题,当然线性基也可以放入图论问题中)

如果没学过线性基的建议先自学线性基,本篇只是线性基的应用。可能之后我会写线性基的博客吧。

线性基是可以使用一些数据结构维护的,很多人比赛的时候看到这道题要进行区间操作就直接上线段树平衡树来维护线性基了。但是由于这道题的数据范围过大,数据结构会有logn的一个复杂度导致超时。

这道题的正确的思路是贪心地维护以某个位置为结尾的所有数的线性基。

对于每一个线性基,我们尽量把出现时间较为靠后的数的二进制向量放在高位上,然后原来的线性基中各位置上的二进制向量不断下放。如此地贪心地维护以每个位置为结尾的线性基。

在求最大值的时候,首先找到区间右端点对应结尾的线性基,然后从高位向低位开始扫,如果当前扫到的线性基的位置为第j位,且第j位上的二进制向量出现的比查询区间左端点l要晚,那我们就要考虑这个二进制向量对答案的影响,如果异或此二进制向量能够使得答案变大,那我们就异或上这个二进制向量。否则就不需要考虑。

这样我们得出的线性基就有一个性质:对于每个线性基的每一位,与它异或过的线性基更高位置上的数字肯定都出现在它右侧 (否 则它就会被插入在那个位置了),因此做法的正确性显然。

最终复杂度位O(31*n)。(注意此题的强制在线的操作)

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag
Title - Artist
0:00