首页 > 试题广场 >

整数覆盖

[编程题]整数覆盖

我们称正整数 $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

算法知识视频讲解

Silencer76

发表于 2025-08-31 16:39:27

题目链接整数覆盖题目描述给定个正整数。我们定义一个正整数 “包含” 另一个正整数，当且仅当 (A | B) == A，其中 | 是按位或运算。这个条件的含义是，在二进制表示下，所有中为的位，在中也必须为。任务是从这个数中选出尽可能少的数，组成一个集合，使得原来个展开全文

动态规划位运算

难度：

0条回答 2收藏 63浏览

整数覆盖

扫一扫，把题目装进口袋