洛谷P12972题解

题目链接：https://www.luogu.com.cn/problem/P12972。

---

如果这道题你去看简易题面，你成功的被套进去了。

我们化简精力计算公式，可以得到：

$$(k \operatorname{and} a_j)+(k \operatorname{xor} a_j)−k=a_j$$

因此，每轮的总精力消耗为该轮中所有饮料重量的按位或。

为了最小化总和，应让每轮的按位或尽可能小。

所以最终结论就是：

所有饮料的按位或之和的最小值，等于所有饮料重量的按位或结果。

按上面的思路可以写出以下代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, x, ans = 0;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> x;
        ans |= x;
    }
    cout << ans;
    return 0;
}

but，你会发现只会得到 $20$，注意观察数据范围，$0\leq a_i \leq 2^{63}-1$，这已经超出了 int 类型的存储范围，所以需要使用 long long 类型存储。

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