codeforces 336C Vasily the Bear and Sequence

点击打开codeforce 336C

思路; 位运算

分析:

1 题目要求找到k个数，使得这k个数的&的结果能够被2^v整除，并且v的值应该要尽量的大

2 一个数能够被2^v整数，说明这个数的二进制的最右边的1后面刚好是v个0，比如20的二进制为10100，那么刚好可以被2^2整除，那么就有最右边的1的后面0的个数刚好为2个

3 那么我们可以通过从大到小枚举v，然后我们去n个数里面找满足“这个数的二进制的最右边的1后面刚好是v个0”，然后进行求&运算，只要我们找到一个满足的就是最后的ans

代码:

#include<set>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 100010;

int n;
int num[MAXN];

void solve(){
    set<int>s;
    for(int v = 30 ; v >= 0 ; v--){
        int val = 1<<v;
        int sum;
        s.clear();
        for(int i = 0 ; i < n ; i++){
            if(num[i]&val){
                if(s.empty())
                    sum = num[i];
                else
                    sum &= num[i]; 
                s.insert(num[i]);
            }
        }
        if(sum%val == 0){
            printf("%d\n" , s.size()); 
            set<int>::iterator it = s.begin();
            printf("%d" , *it++);
            for(; it != s.end() ; it++)
                printf(" %d" , *it);
            puts("");
            return;
        }
    }
}

int main(){
    while(scanf("%d" , &n) != EOF){
         for(int i = 0 ; i < n ; i++)
             scanf("%d" , &num[i]);
         solve();
    }
    return 0;
}