出题人题解||快去打瓦 题解

T1_快去打瓦 题解

前置知识：$a+b=(a\oplus b)+2(a\land b)$

其中 $\oplus$ 表示异或运算，$\land$ 表示 $\tt{C++}$ 里面的 $\&$ 运算。

稍微说一下，$a\oplus b$ 表示了二进制下 $a+b$ 但是不考虑进位，不处理进位的结果，即不进位加。

然后 $a\land b$ 又表示二进制下所有 $a+b$ 会进位的位权和，把这个位权和乘 $2$ 就是只处理进位得到的结果。

所以把这两个东西加在一起就是 $a+b$。

---

然后对于本题我们有一个结论如下。

结论：$a\oplus b\le a+b$。

证明：

• $\because a+b=(a\oplus b)+2(a\land b)$
• $\therefore a+b-(a\oplus b)=2(a\land b)$
• $\because 2(a\land b)\ge 0$
• $\therefore a+b-a\oplus b\ge 0$
• $\therefore a+b\ge a\oplus b$
• $\therefore a\oplus b\le a+b$

证毕。

所以两个数的时候答案就是这两个数的和，同理，三个数的时候就是三个数的和，$n$ 个数的时候就是 $\sum a$。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,x,ans;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1;i<=n;++i){
        cin>>x;
        ans+=x;
    }
    cout<<ans;
}

时间复杂度：$O(n)$