首页 > 试题广场 >

组数制进二

[编程题]组数制进二
  • 热度指数：998 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}小美有一个长度为 n 的数组 \{a_1,a_2,\dots,a_n\}，他希望构造一个非负整数 x，满足 x 的二进制位数不超过数组中最大值的二进制位数（特别的 0 二进制位数为 1 ）。
\hspace{15pt}随后，可对数组 a 重复进行以下操作，以使所有元素的总和最大：
\hspace{23pt}\bullet\,选择一个下标 i，同时将 a_i 修改为 a_i\operatorname{or} x，将 x 修改为 a_i\operatorname{and} x。
\hspace{15pt}在使元素总和达到最大值的前提下，要求所有操作前初始的 x 尽可能小。请输出最大总和及对应的最小 x。

\hspace{15pt}按位或：\operatorname{or} 表示按位或运算，即对两个整数的二进制表示的每一位进行逻辑或操作。
\hspace{15pt}按位与：\operatorname{and} 表示按位与运算，即对两个整数的二进制表示的每一位进行逻辑与操作。

输入描述:
\hspace{15pt}每个测试文件均包含多组测试数据。 
\hspace{15pt}第一行输入一个整数 T\left(1\leqq T\leqq 1000\right)，代表数据组数； 

\hspace{15pt}对于每组测试数据，输入如下： 
\hspace{15pt}第一行输入一个整数 n\left(1\leqq n\leqq 500\right)，表示数组的长度； 
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n\left(0\leqq a_i<2^{30}\right)，表示数组 a 的元素。


输出描述:
\hspace{15pt}对于每组测试数据，新起一行。输出两个整数，用空格分隔：第一个整数为数组可以达到的最大总和；第二个整数为在达到最大总和的前提下初始最小的 x。
示例1

输入

2
2
3 3
3
1 2 3

输出

6 0
9 3
算法知识视频讲解
开通博客
头像 Silencer76
发表于 2025-08-28 00:33:08
题目链接 组数制进二 题目描述 给定一个长度为 的数组 。我们需要构造一个非负整数 ，其二进制位数不超过数组中最大值的二进制位数。然后，可以对数组 重复执行以下操作： 选择一个下标 和当前的整数 。 将 更新为 （按位或）。 将 更新为 （按位与）。 目标是： 找到使数组元素最终总和 展开全文
去ta的博客 赞 (5) 回复(0) 收起

问题信息

贪心 位运算
难度：
7条回答 691浏览

热门推荐

相关试题

组数制进二

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号