【LOJ6060】「2017 山东一轮集训 Day1 / SDWC2018 Day1」Set（线性基）

点此看题面

大致题意： 让你把\(n\)个数分成两部分，使得在两部分异或和之和最大的前提下，两个异或和中较小的那个尽量小。输出最优的较小异或和。

线性基

关于线性基，可以看一下这篇博客：线性基入门。

解题思路

首先，做这题要有一定的位运算常识。

我们求出所有数的异或和，记作\(s\)。

则对于\(s\)二进制下每一位，我们进行分类讨论：

如果这一位是\(1\)。则划分出的两个集合的异或和这一位必然分别是\(0\)或\(1\)，即：两个集合中这一位之和是固定不变的。
如果这一位是\(0\)。则划分出的两个集合的异或和这一位必然是全\(0\)或全\(1\)。

既然我们要让总和最大，由于\(1\)位上的总和不变，则显然应该先去考虑\(0\)位，使\(0\)位尽量为两个\(1\)。

然后，借助线性基的思想，我们修改一下线性基的操作方式，就可以轻松求解此题啦。

对于插入

对于插入，由于我们刚刚已经总结出使\(0\)位尽量为两个\(1\)，因此，我们在插入时要优先考虑\(0\)位。

具体实现时，就是先对\(0\)位从高到低扫一遍判断是否可以插入，然后对\(1\)位从高到低扫一遍判断是否可以插入。

先扫\(0\)我们就相当于把每个最后插入到\(1\)位的数的\(0\)位全变成了\(0\)，使得操作\(1\)位不会影响到\(0\)位，为后面的询问奠定了基础。

对于询问

我们先从高到低扫一遍\(0\)位，如果当前\(ans\)这一位上是\(0\)，则我们尽量使其为\(1\)。

由于这一位上的数要么二进制下这一位是\(1\)（可以把\(ans\)这一位上变成\(1\)），要么这个数就是\(0\)（异或\(0\)没有任何影响），因此直接将\(ans\)异或上当前这一位的数即可。

然后从高到低扫一遍\(1\)位，如果\(ans\)这一位是\(1\)，由于我们要让这个数尽量小，就异或上当前这一位的数即可（理由同上）。

代码

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define RL Reg LL

#define Con const

#define CI Con int&

#define CL Con LL&

#define I inline

#define W while

#define N 100000

#define LL long long

using namespace std;

int n;LL s,a[N+5];

class FastIO

{

	private:

		#define FS 10000

		#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)

		#define tn (x<<3)+(x<<1)

		#define D isdigit(c=tc())

		char c,*A,*B,FI[FS];

	public:

		I FastIO() {A=B=FI;}

		Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}

		Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}

}F;

class LinearBasis//线性基

{

	private:

		#define P 60

		LL v[P+5];

	public:

		#define ins() {if(!v[i]) return (void)(v[i]=x);x^=v[i];}

		I void Insert(RL x)

		{

			RI i;for(i=P;~i;--i) if(!(s>>i&1)&&x>>i&1) ins();//优先考虑0位

			for(i=P;~i;--i) if(s>>i&1&&x>>i&1) ins();

		}

		I LL Query()

		{

			RI i;RL ans=0;for(i=P;~i;--i) !(s>>i&1)&&!(ans>>i&1)&&(ans^=v[i]);//尽量使0位变成1

			for(i=P;~i;--i) s>>i&1&&ans>>i&1&&(ans^=v[i]);return ans;//尽量使1位更小

		}

}B;

int main()

{

	RI i;for(F.read(n),i=1;i<=n;++i) F.read(a[i]),s^=a[i];//统计所有数异或和

	for(i=1;i<=n;++i) B.Insert(a[i]);return printf("%lld",B.Query()),0;//求解并输出答案

}

巴特西

【LOJ6060】「2017 山东一轮集训 Day1 / SDWC2018 Day1」Set（线性基）

线性基

解题思路

对于插入

对于询问

代码

最新文章

热门文章