BZOJ 4269 再见 Xor

发布于 2017-06-23  118 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4269

题意:给定 N 个数,你可以在这些数中任意选一些数出来,每个数可以选任意多次,试求出你能选出的数的异或和的最大值和严格次大值。


显然我们可以知道 每个数可以选任意多次 这个条件是完全没用的... 因为偶数次异或自身为 0,奇数次为自身...

那么维护异或和什么的... 当然上线性基辣。对于这 N 个数构造完线性基后可以贪心的构造最大值,即从最高位开始若能使得答案更大就异或下去... 正确性?不会拟阵的蒟蒻是这么 YY 的:对于某一位如果能选,即使后面的位都选不上也肯定更优... 因为后面位无论怎么异或也没法进位了...

那么构造次大值也是很容易的了,从小到大贪心每一位,若能去掉就去掉输出答案即可,证(Y)明(Y)是类似的

结果调了半个多小时... 原来位运算优先级比大于小于都高啊!!!!

 


一个非常弱的准退役OIER