欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Light Emitting Hindenburg 解题思路

程序员文章站 2022-05-22 08:23:18
...

题目大意:

给你n个数,你从里面选出k个数,是他们相与(&)起来的值最大。
题目地址:https://nanti.jisuanke.com/t/45643

思考过程:

在二进制下,假设a有一位是1(前面都是0),而b的那一位是0,且前面没有1,那么无论b的后面是多少,a永远大于b
所以,从最开始的一位检查,如果能找到k个数,这k个数这一位是1,那么这k个数一定有构成最优解的潜质。所以就不断地这么从前往后找。

具体过程:

从第一位开始检索,统计这一位是1的个数,如果这一位为1的数的个数大于k,那么这一位肯定有戏,以后就从这几个数里面选,放弃掉这一位不是1的数。如果小于k,那么这一位就没戏了,直接取检查下一位。
最后,把所有没有放弃的数&起来就是最终结果了。
有多种可能情况也没事,因为有多种情况说明有几个数是一样的,他们&起来也是一样的。

#include<cstdio>
#include<iostream>
using namespace std;
#define ll long long
const int maxn=2e5+7;

int a[maxn],sc[maxn],n,k;

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=31;i>=0;--i){
        int cnt=0;
        for(int j=1;j<=n;++j)
            if(sc[j]==0&&((a[j]>>i)&1))
                cnt++;
        if(cnt<k) continue;
        else{
            for(int j=1;j<=n;++j)
                if(sc[j]==0&&((a[j]>>i)&1)==0)//如果能凑够k个数,而这个数这一位不是1
                    sc[j]=1;//放弃了这个数
        }
    }
    int ans=-1;
    for(int i=1;i<=n;++i)
        if(!sc[i]) ans&=a[i];
    printf("%d\n",ans);
    return 0;
}

一些思考:

比赛的时候只考虑了最靠前能凑够k个数的情况,没考虑后面的,然后考虑到了之后不知道怎么实现(码力不足),之后才发现这种不断做标记的方法。

最后送大家一个可爱的33娘!!

Light Emitting Hindenburg 解题思路

每日中二

不要被眼下的烦恼所击退!!