[MtOI2019]永夜的报应 解题报告
disangan233
2019-08-23 21:52:44
## 题意
给你 $n$ 个非负整数 $a_1,a_2\cdots a_n$，让你将这些数分成若干组。定义一组数的权值为该组内所有数的**异或和**，求分出的所有组数的权值之和的最小值。
## Solutions
### Sol 1
直接暴搜，时间复杂度 $O\left(3^nn\right)$，期望得分：$80~pts$。
### Sol 2
假设所有数的异或和在 $2^t$ 位为 $0$，那么分到一组对答案没有贡献。
假设所有数的异或和在 $2^t$ 位为 $1$，那么显然无论如何分组，$2^t$ 位对答案的总贡献都不会为 $0$（因为当前位有奇数个 $1$），即 $1$ 是答案下界。
因此，将所有数分为一组即为最优答案。
输出所有数的异或和即可，时间复杂度 $O(n)$，期望得分：$100~pts$
## Code
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register int
#define db double
#define in inline
namespace fast_io
{
char buf[1<<12],*p1=buf,*p2=buf,sr[1<<23],z[23],nc;int C=-1,Z=0,Bi=0;
in char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
in ll read()
{
ll x=0,y=1;while(nc=gc(),(nc<48||nc>57)&&nc!=-1)if(nc==45)y=-1;Bi=1;
x=nc-48;while(nc=gc(),47<nc&&nc<58)x=(x<<3)+(x<<1)+(nc^48),Bi++;return x*y;
}
in db gf() {re a=read(),b=(nc!='.')?0:read();return (b?a+(db)b/pow(10,Bi):a);}
in int gs(char *s) {char c,*t=s;while(c=gc(),c<32);*s++=c;while(c=gc(),c>32)*s++=c;return s-t;}
in void ot() {fwrite(sr,1,C+1,stdout);C=-1;}
in void flush() {if(C>1<<22) ot();}
template <typename T>
in void write(T x,char t)
{
re y=0;if(x<0)y=1,x=-x;while(z[++Z]=x%10+48,x/=10);
if(y)z[++Z]='-';while(sr[++C]=z[Z],--Z);sr[++C]=t;flush();
}
in void write(char *s) {re l=strlen(s);for(re i=0;i<l;i++)sr[++C]=*s++;sr[++C]='\n';flush();}
};
using namespace fast_io;
int n,ans;
int main()
{
n=read();
while(n--) ans^=read();
write(ans,'\n');
return ot(),0;
}
```