模拟+位运算 HDOJ 5491 The Next-白红宇

模拟+位运算 HDOJ 5491 The Next

阅读量：7113 次

发布时间：2019-06-28

本文共 1508 字，大约阅读时间需要 5 分钟。

题意：意思很简单，找一个最接近D且比D大的数，满足它的二进制表示下的1的个数在[S1, S2]之间

分析：从D + 1开始，若个数小于S1，那么从低位向高位把0替换成1直到S1就是最小值，否则往更大的数去找，此时目标是减少1的数量，可以优化, +lowbit (D)，因为+小于lowbit (D)只会增加1的数量。这题比赛时队友想的很复杂，方法不够简单暴力。

/************************************************* Author        :Running_Time* Created Time  :2015/9/28 星期一 09:19:08* File Name     :H.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;const double EPS = 1e-8;int b[64];int low_bit(int i) { return i & (-i);}int main(void) { int T, cas = 0; scanf ("%d", &T); while (T--) { int S1, S2; ll D; scanf ("%I64d%d%d", &D, &S1, &S2); memset (b, 0, sizeof (b)); int n = 0, j = 0; D++; do { ll tmp = D; j = 0; n = 0; while (tmp) { if (tmp & 1) { b[j++] = 1; n++; } else b[j++] = 0; tmp >>= 1; } if (n < S1) { int add = S1 - n; j = 0; while (add) { if (!b[j]) b[j] = 1, add--; j++; } break; } else D += low_bit (D); }while (n < S1 || n > S2); ll ans = 0, x = 1; for (int i=0; i<64; ++i) { if (b[i]) ans += x; x <<= 1; } printf ("Case #%d: %I64d\n", ++cas, ans); } return 0;}

转载于:https://www.cnblogs.com/Running-Time/p/4844374.html

你可能感兴趣的文章