好题题解
P16995 【MX-S15-T1】「DLESS-5」Another OR Problem
好题！
看到这个按位或求 很难不想到按位枚举，但是这个 的限制很烦人，可以考虑能不能知道当 固定时，随着 的增大，答案的大小变化。
设 表示
$$\max_{\sum{b} = k}\{ \lor_{i = 1}^{n} (a_i + b_i)\} $$考虑 与 的大小关系。
设 为 ，其中 ，。
考虑分讨：
- 当二进制下的每一个 的末尾都为 时，可以选择末尾连续 的数量最小的 加一，这样，。
- 当存在二进制下的 末尾为 ，可以直接对这个 加一，这时，。
综上，，即数列 单调不降。
然后就按位枚举，考虑怎么写 。
如果已经存在 的第 位为 ，显然满足条件。
否则如果让 的第 位为 ，就需要加上 ，然后选的肯定是这个值最小的，然后判一下就做完了。
这样就能获得 分的高分！
考虑正解。
当进行完操作后 不为 时，说明还有若干位需要被填，假设 在二进制下的第 位为 ，考虑这一个 加在哪一个 上。若有一个 满足在二进制下的第 位为 ，那么显然可以加在这个 上，否则选择从第 位到最高位连续 的个数最小的那一个 加上，这是因为 是单调不降的。
#include<bits/stdc++.h>
const int MAXN = 1e6 + 5;
#define pb push_back
typedef long long LL;
typedef std::pair<int, int> PII;
typedef std::pair<LL, int> PLI;
int n; LL k, a[MAXN], b[MAXN];
LL sum;
inline bool check(int x)
{
for(int i = 1; i <= n; i++)
if((a[i] >> x) & 1)
return 1;
PLI ans = {LLONG_MIN, 0};
for(int i = 1; i <= n; i++)
ans = std::max(ans, {a[i] % (1ll << x), i});
LL nd = (1ll << x) - ans.first;
// std::cout << sum << ' ' << nd << ' ' << ans.first << ' ' << (1ll << x) << '\n';
if(sum + nd <= k)
{
sum += nd, a[ans.second] += nd, b[ans.second] += nd;
// std::cout << x << '\n';
return 1;
}
else return 0;
}
inline void solve()
{
scanf("%d%lld", &n, &k);
for(int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
for(int i = 1; i <= n; i++)
b[i] = 0;
LL ans = 0; sum = 0;
for(int j = 60; ~j; j--)
if(check(j))
ans |= (1ll << j);
k -= sum;
if(k) for(int j = 60; ~j; j--)
{
if(!((k >> j) & 1)) continue;
bool fl = 0;
for(int i = 1; i <= n && !fl; i++)
if(!((a[i] >> j) & 1))
a[i] += (1ll << j), b[i] += (1ll << j), fl = 1;
if(fl) continue;
PII ans = {INT_MAX, 0};
for(int i = 1; i <= n; i++)
{
LL x = (a[i] >> j);
int cnt = 0;
while(x)
{
if(!(x & 1))
break;
x >>= 1, cnt++;
}
ans = std::min(ans, {cnt, i});
}
a[ans.second] += (1ll << j), b[ans.second] += (1ll << j);
}
printf("%lld\n", ans);
for(int i = 1; i <= n; i++)
printf("%lld%c", b[i], (i == n ? '\n' : ' '));
}
int main()
{
int c, T;
scanf("%d%d", &c, &T);
while(T--)
solve();
return 0;
}
73 浏览2 点赞0 收藏0 评论
