当前位置：首页 > news >正文

【TUST“码蹄杯”编程之星】4.27 每日一题

news 2025/4/28 10:22:54

题目要求

你被给定一个大小为n的数组a。

你可以对该数组执行以下操作：

选择两个不同的整数i,j（1≤i<j≤n），将ai替换为x，aj替换为y。为了不破坏数组，必须满足ai | aj = x | y，其中 | 表示按位或运算。注意x和y是非负整数。
请输出在使用上述操作任意次数后，数组元素可能的最小总和。

输入格式

第一行包含一个整数n（2≤n≤100）——数组a的大小。

第二行包含n个整数a1,a2,…,an（0≤ai<2^30）。

输出格式

输出
每个测试用例输出一行一个数字——数组可能的最小总和。

输入数据：

14
571222016 671296024 538780184 43909120 34540040 168034840 143008256 926208 34545664 680010264 578887680 33696264 546048000 671221760

实现步骤

1.操作观察

答案希望最小化和，且只涉及到按位或操作，那希望0的个数越多越好，根据题目保证两两按位或之后更换的两个数按位或结果不变，因此很自然联想到任何一个数和0按位或结果为0，所以我们不妨疯狂把ai bi变为ai | bi 和 0，因此一路按位或下去就行了。

2.实现思路

读取输入。
遍历，将数组变为一个数包含所有原始元素的按位或，其他都是0。
输出ans

代码示例

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef __int128_t i128;
#define N 200005
const int M = 1e9 + 7;
void solve()
{int n;cin >> n;vector<i64> a(n);for (int i = 0; i < n; i++){cin >> a[i];}i64 ans = 0;for (int i = 0; i < n; i++){ans |= a[i];}cout << ans;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();return 0;
}