看了题解才知道这个性质:
a
⊕
b
≤
a
+
b
a oplus b le a+b
a⊕b≤a+b
粗略证明:
由
0
+
0
=
0
,
0
⊕
0
=
0
1
+
0
=
1
,
1
⊕
0
=
1
0
+
1
=
1
,
0
⊕
1
=
1
1
+
1
=
2
,
1
⊕
1
=
0
0+0=0,0oplus 0=0\ 1+0=1,1oplus 0=1\ 0+1=1,0oplus 1=1\ 1+1=2,1oplus 1=0
0+0=0,0⊕0=01+0=1,1⊕0=10+1=1,0⊕1=11+1=2,1⊕1=0
可以得到:
a
⊕
b
≤
a
+
b
a oplus b le a+b
a⊕b≤a+b
回到题目,设分成了2组,得到结果为c,d,原数为 a 1 , a 2 , a 3 , a 4 a_1,a_2,a_3,a_4 a1,a2,a3,a4,则 c + d = ( a 1 ⊕ a 2 ) + ( a 3 ⊕ a 4 ) ≥ a 1 ⊕ a 2 ⊕ a 3 ⊕ a 4 c + d =(a_1 oplus a_2)+(a_3 oplus a_4)ge a_1 oplus a_2 oplus a_3 oplus a_4 c+d=(a1⊕a2)+(a3⊕a4)≥a1⊕a2⊕a3⊕a4
代码:
#include <bits/stdc++.h>
using namespace std;
int n,ans,p;
int main()
{
cin>>n;
cin>>ans;
for(int i=2;i<=n;i++)
{
cin>>p;
ans=ans^p;
}
cout<<ans;
return 0;
}