【SDWC2018】Set

Source and Judge

SDWC2018
loj6060

Analysis

请先思考后再展开

先考虑最大化a+sum^a,因为是个和,会有进位,不妨不考虑进位,允许有2
考虑每个二进制位置,如果是1,那么就是一个0和一个1,对和没有影响
如果是0,那么如果可以的话(很多人漏了)就是1和1
那么我们只要按照先0再1的顺序考虑,就能保证和最大
那怎么最小化a呢?因为是个子集的异或和,考虑线性基,然后考虑最大化sum^a会更方便
那这个东西的话,就是在刚才的顺序下,跑常规的线性基即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=110000;
ll sum=0,bin[70];int a[MAX_N],tot[70];
bool cmp(int x,int y)
{
int a=(sum&bin[x])==0 and tot[x]>0;
int b=(sum&bin[y])==0 and tot[y]>0;
return a>b or (a==b and x>y);
}
struct Basic
{
ll b[70];Basic(){memset(b,0,sizeof b);}
void insert(ll now)
{
for(int i=0;i<=60;i++) if(now&bin[a[i]])
{
if(b[a[i]]) now^=b[a[i]];
else {b[a[i]]=now;break;}
}
}
ll ask()
{
ll ans=0;
for(int i=0;i<=60;i++) if((ans&bin[a[i]])==0) ans^=b[a[i]];
return ans;
}
}bs;
ll num[MAX_N];
int main()
{
bin[0]=1;for(int i=1;i<=60;i++) bin[i]=bin[i-1]<<1;
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&num[i]);sum^=num[i];
for(int j=0;j<=60;j++) tot[j]+=(num[i]&bin[j])>0;
}
for(int i=0;i<=60;i++) a[i]=i;
sort(a,a+60+1,cmp);
for(int i=1;i<=n;i++) bs.insert(num[i]);
printf("%lld",sum^bs.ask());
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/6bea.html
转载请注明出处,谢谢!