首页 > 编程语言 >【算法笔记】线性基

【算法笔记】线性基

时间：2024-09-14 20:25:30浏览次数：1  
标签：return auto ui64 笔记 算法 kth ans 线性 sorted

线性基

定义：给定数集\(s\)，以异或运算张成的数集与\(S\)相同的极大线性无关集，称为原数集的一个线性基。

性质 ：

  1. 原数集的任意一个数都能有线性基内部的一些数异或得到。
  2. 线性基内部任意数异或不为 0
  3. 线性基内数唯一，且保证性质一的情况下，数的个数最少。
  4. 线性基内每个数的最高有效位各不相同。

如何判断原数集能否异或出\(0\)，在插入的过程中如果插入失败就可以异或出\(0\)。

struct Basis {
    vector<ui64> B;
    bool zero, sorted;

    Basis() {
        B = vector<ui64>();
        zero = false, sorted = true;
    }

    void sort() {
        if (sorted) return;
        sorted = true;
        ranges::sort(B);
        return;
    }

    void insert(ui64 x) {
        for (auto b: B)
            x = min(x, b ^ x);
        if (x == 0) {
            zero = true;
            return;
        }
        for (auto &b: B)
            b = min(b, b ^ x);
        B.push_back(x), sorted = false;
        return;
    }

    int query(int kth = 1) { // query k-th smallest element
        sort();
        if (zero) kth--;
        ui64 ans = 0;
        for (auto b: B) {
            if (kth & 1) ans ^= b;
            kth >>= 1;
        }
        if (kth == 0) return ans;
        return -1;
    }

    ui64 max() {
        ui64 ans = 0;
        for (auto b: B)
            ans ^= b;
        return ans;
    }

    bool check(ui64 x) {
        for (auto b: B)
            x = min(x, b ^ x);
        return x == 0;
    }

    void merge(const Basis &oth) {
        for (auto x: oth.B)
            insert(x);
        return;
    }
};

例题

P3812 【模板】线性基

验证模板，考虑到线性基内数的最高有效位各不相同，所以直接把所有的数异或就是答案

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

using ui64 = uint64_t;

struct Basis {
    vector<ui64> B;
    bool zero, sorted;

    Basis() {
        B = vector<ui64>();
        zero = false, sorted = true;
    }

    void sort() {
        if (sorted) return;
        sorted = true;
        ranges::sort(B);
        return;
    }

    void insert(ui64 x) {
        for (auto b: B)
            x = min(x, b ^ x);
        if (x == 0) {
            zero = true;
            return;
        }
        for (auto &b: B)
            b = min(b, b ^ x);
        B.push_back(x), sorted = false;
        return;
    }

    int query(int kth = 1) { // query k-th smallest element
        sort();
        if (zero) kth--;
        ui64 ans = 0;
        for (auto b: B) {
            if (kth & 1) ans ^= b;
            kth >>= 1;
        }
        if (kth == 0) return ans;
        return -1;
    }

    ui64 max() {
        ui64 ans = 0;
        for (auto b: B)
            ans ^= b;
        return ans;
    }

    bool check(ui64 x) {
        for (auto b: B)
            x = min(x, b ^ x);
        return x == 0;
    }

    void merge(const Basis &oth) {
        for (auto x: oth.B)
            insert(x);
        return;
    }
};


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    Basis b;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        ui64 x;
        cin >> x;
        b.insert(x);
    }
    cout << b.max();
    return 0;
}

P3857 [TJOI2008] 彩灯

线性基的元素有\(x\)个，每一个都有选或不选两种，方案数\(2^x\)

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

using ui64 = uint64_t;

struct Basis {
    vector<ui64> B;
    bool zero, sorted;

    Basis() {
        B = vector<ui64>();
        zero = false, sorted = true;
    }

    void sort() {
        if (sorted) return;
        sorted = true;
        ranges::sort(B);
        return;
    }

    void insert(ui64 x) {
        for (auto b: B)
            x = min(x, b ^ x);
        if (x == 0) {
            zero = true;
            return;
        }
        for (auto &b: B)
            b = min(b, b ^ x);
        B.push_back(x), sorted = false;
        return;
    }

    int query(int kth = 1) { // query k-th smallest element
        sort();
        if (zero) kth--;
        ui64 ans = 0;
        for (auto b: B) {
            if (kth & 1) ans ^= b;
            kth >>= 1;
        }
        if (kth == 0) return ans;
        return -1;
    }

    ui64 max() {
        ui64 ans = 0;
        for (auto b: B)
            ans ^= b;
        return ans;
    }

    bool check(ui64 x) {
        for (auto b: B)
            x = min(x, b ^ x);
        return x == 0;
    }

    void merge(const Basis &oth) {
        for (auto x: oth.B)
            insert(x);
        return;
    }
};


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    Basis b;
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        string s;
        cin >> s;
        i64 val = 0;
        for (auto c: s) {
            val <<= 1;
            val |= (c == 'O');
        }
        b.insert(val);
    }
    int t = b.B.size(), res = 1;
    for (int i = 0; i < t; i++)
        res = res * 2 % 2008;
    cout << res;
    return 0;
}

P4570 [BJWC2011] 元素

首先选出的集合内不能存在异或和为\(0\)的情况，这个可以用线性基来维护。

值最大可以贪心，优先插入魔力值大的。假设集合内存在\(a\oplus b \oplus c \oplus d = 0\)的情况，我们肯定扔掉最小值最优。

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

using ui64 = uint64_t;

struct Basis {
    vector<ui64> B;
    bool zero, sorted;

    Basis() {
        B = vector<ui64>();
        zero = false, sorted = true;
    }

    void sort() {
        if (sorted) return;
        sorted = true;
        ranges::sort(B);
        return;
    }

    void insert(ui64 x) {
        for (auto b: B)
            x = min(x, b ^ x);
        if (x == 0) {
            zero = true;
            return;
        }
        for (auto &b: B)
            b = min(b, b ^ x);
        B.push_back(x), sorted = false;
        return;
    }

    int query(int kth = 1) { // query k-th smallest element
        sort();
        if (zero) kth--;
        ui64 ans = 0;
        for (auto b: B) {
            if (kth & 1) ans ^= b;
            kth >>= 1;
        }
        if (kth == 0) return ans;
        return -1;
    }

    ui64 max() {
        ui64 ans = 0;
        for (auto b: B)
            ans ^= b;
        return ans;
    }

    bool check(ui64 x) {
        for (auto b: B)
            x = min(x, b ^ x);
        return x == 0;
    }

    void merge(const Basis &oth) {
        for (auto x: oth.B)
            insert(x);
        return;
    }
};

using vi = vector<i64>;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    vi number(n), magic(n), p(n);
    for (int i = 0; i < n; i++)
        cin >> number[i] >> magic[i], p[i] = i;
    ranges::sort(p, [&](const int x, const int y) {
        return magic[x] > magic[y];
    });
    Basis b;
    i64 res = 0;
    for (auto i: p) {
        if (b.check(number[i])) continue;
        b.insert(number[i]), res += magic[i];
    }
    cout << res;
    return 0;
}

P4301 [CQOI2013] 新Nim游戏

首先根据Nim游戏的性质，我们知道如果初始的异或和不为\(0\)，先手必胜。

假设在第一轮先手操作后异或和不为 0，后手是不可能通过拿操作是的异或为 0 的。对于先手来说，极端情况就是保留一个，此时异或和一定不为0。所以先手必胜。

先手选取的方式用线性基来维护，总数最小参考上一题的贪心处理就好了。

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

using ui64 = uint64_t;

struct Basis {
    vector<ui64> B;
    bool zero, sorted;

    Basis() {
        B = vector<ui64>();
        zero = false, sorted = true;
    }

    void sort() {
        if (sorted) return;
        sorted = true;
        ranges::sort(B);
        return;
    }

    void insert(ui64 x) {
        for (auto b: B)
            x = min(x, b ^ x);
        if (x == 0) {
            zero = true;
            return;
        }
        for (auto &b: B)
            b = min(b, b ^ x);
        B.push_back(x), sorted = false;
        return;
    }

    int query(int kth = 1) { // query k-th smallest element
        sort();
        if (zero) kth--;
        ui64 ans = 0;
        for (auto b: B) {
            if (kth & 1) ans ^= b;
            kth >>= 1;
        }
        if (kth == 0) return ans;
        return -1;
    }

    ui64 max() {
        ui64 ans = 0;
        for (auto b: B)
            ans ^= b;
        return ans;
    }

    bool check(ui64 x) {
        for (auto b: B)
            x = min(x, b ^ x);
        return x == 0;
    }

    void merge(const Basis &oth) {
        for (auto x: oth.B)
            insert(x);
        return;
    }
};

using vi = vector<i64>;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    vi a(n);
    for (auto &i: a) cin >> i;
    ranges::sort(a, greater<>());
    Basis b;
    i64 res = 0;
    for (auto &i: a) {
        if (b.check(i)) res += i;
        else b.insert(i);
    }
    cout << res;
    return 0;
}

标签：return,auto,ui64,笔记,算法,kth,ans,线性,sorted
From： https://www.cnblogs.com/PHarr/p/18414642

相关文章

  • 滑动窗口算法—最小覆盖子串
    题目         ”最小覆盖子串“问题，难度为Hard，题目如下：        给你两个字符串S和T，请你在S中找到包含T中全部字母的最短子串。如果S中没有这样一个子串，则算法返回空串，如果存在这样一个子串，则可以认为答案是唯一的。    比如输入S="ADB......
  • transformer（李宏毅笔记）
    transformerEncoder之前的Self-attention其实已经提到过transformer，而且transformer和后面的bert也有很大关系，transformer就是一个sequencetosequence的model这些都是输出不定长的例子，语音识别+机器翻译=语音翻译吗，有些语言可能没有文字，或者说某些方言训练这样的模型，你就......
  • 「数学::质数」埃氏筛|欧拉筛（埃拉托斯特尼筛法|线性筛法）/ LeetCode 204（C++）
    目录概述1.埃氏筛思路复杂度Code2.欧拉筛（线性筛）思路复杂度Code总结概述上一节我们介绍了对判断一个数是否为质数的方法：「数学::质数」试除法/LuoguP5736（C++）那如果我们期望输出一个范围内的所有质数，使用试除法的时间复杂度是n√n，怎么办呢？LeetCode204：给定整......
  • java计算机毕业设计协同过滤算法的就业推荐系统（开题+程序+论文）
    本系统（程序+源码）带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景在当今快速发展的数字经济时代，人才与企业的精准匹配成为推动产业升级与创新的关键。然而，面对海量的人才信息与多样化的岗位需求，传统的招聘方式往往效......
  • 前端必须掌握的五种排序算法，你会几种？
    文章目录前言1.冒泡排序（BubbleSort）2.选择排序（SelectionSort）3.插入排序（InsertionSort）4.快速排序（QuickSort）5.归并排序（MergeSort）前言在前端开发中，对数据进行排序是一项基本且常见的任务。掌握排序算法不仅可以帮助我们更有效地处理数据，还能提升代码的执行效......
  • 代码随想录算法 - 二叉树4
    题目1654.最大二叉树给定一个不重复的整数数组nums。最大二叉树可以用下面的算法从nums递归地构建:创建一个根节点，其值为nums中的最大值。递归地在最大值左边的子数组前缀上构建左子树。递归地在最大值右边的子数组后缀上构建右子树。返回nums构建的*......
  • 顶刊算法 | 鹈鹕算法POA-Transformer-LSTM多变量回归预测
    顶刊算法|鹈鹕算法POA-Transformer-LSTM多变量回归预测目录顶刊算法|鹈鹕算法POA-Transformer-LSTM多变量回归预测效果一览基本介绍程序设计参考资料效果一览基本介绍1.Matlab实现顶刊算法|鹈鹕算法POA-Transformer-LSTM多变量回归预测（程序可以作为JCR一区级论文代码支撑，目......
  • 路径规划 | 基于A*算法的往返式全覆盖路径规划的改进算法（Matlab）
    目录效果一览基本介绍程序设计参考文献效果一览基本介绍基于A*算法的往返式全覆盖路径规划的改进算法matlab实现代码往返式全覆盖路径规划，通过建立二维栅格地图，设置障碍物，以及起始点根据定义往返式路径规划的定义的优先级运动规则从起始点开始进行全图遍历，利用A星算法逃离死角......
  • 多输入多输出 | Matlab实现SO-BP蛇群算法优化BP神经网络多输入多输出预测
    多输入多输出|Matlab实现SO-BP蛇群算法优化BP神经网络多输入多输出预测目录多输入多输出|Matlab实现SO-BP蛇群算法优化BP神经网络多输入多输出预测预测效果基本介绍程序设计往期精彩参考资料预测效果基本介绍多输入多输出|Matlab实现SO-BP蛇群算法优化BP神经网络多输入多输......
  • 时序预测 | MATLAB实现BKA-XGBoost(黑翅鸢优化算法优化极限梯度提升树)时间序列预测
    时序预测|MATLAB实现BKA-XGBoost(黑翅鸢优化算法优化极限梯度提升树)时间序列预测目录时序预测|MATLAB实现BKA-XGBoost(黑翅鸢优化算法优化极限梯度提升树)时间序列预测预测效果基本介绍模型描述程序设计参考资料预测效果基本介绍Matlab实现BKA-XGBoost时间序列预测，黑翅鸢优......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99