LOJ 6060「2017 山东一轮集训 Day1 / SDWC2018 Day1」Set（线性基，贪心）

LOJ 6060「2017 山东一轮集训 Day1 / SDWC2018 Day1」Set

---

---

$ solution: $

这一题的重点在于优先级问题，我们应该先保证总和最大，然后再保证某一个最小。于是我们分两部分贪心：（注意 $ tot $ 表示左右元素的异或和）

1. 首先我们要让总和最大的话，我们只需要讨论 $ tot $ 的某一位为0的情况（如果为1，那么不管怎么分配两边的数都只能并且一定有一个数，使它这一位上含有1）。对于 $ tot $ 的某一位为0的情况，我们肯定贪心的让两边都在这一位上含有一！这个我们只需要让其中一个有一，另一个就必定有一。于是我们贪心的让 $ x2 $ 在这一位上尽量大
2. 然后，我们要让左边最小，就只要再讨论 $ tot $ 的某一位为1的情况，我们肯定将这个1尽量分给 \(x2\) ，于是又是让 $ x2 $ 在这一位上尽量大！

这两个贪心是有优先级的，必须第一个贪完，第二个再贪！然后构造 $ x2 $ 最大，线性基最擅长，为了满足优先级我们先在 $ tot $ 的某一位为0的位上跑线性基，再在 $ tot $ 的某一位为1的位上跑线性基！

---

---

$ code: $

#include<iostream>

#include<cstdio>

#include<iomanip>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<cmath>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define db double

#define rg register int

using namespace std;

int n;

ll tot;

ll a[100005];

ll f[100005];

ll p[100005];

inline ll qr(){

	register char ch; register bool sign=0; ll res=0;

	while(!isdigit(ch=getchar()))if(ch=='-')sign=1;

	while(isdigit(ch))res=res*10+(ch^48),ch=getchar();

	if(sign)return -res; else return res;

}

inline void add(ll x){

	for(rg i=60;i>=0;--i){ //第一优先级

		if(!(tot&f[i])){ //先处理tot这一位为0的情况

			if(x&f[i]){

				if(p[i]) x^=p[i];

				else{p[i]=x; return ;}

			}

		}

	}

	for(rg i=60;i>=0;--i){ //第二优先级

		if(tot&f[i]){ //再处理tot这一位为1的情况

			if(x&f[i]){

				if(p[i]) x^=p[i];

				else{p[i]=x; return ;}

			}

		}

	}

}

inline ll ask(){

	ll res=0;

	for(rg i=60;i>=0;i--) //同理先保证全局最大

		if(!(tot&f[i])&&!(res&f[i])) res^=p[i];

	for(rg i=60;i>=0;i--) //然后保证单个最小（就是另一个最大）

		if(tot&f[i]&&!(res&f[i])) res^=p[i];

	return res;

}

int main(){

	//freopen(".in","r",stdin);

	//freopen(".out","w",stdout);

	n=qr(); f[0]=1;

	for(rg i=1;i<=60;++i) f[i]=f[i-1]<<1; //预处理

	for(rg i=1;i<=n;++i) a[i]=qr(),tot^=a[i]; //读入，统计tot

	for(rg i=1;i<=n;++i) add(a[i]); //逐个加入

	printf("%lld\n",tot^ask());

	return 0;

}