题目链接

构造异或三角形

题目描述

给定一个正整数 ，请判断是否存在一个正整数 ，满足以下两个条件：

  2. 边长为 , , 和 的三条边能构成一个非退化三角形。

若存在，输出任意一个满足条件的 ；否则输出 -1。

解题思路

这是一个结合了位运算和几何性质的构造性问题。

1. 问题转化与条件简化

我们要寻找一个正整数 ()，使得三条边 , , 满足三角不等式（两边之和大于第三边）：

我们可以利用一个关键的位运算恒等式 来分析上述不等式。

  • 对于条件 1 ():
    代入恒等式得 ，简化后得到 ，即 。
    这意味着， 和 的二进制表示中，必须至少有一位是共同的 1。

  • 对于条件 2 ():
    这个条件总是成立的。因为 ， 的最高有效位 (MSB) 的位置必然大于等于 的 MSB。 的结果是一个正数。一个正数 加上另一个正数，其和必然大于 。

  • 对于条件 3 ():
    代入恒等式得 。
    因为 ，所以不等式变为 ，简化后得到 。
    这意味着， 和 的二进制表示中，必须至少有一位是共同的 1。

综上，我们的任务被简化为：寻找一个 ()，使得它同时满足以下两个位运算条件：

  1. N & b != 0
  2. b & (N ^ b) != 0

2. 寻找构造方法

现在问题变成了如何构造一个满足条件的 。我们可以先分析哪些情况下解不存在。

  • 无解情况 1: 是 2 的幂
    如果 是 2 的幂（例如 2, 4, 8, ...），那么其二进制表示只有一个 1（在最高位）。对于任何 ， 的所有 1 都在比 的 1 更低的位置上。因此， 永远为 0，无法满足第一个条件。故无解。
    判断方法：N > 0 && (N & (N - 1)) == 0。

  • 无解情况 2: 是形如 的数
    如果 是形如 的数（例如 3, 7, 15, ...），其二进制表示为连续 个 1。对于任意 ，N ^ b 在这 位中等价于按位取反。这意味着 和 在这 位中没有共同的 1，所以 永远为 0，无法满足第二个条件。故无解。
    判断方法：N > 0 && (N & (N + 1)) == 0。

  • 有解情况的构造
    对于其他所有情况，解是存在的。题目要求我们给出任意一个解即可。一个简单且有效的构造方法如下：

    1. 找到小于 的最大的 2 的幂，记为 。（例如，, ；, ）。
    2. 令 。

    这个构造可以被证明在所有有解的情况下都满足上述两个位运算条件。

3. 最终算法

  1. 读入 。
  2. 判断 是否为 2 的幂，或者是否为 的形式。如果是，输出 -1。
  3. 否则，计算小于 的最大的 2 的幂 ，然后输出 。

代码

#include <iostream>

using namespace std;

// Function to find the highest power of 2 less than n
long long highestPowerOf2(long long n) {
    long long p = 1;
    while (p * 2 < n) {
        p *= 2;
    }
    return p;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        // Case 1: n is a power of 2
        bool is_power_of_2 = (n > 0) && ((n & (n - 1)) == 0);
        // Case 2: n is of the form 2^k - 1
        bool is_mersenne_form = (n > 0) && ((n & (n + 1)) == 0);

        if (is_power_of_2 || is_mersenne_form) {
            cout << -1 << endl;
        } else {
            long long k = 1;
            while (k < n) {
                k *= 2;
            }
            // k is now the smallest power of 2 >= n.
            // We need the largest power of 2 < n, which is k/2.
            k /= 2;
            cout << k - 1 << endl;
        }
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            long n = sc.nextLong();

            // Case 1: n is a power of 2
            boolean isPowerOf2 = (n > 0) && ((n & (n - 1)) == 0);
            // Case 2: n is of the form 2^k - 1
            boolean isMersenneForm = (n > 0) && ((n & (n + 1)) == 0);

            if (isPowerOf2 || isMersenneForm) {
                System.out.println(-1);
            } else {
                // Find the highest power of 2 less than n
                long k = 1;
                while (k < n) {
                    k <<= 1;
                }
                k >>= 1;
                System.out.println(k - 1);
            }
        }
    }
}

import sys

def solve():
    n_str = sys.stdin.readline()
    if not n_str: return
    n = int(n_str)

    # Case 1: n is a power of 2
    is_power_of_2 = (n > 0 and (n & (n - 1)) == 0)
    # Case 2: n is of the form 2^k - 1
    is_mersenne_form = (n > 0 and (n & (n + 1)) == 0)
    
    if is_power_of_2 or is_mersenne_form:
        print(-1)
        return

    # For other cases, a constructive solution exists.
    # Find the highest power of 2 less than n
    k = 1
    while k < n:
        k <<= 1
    k >>= 1
    print(k - 1)


def main():
    t_str = sys.stdin.readline()
    if not t_str: return
    t = int(t_str)
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法: 位运算、数学构造
  • 时间复杂度: 对于每个测试用例，我们通过循环来找到小于 的最大2的幂，这个过程的复杂度是 。总的时间复杂度为 。
  • 空间复杂度: 没有使用与输入规模相关的额外存储空间，空间复杂度为 。