线性基 – Tgotp-Blog

#6060. 「2017 山东一轮集训 Day1」Set

异或和一般都会想到01trie 或者线性基.

发现是在任意位置选取集合元素.

那么容易想到用线性基做.

考虑令s 等于所有数的异或和.

那么x1 ^ x2 = s

考虑怎么取得max(x1 + x2)且min(x1)

把s化为2进制.

对于s的某一位x,如果[......]

Read more

3105: [cqoi2013]新Nim游戏

nim游戏先手必胜的条件是亦或和 != 0 ,那么排序后,能加就加,搞定

c++代码如下:

 

4004: [JLOI2015]装备购买

卡精度啊这题。

写题半小时,卡精度两小时。

线性基裸题。

按权值排序后直接处理就好了。

再次强调注意卡精度。

c++代码如下:

 

 

2115: [Wc2011] Xor

考虑到直接走到某个位置再走回去,xor 值为零,所以考虑先走到n点,然后就是寻求从n点走任意路劲使得值最大,那么对于一个环,当我们走到上面的时候,会产生环的xor值,走两边值又为0,

因为最后是要重新走到n点,那么除环以外的路径一定不用考虑,接下来只用判断在能走到所有的环上,哪些走奇数次,哪些[......]

Read more

SGU275 To xor or not to xor

线性基入门题:
题目大意:选出一些数使得异或值最大。

c++代码如下: