P14664 [KenOI 2025] 异或题 解题报告

· · 题解

算法

考虑按位贪心喵。

弱化

先考虑没有限制咋做喵。显然拆分为二进制喵，于是有：

设 n = \sum ^ {k}_{i = 0} 2^i a_i 喵，其中 a_k = 1 ,\forall 1 \le i \le k \land i \in \Z ，a_i = 0 \land a_i = 1 喵。

则 ans = \sum ^ {k}_{i = 0} (1 + [a_i = 0]) \times 2^i 喵，因为要使和最大喵，对于 i 位而言喵，最终目标中这一位为 0 时喵，两个 0 产生贡献为 0 喵，两个 1 产生贡献为 2 ^ {i + 1} 喵。若目标此位为 1 喵，无论如何构造方案必为一 0 一 1 喵，对结果无影响喵。

推广

我们考虑限制喵，则需将一些同为 1 的位改为同为 0 喵。我们拆位喵，将最高位的 1 分给方案中 a，b 中较大数喵，低位的某一个 1 分给较小数喵。显而易见喵，在这两个 1 中的 0 是必须舍弃贡献的喵，因为构造方案中 a，b 都为 1 时，其中的较大数必定大于了 n 喵。所以喵，我们应当将位值次高的 1 分给较小数喵。

码

有点长喵。

#include<bits/stdc++.h>
#define int long long
#define y1 qht_yjx
#define hash ZhaoAk
#define maxn 200005
#define maxsqt 230 
#define endl "\n"
#define nullptr 0
#define I ios::sync_with_stdio (nullptr);
#define AK cin.tie (nullptr);
#define CSP cout.tie (nullptr);

using namespace std;

int stk[100] ,top;

void work ()
{
    int n;
    cin >> n;
    int ans = 0 ,res = 0 ,ones = 0;
    top = 0;
    while (n)
    {
        stk[top ++] = n & 1;
        n >>= 1;
    }
    top --;
    for (int i = top ;i >= 0 ;i --)
    {
        if (stk[i] == 1)
        {
            ones ++;
            ans += (1 << i);
        }
        else
            if (ones >= 2)
                ans += (1 << (i + 1));
    }
    cout << ans << endl;
}

signed main()
{
    I AK CSP
    int T;
    cin >> T;
    while (T --)    work ();
    return !!!!! ("ShZhao" && "SHzhao");
}
//Code by Lyyq.
//wage.