icontofig | 发布于 2019-10-05 22:54:58 | 阅读量 338 | 线性基
发布于 2019-10-05 22:54:58 | 线性基
牛客欢乐赛4 2017湘潭市赛 C.Intersection 线性基 + 秩(线性代数题目)
题目大意给两个可重集合A,B,求问有多少个数x同时属于A的异或集和B的异或集。 此处的异或集指,从原集合中人与选出若干个数异或出的所有可能结果构成的集合。 题解如果要我们去枚举每一个数选或者不选,那么一个集合的异或集最多会有250个种元素。这样枚举每种情况的代价太大了,我们如何能够构造一种能够表示异或集内所有可能的值呢? 这里很自然的想到可以对原集合构造异或线性基,线性基的插入就可以判断当前这个数能否被当前构造出的线性基表示。 如果一个数x属于当前集合的异或集,那么x一定能够用线性基向量中的所有位和系数0/1(代表选不选)的组合表示出来。 通过以下韦恩图,我们可以更轻松的理解容斥原理|A∩B|
继续阅读
icontofig | 发布于 2019-07-27 20:09:15 | 阅读量 317 | 线性基
发布于 2019-07-27 20:09:15 | 线性基
2019 Multi-University Training Contest 1 1002 Operation 线性基
题目大意给出一个序列,有两种操作你需要完成: 0操作:询问l-----r区间内所有数中部分数通过异或运算所组成的所有数中的最大值。 1操作:在序列尾部插入值x。 注意题目强制在线。 题解此题是个强制在线的题目,不能使用离线算法(如莫队、CDQ分治)完成。 从0操作我们可以看出来此题很明显是一个线性基的题目(线性基主要用来解决序列中取出若干数使得这些数的异或值最大的问题,当然线性基也可以放入图论问题中) 如果没学过线性基的建议先自学线性基,本篇只是线性基的应用。可能之后我会写线性基的博客吧。 线性基是可以使用一些数据结构维护的,很多人比赛的时候看到这道题要进行区间操作就直接上线段树平衡树来维护线
继续阅读