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娘!!
每日中二
不要被眼下的烦恼所击退!!
上一篇: 如何防治痛风?治疗痛风有方法
下一篇: Spring Boot Admin