第 2 届河北省大学生程序设计竞赛（河北省赛）-Problem H. 神殿-题解

本文主要是介绍第 2 届河北省大学生程序设计竞赛（河北省赛）-Problem H. 神殿-题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

Problem A. Mex Query

Problem B. Nim Game

Problem C. icebound 的账单

Problem G. 520

Problem H. 神殿

Problem J. icebound 的商店

Problem K. Bitmap

       哈希讲解

       二维哈希讲解

Problem L. 跑图

Problem H. 神殿

Time Limit: 1000ms
Memory Limit: 65536KB

Description

icebound通过勤工俭学，攒了一小笔钱，于是他决定出国旅游。这天，icebound走进了一个神秘的神殿。神殿由八位守护者守卫，总共由$64$个门组成，每一道门后都有一个迷宫，迷宫的大小均为$100\times 100$。icebound在迷宫中总共耗时$T$小时，消耗食物$K$公斤。历经千辛万苦之后，icebound终于穿越了迷宫，到达了神殿的中心。神殿的中心有一个宝箱。宝箱上显示有两个正整数$l$和$r$。icebound苦思冥想，终于发现一些打开宝箱的线索。你需要找到一个数$P$，它具有一个美妙的性质：它是$[l,r]$中所有数的二进制表示里，$1$的个数最多的一个数。如果你发现了这个美妙的数字，你就可以打开宝箱，获得巨额财富。

比如$[4,8]$中：

4: 0100
5: 0101
6: 0110
7: 0111
8: 1000

二进制表示中$1$的个数最多的数是$7$，它含有$3$个$1$。

Input

输入一行，两个正整数：ll和rr，用空格隔开，代表神殿中宝箱上显示的数。

$1\le T<2^{31}$ ,

$1\le K\le 10^5$ ,

$1\le l\le r\le 10^6$

Output

一个十进制数$P$，代表满足条件的解。如果有多个$P$满足条件，输出最小的$P$。

Sample Input

4 8

Sample Output

7

---

题目大意

前面一堆其实不用管，给你一个$l$和一个$r$，让你输出从$l$到$r$的所有的数中，二进制状态下$1$最多的数。
如果有多个，就输出最小的那个。

---

解题思路

这是一道阅读理解题，题目不短，有效信息不多。
$l$和$r$的范围都是$10^6$，而$2^{20}=1048576>10^6$，因此每个数最多看它的$20$位就够了。$10^6\times 20=2e7$，暴力可以通过。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int get(int n)//get(n)的作用是返回n的二进制有多少个1
{int s=0;//初始值有0个1while(n)//n不为0时{s+=n&1;//加上最后一位n>>=1;//右移一位}return s;
}
int main()
{int a,b;int M=-1;//M来记录最大的0的个数cin>>a>>b;int ans;for(int i=a;i<=b;i++)//从a到b枚举{int t=get(i);//i的二进制有get(i)个1if(t>M)//如果大于历史最多{M=t;//更新ans=i;}}cout<<ans<<endl;//输出return 0;
}

---

原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/116534218

这篇关于第 2 届河北省大学生程序设计竞赛（河北省赛）-Problem H. 神殿-题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---