给定异或值与两数范围，求两数的最大可能和

你已经找对了核心方向：X+Y = K + 2(X&Y)*，所以最大化X+Y等价于最大化X&Y。结合X^Y=K的约束，我们可以推导两个关键结论：

1. 由异或的逆运算可得：**Y = X^{K**，因此问题可转化为寻找X∈[a,b]，使得Y=X}K∈[c,d]，同时最大化X&Y。
2. X&Y的二进制位中，只有当K的对应位为0时，才可能为1（若K的位为1，X和Y的位必然一0一1，按位与结果为0）。因此**X&Y = X & (_{K)**（这里的}K用61位掩码截断，避免符号位干扰），最大化X&Y等价于在K的位为0的位置上，尽可能让X的对应位为1。

贪心构造最优X #

我们采用从高位到低位（覆盖1e18只需60位）的贪心策略，逐位确定X的每一位：

1. 初始化current_x为0，代表当前构造的X前缀。
2. 对每一位i（从60到0）：
   • 尝试将X的第i位设为1，得到候选值candidate。
   • 计算该候选值对应的X范围：[candidate, candidate | ((1<<i)-1)]（低位全设为1），再将其裁剪到[a,b]范围内，得到[low_x, high_x]。
   • 检查是否存在X∈[low_x, high_x]，使得Y=X^K∈[c,d]。若存在，则保留该位为1（这能让X&Y更大）；否则保持该位为0。
3. 构造完成后，验证最终的X是否满足所有约束，若满足则计算X+Y，否则返回无解。

关键：判断可行解是否存在 #

要判断是否存在X∈[L,R]使得X^{K∈[C,D]，我们可以先计算X∈[L,R]时Y=X}K的所有可能区间，再检查这些区间是否与[C,D]有交集。计算Y的区间可通过递归拆分实现：

• 若L==R，Y的区间就是[L^K, L^K]。
• 若L<R，找到最高位i使得L和R的该位不同，将X的范围拆分为[L, (1<<i)-1]和[(1<<i), R]，递归计算这两个范围对应的Y区间，最后合并相邻区间。

代码实现 #

def get_intervals(L, R, K):
    if L > R:
        return []
    if L == R:
        return [(L ^ K, L ^ K)]
    # 找到最高位不同的位
    i = 60
    while i >= 0 and ((L >> i) & 1) == ((R >> i) & 1):
        i -= 1
    if i < 0:
        return [(L ^ K, R ^ K)]
    mask = (1 << i) - 1
    left_intervals = get_intervals(L, mask, K)
    right_intervals = get_intervals(1 << i, R, K)
    # 合并区间
    merged = left_intervals + right_intervals
    merged.sort()
    res = []
    for s, e in merged:
        if res and s <= res[-1][1] + 1:
            res[-1] = (res[-1][0], max(res[-1][1], e))
        else:
            res.append((s, e))
    return res

def has_overlap(intervals, C, D):
    for s, e in intervals:
        if not (e < C or s > D):
            return True
    return False

def max_xor_sum(a, b, c, d, k):
    # 计算掩码：K的位为0的位置设为1，其他为0
    mask = ((1 << 61) - 1) ^ k
    current_x = 0
    for i in range(60, -1, -1):
        candidate = current_x | (1 << i)
        # 计算候选X的范围
        low_x = candidate
        high_x = candidate | ((1 << i) - 1)
        # 裁剪到[a,b]
        low_x = max(low_x, a)
        high_x = min(high_x, b)
        if low_x > high_x:
            continue
        # 检查是否存在X在[low_x, high_x]使得X^k在[c,d]
        y_intervals = get_intervals(low_x, high_x, k)
        if has_overlap(y_intervals, c, d):
            current_x = candidate
    # 验证最终的X是否满足条件
    y = current_x ^ k
    if a <= current_x <= b and c <= y <= d:
        return k + 2 * (current_x & mask)
    else:
        return -1

# 示例调用
a, b, c, d, k = map(int, input().split())
result = max_xor_sum(a, b, c, d, k)
print(result if result != -1 else "无解")

时间复杂度分析 #

该算法的时间复杂度为O(60²)，每一位处理时递归拆分区间最多需要60次，整体为对数级，完全可以处理1e18的范围，彻底解决了暴力解法的时间爆炸问题。

内容的提问来源于stack exchange，提问作者Coder