通过按位或生成所需数字

Question

给定N个整数区间[lo_i,hi_i]。

从每个区间中选择一个数字，使它们的按位或值成为给定的数字X。（如果生成的数字是Y，则即使结果比X有更多的1位，也不重要；即应满足(X&Y)==X）

- a-z

---

所有区间只需要一个 X 吗？ - Ade YU

对于每个区间，选择一个Y，使得 X|Y == X？如果该区间中没有这样的数字 Y，该怎么办？我正在考虑 [8, 9] 和 X = 6。 - hroptatyr

你能提供一个例子吗？就像这样：当X == 15时，从[13,14]和[1,2]中，你选择了14和1，使得(14 | 1) & X == X。 - Ade YU

用蛮力方法做这件事很容易，但速度极慢（现在不仅取决于N，还取决于范围的大小）- 我想你希望得到一些合理的东西？我看了很多二分图匹配和集合覆盖问题，但我没有找到合适的解决方法。我能想到的最好的方法是采用蛮力方法并进行一些修剪（例如，如果某个位只出现在一个区间的上半部分中，那么您必须从该区间的上半部分选择一个数字）。 - harold

异或运算已经具有这个属性 (a xor b) xor b = a。 - John Eipe

@John 那又怎样？OP说的是OR，不是XOR，而且由于这个属性，它似乎是一个更难的问题 - 每次选择一个数字都可能会撤销以前的工作（所以我看不到任何修剪的方法）。 - harold

Answer 1

我猜这个问题是NP完全的，尽管我还没有找到一个易于约化到此问题的NP困难问题。

但对于那些包含2^(最高有效位)-1的集合，我会使用启发式方法：首先，尝试数字1...1(最高有效位-1个1)，其次是具有最高有效位和尽可能多的其他位设置的数字。这种启发式方法只有在您需要从设置了最高有效位和少量不同较低有效位的集合中选择数字时才会表现不佳。

借助这种启发式方法，您也可以从这些集合中选择最大的数字1....1作为进一步的启发式方法。

- DaveFar

Answer 2

让我们一般化这个问题。我将编写位运算符，如OR、AND和SR（右移）。

给定自然数X，由自然数组成的区间[lo_1, hi_1]，...，[lo_N，hi_N]和位b（0或1），确定是否存在自然数y_1在[lo_1，hi_1]中，...，y_N在[lo_N，hi_N]中，使得令Y = y_1 OR ... OR y_N，则(X AND Y) = X，并且存在i使得x_i <= hi_i - b。

我的递归算法的基本情况是当lo_1 = hi_1 = lo_2 = ... = hi_n = 0时。只有当X = 0且b = 0时才存在解决方案。

归纳地，通过让X'= X SR 1，lo_i' = lo_i SR 1和hi_i' = hi_i SR 1来准备子问题。如果hi_i AND 1 = 1，则Odd(i)为true。如果奇数，则Odd +(i)为true，如果Odd(i) and lo_i < hi_i。如果X AND 1 = 0：

如果存在i使得Odd+(i)，则令b'=0。否则，让b'=b。

如果X AND 1 = 1：

如果存在不同的i和j，使得Odd+(i)和Odd(j)，则令b'=0。如果不存在j使得Odd(j)，则令b'=1。否则，让b'=b。

返回子问题的答案。

- yabba dabba doo