[MtOI2019]永夜的报应 解题报告

题意

给你 $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

#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; 
}