【题解】LOJ6060 Set(线性基)

orz gql

设所有数的异或和为\(S\)，答案是在\(\max (x_1+S\and x_1)\)的前提下\(\min x_1\)输出\(x_1\)

转换一下就是\(\max (x_2+S\and x_2),s.t. \max x_2\)

考虑先贪心地求出外层\(\max\)

按位贪心，设\(u_i\)为\(S\)第\(i\)位上的\(bit\) ，\(u_i\)是个\(0/1\)变量

\(u_i=1\)时，对于\(x_2\)这一位我们没有任何要求，因为无论\(x_2\)该位上的取值，外层\(\max\)不变。
\(u_i=0\)时，对于\(x_2\)这一位我们要求能有\(bit\)就有\(bit\) ，这样可以对答案有\(2\times 2^i\)贡献。

由于满足要求的\(x_2\)有很多，我们现在要找到最大的那种，就直接线性基套进去就好了。具体实现代码带注释，文字太难说明了！

相当于复读gql的代码了

//@winlere

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

using namespace std;  typedef long long ll;

inline ll qr(){

      register ll ret=0,f=0;

      register char c=getchar();

      while(c<48||c>57)f|=c==45,c=getchar();

      while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();

      return f?-ret:ret;

}

const int maxn=1e5+5;

ll data[maxn];

ll base[66];

ll num[66];

ll n,S;

inline void insert(ll x){

      for(register int t=63;t;--t)

	    if(!(S&num[t])&&(x&num[t])){

		  if(!base[t]) return void(base[t]=x);

      		  x^=base[t];

	    }

      //假如当前元素可以按照条件一的条件插入，就return了，运行下面的代码是条件二

      for(register int t=63;t;--t)

	    if((S&num[t])&&(x&num[t])){

		  if(!base[t]) return void(base[t]=x);

		  x^=base[t];

	    }

}

inline ll top(){

      ll ret=0;

      //构造满足条件一二

      for(register int t=63;t;--t)

	    if(!(S&num[t])&&!(ret&num[t])) ret^=base[t];

      //构造x最大

      for(register int t=63;t;--t)

	    if( (S&num[t])&&!(ret&num[t])) ret^=base[t];

      return ret;

}

int main(){

      num[1]=1;

      for(register int t=2;t<=63;++t) num[t]=num[t-1]<<1;

      n=qr();

      for(register int t=1;t<=n;++t) data[t]=qr(),S^=data[t];

      for(register int t=1;t<=n;++t) insert(data[t]);

      cout<<(top()^S)<<endl;

      return 0;

}

巴特西

【题解】LOJ6060 Set(线性基)

【题解】LOJ6060 Set(线性基)

最新文章

热门文章