青竹qingzhu

线性基

AC自动机(3) KMP(3) tarjan(2) 主席树(2) 二分(1) 优先队列(1) 倍增(2) 后缀数组(1) 后缀自动机(1) 图论(1) 技巧(3) 最短路(10) 树状数组(1) 网络流(10) 题解(7)

/ 注册

全部文章 / 线性基（共3篇）

线性基基础问题

大佬的博客假设有n个数，这n个数能组成的异或和的集合为V，线性基就是能表示这个异或和集合V的最小集合。线性基的作用:求解异或和第k小、异或和最大值、某个数是否存在于异或和集合里等问题。洛谷P3812 求异或和的最大值 #include <bits/stdc++.h> using ...

2020-07-13

0 511

bzoj 2115 线性基

题目链接题意给一个n个顶点m条边的无向带权图，求从1到n的一条路径上的最大异或和。思路从1到n的一条路径上，没有要求点各异、边各异，所以根据贪心的思想，如果有环的话，从1到n上的路径上的一个顶点，走过这个环再回到这个顶点，可能使异或值变大，所以遍历这些环，如果能使异或值增加的就走，最后可以得...

2020-07-13

0 417

bzoj 2844-线性基

题目链接题意给定n个数以及一个数q，将这n个数的所有子集（可以为空）的异或值从小到大排序得到序列B（这样B内就有2^n 个元素），求出q在序列B中第一次出现的下标，答案对10086取模（默认q一定存在）。思路首先有一个定理：B数列中每个数字出现次数都是2^(n-cnt)，cnt为线性基的大...

2020-07-13

0 470