传送门
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 A. Mex QueryProblem B. Nim GameProblem C. icebound 的账单Problem G. 520Problem H. 神殿Problem J. icebound 的商店Problem K. Bitmap哈希讲解二维哈希讲解Problem L. 跑图Problem H. 神殿DescriptionInputOutputSample InputSample Output题目大意解题思路AC代码Problem H. 神殿
Time Limit: 1000ms
Memory Limit: 65536KB
Description
icebound通过勤工俭学，攒了一小笔钱，于是他决定出国旅游。这天，icebound走进了一个神秘的神殿。神殿由八位守护者守卫，总共由646464个门组成，每一道门后都有一个迷宫，迷宫的大小均为100×100100 \times 100100×100。icebound在迷宫中总共耗时TTT小时，消耗食物KKK公斤。历经千辛万苦之后，icebound终于穿越了迷宫，到达了神殿的中心。神殿的中心有一个宝箱。宝箱上显示有两个正整数lll和rrr。icebound苦思冥想，终于发现一些打开宝箱的线索。你需要找到一个数PPP，它具有一个美妙的性质：它是[l,r][l,r][l,r]中所有数的二进制表示里，111的个数最多的一个数。如果你发现了这个美妙的数字，你就可以打开宝箱，获得巨额财富。
比如[4,8][4,8][4,8]中：
4: 0100
5: 0101
6: 0110
7: 0111
8: 1000
二进制表示中111的个数最多的数是777，它含有333个111。
Input
输入一行，两个正整数：ll和rr，用空格隔开，代表神殿中宝箱上显示的数。
1≤T<2311 \leq T < 2^{31}1≤T<231 ,
1≤K≤1051 \leq K \leq 10^51≤K≤105 ,
1≤l≤r≤1061 \leq l \leq r \leq 10^{6}1≤l≤r≤106
Output
一个十进制数PPP，代表满足条件的解。如果有多个PPP满足条件，输出最小的PPP。
Sample Input
4 8
Sample Output
7
题目大意
前面一堆其实不用管，给你一个lll和一个rrr，让你输出从lll到rrr的所有的数中，二进制状态下111最多的数。
如果有多个，就输出最小的那个。
解题思路
这是一道阅读理解题，题目不短，有效信息不多。
lll和rrr的范围都是10610^6106，而220=1048576>1062^{20}=1048576>10^6220=1048576>106，因此每个数最多看它的20位就够了。106×20=2e710^6\times20=2e7106×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./article/details/116534218
