位运算打表 + 贪心
分析方法:
本题要找一个数k,满足若干条件。k可能不存在,而且没有数据范围,从1 ~ 10^15 挨个试肯定是不行,可以考虑构造此数
第一步
可以先减少条件以简化问题。先去掉 <= M 这个条件,就成了给一个序列 {A1,A2,…,An}, 求argmax(S,k)
即S = {A} 与 k的异或和最大
由数据范围10^15可知道S不会大于50位,可以把S(1000个数的50位的异或和)分解成50位的1000个数的异或和
每一位可分成两大类进行累加,i位是1时把 1<<i累加进s[i][0], i位是0时把 1<<i累加进s[i][1]
这个s[50][2]数组体现了在当前给的序列{A}能构造的S的所有位的值
第二步把条件<=M 考虑进来用s[50][2]构造出 S
如果所有位的最小值之和>M,说明不满足条件<=M,k不存在。
因为是求满足条件的最大的k,可以用贪心的思想从最高位取大值(第i位取1)来构造k和S,
从高位向低位逐位取数,只要构造过程中S <= M,就取可以取1
逐位累加和的最小值也可以打表
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N =1010;
int T, n;
LL m;
LL a[N], c[N];
LL s[50][2]; // s[bit][0]: s[bit][取0]=bit位的异或后得到的值,存储的是int,表示S第bit的值
// s[bit][1]: s[bit][取1]=bit位的异或后得到的值,存储的是int,表示S第bit的值
int main() {
cin>>T;
for(int t = 1; t<=T; t++) {
memset(s,0,sizeof s);
cin>>n>>m;
for(int i = 0; i<n; i++) scanf("%lld", &a[i]);
for(int i = 0; i<n; i++) // 1000个数
for(int b = 0; b<50; b++) // 每个数50位
if (a[i] >> b & 1) // 这个数b位是1
s[b][0] += 1ll << b; // k的b位是0时才能异或后是1
else
s[b][1] += 1ll << b; // 否则,k的b位是1时才能异或后是1
//逐位累加和的最小值也可以打表
for(int i = 0; i<50; i++) c[i] = c[i-1] + min(s[i][0],s[i][1]);
LL k = 0, sum = 0; // sum就是当前构造的S值
if (c[49] > m) k = -1;
else {
for(int b = 49; ~b; b--)
if (sum + c[b-1] + s[b][1] <= m) {
sum += s[b][1]; //构造S时用贪心法,的同时得到k
k += 1ll << b;
}
else sum += s[b][0];
}
printf("Case #%d: %lld\n", t, k);
}
return 0;
}