题解 P5514 【[MtOI2019]永夜的报应】

· · 题解

趁还没有题解赶紧抢占先机

前置芝士： 异或

异或，有人称它为不进位加法，具体运算规则如下

1 xor 1=0

0 xor 1=1

1 xor 0=1

0 xor 0=0

这个题在比赛标记中属于签到题，还算比较简单了，没有什么特别恶心的数论

思路:两个数异或起来一定小于等于他们的和

就一句话！想一想是不是这样

因为异或是两个数二进制下对应的每一位异或的，所以两个数如果相同二进制下没有相同位上有1，就相当于两个相加，如果有相同位置上有1，那么1 xor 1=0,结果将会比和更小

就拿第二个样例来说

6

9 18 36 25 9 32

计算过程 9 xor 18=27

27 xor 36=63

63 xor 25=38

38 xor 9=47

47 xor 32=15

发现异或首先满足交换律，且与分组最小和是等价的！（或者说全部分为一组异或起来）

然后我们就可以很愉快地把所有数异或起来解决这道题了~

code: 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans;
inline int read(){
    char c=getchar();
    int s=1,f=0;
    while(c<'0' or c>'9'){
        if(c=='-')
        s=-1;
        c=getchar();
    }
    while(c>='0' and c<='9'){
        f=f*10+c-'0';
        c=getchar();
    }
    return s*f;
}
signed main(){
    n=read();
    for(register int i=1;i<=n;i++)
    ans=ans^read();//^符号在C++中是异或的意思 
   printf("%lld\n",ans);
    return 0;
}