首页 > 代码库 > HDU 5491 The Next(位运算)
HDU 5491 The Next(位运算)
题意:已知D(0<=D<2^31)、s1、s2,其中L为D转化为二进制数时1的个数,题目保证s1<=L<=s2,求一个数,满足以下条件:
1、比D大
2、转化为二进制时1的个数在[s1, s2]内
3、找出满足1、2条件的最小数字
分析:
1、首先将D加1,假设该数为x,求出x转化为二进制时1的个数cnt。
2、若s1<=cnt<=s2,则输出x
3、若cnt<s1,则应当增加1的数目,因为要保证找到的数字最小,所以要从二进制数的最右边开始改变。
方法:从右向左,将找到第一个0变为1,假设找到的这个0的位数为i(从右往左数第一个数字位数为0,以此类推),那将该数字变为1时,D会增加2^i。(eg:5的二进制数位101,将第1位的0变为1,则是111,转化为十进制是7,,5变成7增加了2^1)
4、若cnt>s1,则应当减少1的数目,因为要保证找到的数字最小,所以要从二进制数的最右边开始改变。
方法:从右向左,将找到第一个1变为0,假设找到的这个1的位数为i(从右往左数第一个数字位数为0,以此类推),那将该数字变为0时,D会增加2^i。(eg:6的二进制数位110,将第1位的1变为0,则是1000,转化为十进制是8,,6变成8增加了2^1)
5、循环上述操作直到满足条件。
6、如上解法的原因有二:
(1)因为是在二进制上操作,所以当cnt<s1加1时,就不必要调用get函数求二进制中1的个数(如果这道题想暴力水过的话,就容易明白这句话)
(2)最最主要的原因是,它跳过了许多不满足的中间数字。
如以下例子:D = 4, s1 = 1, s2 = 1,为了方便理解可以看下表。
按照该题的解题思路,D+1为5,那么因为其二进制数中1的个数是2,cnt>s2,因此按代码操作后D为6,仍cnt>s2,继续按代码操作,可得D为8,跳过了D为7的情况,这种跳过的现象数越大越明显,此处不再举例。
#include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<stack> #include<deque> #include<queue> #include<list> #define Min(a, b) a < b ? a : b #define Max(a, b) a < b ? b : a typedef long long ll; typedef unsigned long long llu; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const ll LL_INF = 0x3f3f3f3f3f3f3f3f; const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f; const int dr[] = {0, 0, -1, 1}; const int dc[] = {-1, 1, 0, 0}; const double pi = acos(-1.0); const double eps = 1e-8; const int MAXN = 100 + 10; const int MAXT = 10000 + 10; using namespace std; int a[MAXN]; int get(ll n){//求二进制数中1的个数,边求边将D+1的二进制数依次存入数组a,便于之后从右向左找第一个1或第一个0 int k = 0; int cnt = 0; while(n){ a[k++] = n % 2; if(n & 1) ++cnt; n >>= 1; } return cnt; } ll POW(int k){//快速幂,因为该题只需求2的k次幂,所以只传了k ll ans = ll(1); ll x = ll(2); while(k){ if(k & 1) ans *= x; x *= x; k >>= 1; } return ans; } int main(){ int T; scanf("%d", &T); for(int i = 1; i <= T; ++i){ memset(a, 0, sizeof a); ll D; int s1, s2; scanf("%lld%d%d", &D, &s1, &s2); printf("Case #%d: ", i); int cnt = get(++D); while(1){ if(cnt >= s1 && cnt <= s2){ printf("%lld\n", D); break; } else if(cnt < s1){ int k = 0; while(a[k]) ++k; a[k] = 1;//将0变成1,a数组中存的是D的二进制数 D += POW(k); ++cnt;//注意1的个数要增加 } else if(cnt > s2){ int k = 0; while(!a[k]) ++k; D += POW(k);//此处可以改为lowbit(D),所需函数如下 cnt = get(D);//1的个数可能不变,可能减少,此处不仅重新计算了D的二进制中1的个数,而且更新了a数组,存进了新的D的二进制数,便于之后从右向左找第一个1或第一个0 } } } return 0; }
PS:lowbit的功能是求2^p,p为x的二进制数中,从右向左数第一个1的位置(从右往左数第一个数字位数为0,以此类推)
int Lowbit(int x){
return x&(-x);
}
eg:若x=9,则9&-9为0000 1001 & 1111 0111,结果为1.(注意该二进制是补码表示,最左边的位为符号位,正数为0 ,负数为1,原码变为补码是按位取反再加1)
而9的二进制数时1001,从右向左数第一个1的位置,其位数为0,所以Lowbit(9) = 2^0 = 1.
HDU 5491 The Next(位运算)