题解：P16995 【MX-S15-T1】「DLESS-5」Another OR Problem

__liujy · 2026-07-20 22:56:40 · 题解

P16995 【MX-S15-T1】「DLESS-5」Another OR Problem

好题！

看到这个按位或求 \max 很难不想到按位枚举，但是这个 \sum{b} = k 的限制很烦人，可以考虑能不能知道当 a 固定时，随着 k 的增大，答案的大小变化。

设 f_k(a) 表示

考虑 f_k(a) 与 f_{k+1}(a) 的大小关系。

设 c_{i} 为 a_i + b_i，其中 \sum b = k，\lor_{i = 1}^{n}c_i = f_k(a)。

考虑分讨：

1. 当二进制下的每一个 c_i 的末尾都为 1 时，可以选择末尾连续 1 的数量最小的 c_i 加一，这样，f_{k+1}(a) \ge f_{k}(a)。
2. 当存在二进制下的 c_i 末尾为 0，可以直接对这个 c_i 加一，这时，f_{k+1}(a) \ge f_{k}(a)。

综上，f_{k+1}(a) \ge f_{k}(a)，即数列 \{f_{k}(a) \} 单调不降。

然后就按位枚举，考虑怎么写 \operatorname{check}(x)。

如果已经存在 c_i 的第 x 位为 1，显然满足条件。

否则如果让 c_i 的第 x 位为 1，就需要加上 2^x - (c_i \bmod 2^x)，然后选的肯定是这个值最小的，然后判一下就做完了。

这样就能获得 40 分的高分！

考虑正解。

当进行完操作后 k 不为 0 时，说明还有若干位需要被填，假设 k 在二进制下的第 j 位为 1，考虑这一个 2^j 加在哪一个 b_i 上。若有一个 a_i 满足在二进制下的第 i 位为 0，那么显然可以加在这个 b_i 上，否则选择从第 j 位到最高位连续 1 的个数最小的那一个 i 加上，这是因为 f_k(a) 是单调不降的。 ::::info[code]

#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;
}

::::