Newcoder 156 C.托米的位运算（贪心）_v5zsq的博客-程序员秘密

Description

托米完成了 $1317$ 的上一个任务，十分高兴，可是考验还没有结束

说话间 $1317$ 给了托米 $n$ 个自然数 $a_1... a_n$ , 托米可以选出一些带回家，但是他选出的数需要满足一些条件

设托米选出来了$k $个数$ b_1,b_2… b_k$, 设这个数列 $b$ 的给值为 $b$ 中所有数按位与的结果，如果你能找到一个整除 $b $的最大的$ 2v $,$ (v\ge 0)$，则设定 $v$ 为这个数列的给价，如果不存在这样的 $v$ ，则给价值为$ -1$, $1317$ 希望托米在最大化给价的情况下，最大化$ k$

Input

第一行输入一个整数$ n$, 第二行输入 $a_1...a_n$

$(n\le 10^5,a_1,...,a_n<2^{31})$

Output

第一行输出最大的整数 $k$ , 第二行输出 $k$ 个整数 $b_1... b_k$ , 按原数列的相对顺序输出 (如果行末有额外空格可能会格式错误)

Sample Input

5
1 2 3 4 5

Sample Output

2
4 5

Solution

从大到小枚举 $v$ ，将第 $v$ 位都为 $1$ 的数字取出，若这些数字逻辑与后在第 $v$ 位后都是 $0$ 则说明 $v$ 合法，此时选取的数字显然最多

Code

#include<cstdio>
using namespace std;
#define maxn 100005
int n,a[maxn],ans[maxn],res;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int v=30;v>=0;v--)
	{
		int temp=(1<<v)-1;
		res=0;
		for(int i=1;i<=n;i++)
			if((a[i]>>v)&1)temp=(temp&a[i]),ans[res++]=i;
		if(temp==0)
		{
			printf("%d\n",res);
			for(int i=0;i<res;i++)printf("%d%c",a[ans[i]],i==res-1?'\n':' ');
			break;
		}
	}
	return 0;
}

本文链接：https://blog.csdn.net/V5ZSQ/article/details/82917247

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Xcode12真机调试iOS15提示The code signature version is no longer supported错误的解决_大熊猫侯佩的博客-程序员秘密

用Xcode12.2连接系统为iOS15的真机调试时出现错误，提示: The code signature version is no longer supported。在不升级Xcode的情况下如何解决这个问题呢？Let’s find out!

Verilog语法（一般不常见） -：与 +：的用法_verilog +=_zaifendoujiayou的博客-程序员秘密

语法定义在Verilog2001以后，Verilog支持在范围中是用变量，并且引入心得语法如下： [<base_index> + : bit_width] //由低位到高位 [<base_index> - : bit_width] //由高位到低位语法应用 wire [7:0] b; wire [3:0] a = b[6 - : 4]; //等价于 a = b[6:3] wire [2:0

堆的操作_Whisper_yl的博客-程序员秘密

编写代码，实现最小堆（Min-Heap）的操作。输入格式:第一行是两个不大于1000的正整数N和K，用空格间隔。其中N是堆的容量，需创建一个容量为N的堆。接下来K行，是对这个堆的依次的K项插入或删除操作：用1 x表示插入元素x；用-1表示删除堆顶。接下来一行是一个不大于1000的正整数M，接下来一行是M个整数（在整型范围内），用空格间隔，要求将这M个整数组成的列表调...

android 闪退分析,Android TimeoutException闪退记录及解决_weixin_39593519的博客-程序员秘密

此问题在oppo R9 系列的手机出现较多，而且主要集中在Android 5.1-6.0的手机系统。TimeoutException，在Android 系统里会出现下面这些，在释放资源时，因耗时导致的，可能不是10s,可能会是20s,30s，60s,120s。具体跟手机有关。android.database.CursorWindow.finalize() timed out after 10 se...

servicemanager之启动过程_servicemanager to start with server name:controlin_fanxiaoyu321的博客-程序员秘密

相关代码文件如下：代码路径说明frameworks/native/cmds/servicemanager/service_manager.cservicemanager守护进程启动文件frameworks/native/cmds/servicemanager/binder.cservicemanager在实现时，并没有引用libbinder库，所以将一些和binde...

数组中存放的多个十六进制数合并成一个十六进制数，并转换成十进制(整形)_两个16进制合并_没有简介的我的博客-程序员秘密

利用的就是计算机存储的特性，需要注意大小端1.char sDec[4] = {0x05,0xc5,0xb3,0xea};低字节序的情况下. 并且 int 占用 32bit. char sDec[4] = {0x05,0xc5,0xb3,0xea};int val = 0;char *pBuf = (char*)&val;pBuf[0] = sDec[3];pBuf[1] = sDec[2];pBuf[2] = sDec[1];pBuf[3] = sDec[0];这时val=