题解 P5514 【[MtOI2019]永夜的报应】
ShineEternal
2019-08-24 16:21:03
## 往这看！通俗易懂！
# 题目链接：
https://www.luogu.org/problem/P5514
# 分析：
这道题乍一看很没有头绪，于是：
**爆搜**
时间复杂度：$O()$
**期望**得分：$80pts$
这可是pjT2啊，显然我们要找满分的做法。
---
我们看到数据范围：
$n\leq10^6$
这大概就是$O(n)$解决？
于是我就考虑把所有的数给异或起来，因为对照样例发现对了。
但这是为什么呢？
~~我只是定性的判断了一下~~
我们知道一个性质：**两个数的相加和一定大于等于两个数的异或和**
- 因为在异或下一定是没有进位的。而加法是有可能进位的
进行了分组之后我们相当于有一些数是相加的（组与组之间）
如果我们把所有数异或起来，就相当于原本的组之间由相加变成了异或。
例如：a,b,c三个数
原来可能是：
$a+(b$ $xor$ $c)$
现在就是：
$a$ $xor$ $(b$ $xor$ $c)$
~~异或的结合律~~
自然比分组更优（
当然也可能等于分组的情况。
这就是样例带来的迷惑（雾
---
时间复杂度：$O(n)$
---
# $code$:
```cpp
#include<cstdio>
using namespace std;
int main()
{
long long n;
long long ans;
scanf("%lld",&n);
long long x;
scanf("%lld",&x);
ans=x;
for(int i=2;i<=n;i++)
{
scanf("%lld",&x);
ans=ans^x;
}
printf("%lld\n",ans);
return 0;
}
```