icontofig | 发布于 2020-05-04 23:46:43 | 阅读量 232 | 线性基
发布于 2020-05-04 23:46:43 | 线性基
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算出来,然后我们来
继续阅读
icontofig | 发布于 2019-10-05 22:54:58 | 阅读量 423 | 线性基
发布于 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 | 阅读量 387 | 线性基
发布于 2019-07-27 20:09:15 | 线性基
2019 Multi-University Training Contest 1 1002 Operation 线性基
题目大意给出一个序列,有两种操作你需要完成: 0操作:询问l-----r区间内所有数中部分数通过异或运算所组成的所有数中的最大值。 1操作:在序列尾部插入值x。 注意题目强制在线。 题解此题是个强制在线的题目,不能使用离线算法(如莫队、CDQ分治)完成。 从0操作我们可以看出来此题很明显是一个线性基的题目(线性基主要用来解决序列中取出若干数使得这些数的异或值最大的问题,当然线性基也可以放入图论问题中) 如果没学过线性基的建议先自学线性基,本篇只是线性基的应用。可能之后我会写线性基的博客吧。 线性基是可以使用一些数据结构维护的,很多人比赛的时候看到这道题要进行区间操作就直接上线段树平衡树来维护线
继续阅读