首页 > 试题广场 >

整数覆盖

[编程题]整数覆盖

我们称正整数 $A$ 包含 $B$ ，当且仅当 $(A | B) = A$ ， $|$ 表示按位或运算，即 $B$ 中的所有为 $1$ 的二进制位，在 $A$ 中都为 $1$ .

现在给定 $n$ 个正整数 $A_i$ ，请你从中选出尽量少的整数，使得所有 $A_i$ 都至少被一个你选出来的整数包含。

显然任何一个数总是包含其自身，即选择全部的数必定为一组合法答案（但不一定是最少的）。

第一行一个正整数，接下来一行个整数，第个整数表示。，

一行一个整数，表示至少需要选出几个数字。

示例1

输入

5
3 7 6 8 4

选择数字和，因为，故均被包含（它们的每一个为的二进制位，在中对应的位置上都为）。而被包含。

示例2

8
4 12 16 3 11 7 9 8

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

动态规划位运算

难度：

0条回答 2收藏 64浏览

整数覆盖

扫一扫，把题目装进口袋