使所有数组元素为零的最小AND操作数

Question

我在编程竞赛中遇到了这个问题：

我们给出一个由n个元素组成的数组。在每次迭代中，您可以选择任意两个元素ai和aj，并用ai和aj替换ai。 ＆是按位AND运算符。找到使所有数组元素为零所需的最小AND操作数。

假设存在给定输入的解决方案。这个问题的最佳解决方案是什么？

编辑：我已经为问题添加了我的DP解决方案，运行时间超过1秒。有什么建议加快它？

0 <n <65535

D：基数2的最大位数（0 <D <17）

目标：2 ^ D - 1

T [i] [X] => {n_0，n_1，...，n_i}中使X为零的最小元素数

T [i] [0] = 0

T [0] [X> 0] = INF

T [i] [X] = min（1 + T [i-1] [X＆n_i]，T [i-1] [X]）

T [n] [目标] - >最小AND操作数

Answer 1

我的猜测是你可以通过使你的DP表稀疏来获得所需的加速。我们可以将得到的算法视为从2^D-1到0的广度优先搜索，其中节点是0..2^D-1，边缘从x到x&y，其中y是数组元素。实际上，由于按位AND的可交换性/相关性，我们可以通过要求x&y清除x中设置的最低位来收紧边集。在下面的Python代码中，通过使用映射zero_index可以有效地实现这一点，但在C中我会使用一个数组（并根据需要用位图或数组替换这些集合）。

import collections
import random


def min_and(seq):
    lst = list(seq)
    zero_index = collections.defaultdict(lambda: set(lst))
    for x in lst:
        y = x
        while y:
            zero_index[y & ~(y - 1)].discard(x)
            y &= y - 1
    visited = set()
    fringe = set(lst)
    i = 0
    while 0 not in fringe:
        visited.update(fringe)
        fringe = {
            x & y
            for x in fringe for y in zero_index[x & ~(x - 1)]
            if x & y not in visited
        }
        i += 1
    return i + len(lst) - 1


print(min_and(
    random.randrange(2**18) | random.randrange(2**18) | random.randrange(2**18)
    for i in range(100)))

Answer 2

在我看来，这就像set cover problem。我们需要找到在每个位置都覆盖零的最小子集。一旦找到该子集，生成的“绝对”零可用于将其他元素转换为零。在下面的示例中，子集中的三个元素中的任何一个都可以用作第一个零。

1001
0101<
0011<
1110<
0111

Answer 3

如果问题有给定输入的解决方案，您可以执行以下操作：

1. 选择[0，n-1]之间的索引i（假设数组索引为零）。
2. 对于0和n之间不是i的每个j，执行ai < - ai＆aj。此时，您可以保证a_i等于0，否则问题是不可解决的，因为您按顺序执行了数组中的所有项目。
3. 对于0和n之间的每个不是i的j，执行aj < - ai＆aj。这将对数组中的所有项执行0，使其也为0。

对第一个循环执行和操作n-1次，对第二个循环执行n-1次，因此总共执行2n-2和操作。

编辑：

这假设您无法查看数组中的值。